GGT Verstädnis Problem bzw Fehlersuche in meinem(!) Code

Don06

Laut Wikipedia sollten die Algorithmen ungefähr so aussehen:

int gcd_iterative(int a, int b)
{
	while (b != 0)
	{
		// siehe Jester
}

int gcd_recursive(int a, int b)
{
	if (b == 0)
		return a;
	else
		return gcd_recursive(b, a % b);
}

Die funktionieren auch für alle Zahlen. Nur wenn einer der beiden 0 ist wird der andere zurückgegeben.

Gruß
Don06

ThaRealMatix

Hm... tut mir leid hab mich wohl falsch ausgedrückt

ich meine ich kann keine rekursive Funktion schreiben die unterscheidet ob a oder b größer ist und entsprechend arbeitet oder?

und die iterative Funktion... tut mir leid ich blicks absolut nicht, egal wie ich rumspiele

Don06

Die rekursive Funktion funktioniert mit _allen_ Werten. Die Werte werden automatisch vertauscht. Geh das ganze doch mal theoretisch auf einem Blatt Papier durch.
Die iterative hat Jester bereits genau beschrieben. Du musst es nur noch in C++ "übersetzen".

Gruß
Don06

ThaRealMatix

Hm...

int ggt( int a, int b)
{

	if (a>b)
	{
		while (b!=0)
		{
			b=a%a%b;
		}
		return b;
	}

	else if (a<b)
	{
		while (b!=0)
		{
			b=a%b%a;
		}
		return b;
	}
}

Funktioniert nicht und egal wie ich rumspiele es will nicht.... was denk ich denn nur falsch -.-

camper

wie kommst du auf a%a%b bzw. a%b%a ?
a%a ist 0 für alle a!=0
a%b ist a, wenn b > a und folglich a%b%a ebenfalls gleich 0

Nicht wild rumspielen, sondern nachdenken und bewusst schreiben.
Nicht das dieser Code irgendetwas mit dem Ursprünglichen zu tun hätte...

ThaRealMatix

Hm...

ich glaube, ich hab es?

int ggt( int a, int b)
{

	if (a>b)
	{
		while (b!=0)
		{
			 b=a%b;
			 return b;
		}		
	}

	else if (a<b)
	{
		while (a!=0)
		{
			a=b%a;
			return a;
		}

	}
}

Edit: zu früh gefreut... die Iterative Lösung gibt mir 21 als bei 70 und 49 Lösung an -.-

Don06

Ich weise nochmal auf das hin, was Jester geschrieben hat:

Jester schrieb:

while(b!=0) 
{ 
  // b!=0, also dürfen wir modulo b rechnen! 
  // ersetze also a durch b und b durch a%b. 
} 

return a;

Es fehlen drei Anweisungen in der Schleife, Jester hat sie (fast) alle beschrieben, Du solltest dir eine Hilfsvariable anlegen, um das Zwischen ergebnis zu speichern.

Gruß
Don06

ThaRealMatix

//GGT
#include <iostream>
using namespace std;

// Rekursiv
int ggtrekursiv(int a, int b)
{
	if (a>b)
	{
		if (a%b==0)
		{
			return b;
		}
		else
			ggtrekursiv(a, a%b);
	}

	else if (a<b)
	{
		if (a%b==0)
		{
			return a;
		}
		else
			ggtrekursiv(b,a%b);
	}

}

int ggt( int a, int b)
{

	if (a>b)
	{
		while (b!=0)
		{
			int c = a%b;
			a = b;
			b = c;
		}

		return a;
	}

	else if (a<b)
	{
		while (a!=0)
		{
			int c = b%a;
			b = a;
			a = c;
		}

		return b;		
	}
}

int main()
{
	int a;
	int b;

	cout << "Bitte geben Sie zwei Integer ein: " << endl;
	cin >> a; cin >> b;

	cout << "Rekursiv: " << ggtrekursiv(a, b) << endl;
	cout << "Iterative Loesung: " << ggt(a, b) << endl;

	system ("PAUSE");

	return 0;
}

ich habs.... ich dachte die ganze zeit ihr meint ich soll nur mti ab und b -.-

Don06

Wie gesagt, die if-Abfragen sind unnötig. Die Algorithmen vertauschen die Werte automatisch. Also:

int gcd_iterative(int a, int b)
{
	while (b != 0)
	{
		int modulo = a % b;
		a = b;
		b = modulo;
	}
	return a;
}

int gcd_recursive(int a, int b)
{
	if (b == 0)
		return a;
	else
		return gcd_recursive(b, a % b);
}

ThaRealMatix

hm sorry aber bei der rekursion ist das definitiv nicht so. ich bekomme da ein falsches ergebnis ohne if

if (a%b==0)
		{
			return b;
		}
		else
			return ggtrekursiv(a, a%b);

ist da a kleiner als b kommt der startwert von a raus

camper

ThaRealMatix schrieb:

hm sorry aber bei der rekursion ist das definitiv nicht so. ich bekomme da ein falsches ergebnis ohne if
if (a%b==0)
		{
			return b;
		}
		else
			return ggtrekursiv(a, a%b);
ist da a kleiner als b kommt der startwert von a raus

stimmt. Ist ja auch nicht das, was vorher gepostet wurde.

return ggtrekursiv([b]b[/b], a%b);