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

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

  • T

    Hallo,

    ich lerne munter weiter C++ ^^ und bin nun bei Rekursion und Iterativer Lösung angelangt. Hier nun mein Lösungsansatz für den Größten Gemeinsamen Teiler:

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

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

int ggt( int a, int b)
{
	if (a>b)
	{
		for (int n=1; n<=b; n++)
		{
			if (a%n == 0 && b%n ==0)
			{
				int ggf= n;
				return ggf;
			}
			else if (b>a)
			{
				for (int n=1; n<=a; n++)
				{
					if (a%n == 0 && b%n ==0)
					{
					int ggf= n;
					return ggf;
					}
				}
			}
		}
	}
}

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;
}

    Das die Rekursive Funktion nur Funktioniert wenn a die größere Integer ist verstehe ich ja noch und glaube, das man das rekursiv nicht abfangen kann, richtig?

    Bei der Iterativen Form scheint jedoch ein (Denk-)Fehler drin zu stecken, auf den ich einfach nicht selber komme.

    Irgendjemand eine Idee? Danke im voraus 🙂

    0
  • J

    ThaRealMatix schrieb:

    Das die Rekursive Funktion nur Funktioniert wenn a die größere Integer ist verstehe ich ja noch und glaube, das man das rekursiv nicht abfangen kann, richtig?

    Nein. Ruf statt ggtrekursiv(a,a%b) einfach ggtrekursiv(b,a%b) auf.

    Deine iterative Version ist irgendwie etwas merkwürdig. Spiel doch mal die rekursive Variante auf dem Papier durch und schau, ob Du das hinkriegst.

    Mein Anfang würde so aussehen:

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

return a;
    0
  • D

    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

    0
  • T

    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 😢

    0
  • D

    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

    0
  • T

    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 -.-

    0
  • C
    Mod

    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...

    0
  • T

    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 -.-

    0
  • D

    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

    0
  • T
     

    //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 -.-

    0
  • D

    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);
}
    0
  • T

    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

    0
  • C
    Mod

    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);
    0
Anmelden zum Antworten