Rekursion Overflow

otze

erstmal fidne ichs schön, dass jemand selsbt denken will

die antwort auf deine Frage ist: die kleinste zahl die durch die zahlen 1-20 teilbar ist, ist die zahl 2*3*5*7*11*13*17*19=9699690 und genau der Wert ist deine Rekursionstiefe. bissl viel, oder?

nebenbei hat dein algo ein Problem: er wird ewig rechnen. wenn nicht sogar länger.

Du terminierst die Schleife nicht, wenn du die Funktion aufgerufen hast. das kannst du aber, denn selbst wenn die nächsten Schleifendurchläufe richtig sind, die zahl ist sicher nicht die gesuchte. Also werden in jeder deiner Funktionen bis zu 20 folge funktionen aufgerufen. also îm worst case irgendwas um20^9699690 funktionen die aufgerufen werden. Das ding wird niemals fertig gerechnet haben

@Don06 was meinste, wird jemand der mit rekursion noch nicht zurechtkommt, mit templates fertigwerden? Nebenebi machst du aus einem einfachen 5 Zeiler(geschätzt) ne recht komplizierte sache. Ob das zur wiederverwendbarkeit beiträgt?

Don06

otze schrieb:

die antwort auf deine Frage ist: die kleinste zahl die durch die zahlen 1-20 teilbar ist, ist die zahl 2*3*5*7*11*13*17*19=9699690

Nicht ganz, versuch mal die Zahl durch 4, 8, 16 oder 9 zu teilen

Laut meinem Algo ist die Zahl 2^4*32*5*7*11*13*17*19 = 232792560

Gruß
Don06

camper

@otze: 5*7*9*11*13*16*17*19=232792560
An der Argumentation ändert das natürlich nichts.

XaTrIxX

tatsächlich, sie rechnet wirklich ewig.
Dickes, dickes Sorry an der Stelle, wie kann man nur so einen Anfängerfehler einbauen?

Nun. ich glaub das beste wär wohl gleich einen anderen Ansatz haben oder?

Alle primzahlen von 1-20 miteinander rausfinden und miteinander multiplizieren.
Könnte passen, oder?

Danke für die Erklärung wegen des Stacks. Klare Sache jetzt.

otze

camper schrieb:

@otze: 5*7*9*11*13*16*17*19=232792560
An der Argumentation ändert das natürlich nichts.

ich bin meine Punkte in HöMa nicht wert

Jester

otze schrieb:

camper schrieb:

@otze: 5*7*9*11*13*16*17*19=232792560
An der Argumentation ändert das natürlich nichts.

ich bin meine Punkte in HöMa nicht wert

macht nix, campers rechnung stimmt auch nicht.
Die Zahl mag ja richtig sein, aber das produkt links enthält nur ungerade zahlen... da kann das ergebnis nicht gerade sein.

muffmolch

bringt hier zwar nicht allzu viel, aber bei rekursiven funktionen sollte man immer drauf achten die lokalen variablen grössentechnsch zu minimieren:

void func(const int& i) 
{ 
    for(short counter=2; counter<=20; counter++) 
        if(i%counter!=0) func(i+1); 

    cout << "die zahl lautet " << i; 
}

damit kommst du bestimmt bis 11

camper

Jester schrieb:

otze schrieb:

camper schrieb:

@otze: 5*7*9*11*13*16*17*19=232792560
An der Argumentation ändert das natürlich nichts.

ich bin meine Punkte in HöMa nicht wert

macht nix, campers rechnung stimmt auch nicht.
Die Zahl mag ja richtig sein, aber das produkt links enthält nur ungerade zahlen... da kann das ergebnis nicht gerade sein.

16 ist bei mir ziemlich gerade

Michael E.

projecteuler.com ?

Kleiner Tipp für die Verallgemeinerung: Die kleinste Zahl, die durch 1 bis n teilbar ist, ist ggt(ggt(...ggt(n-2, ggt(n-1, n))...).

life

Michael E. schrieb:

projecteuler.com ?

Kleiner Tipp für die Verallgemeinerung: Die kleinste Zahl, die durch 1 bis n teilbar ist, ist ggt(ggt(...ggt(n-2, ggt(n-1, n))...).

hm.. sowas hab ich schon mal implementiert als ich die varargs in Java ausprobieren wollte

Bekomme das gleiche Ergebnis wie Don06 für n = 20. Hier der Quellcode (Java):

public class KGVTest {
	public static boolean isEven(int a) {
		return (a & 1) == 0;
	}

	public static int computeGGT(int param) {
		return param;
	}

	public static int computeGGT(int a, int b) {
		int k = 0;
		while (isEven(a) && isEven(b)) {
			a >>= 1;
			b >>= 1;
			++k;
		}
		int t;
		if (!isEven(a)) {
			t = -b;
		} else {
			t = a;
		}
		while (t != 0) {
			while (isEven(t)) {
				t >>= 1;
			}
			if (t > 0) {
				a = t;
			} else {
				b = -t;
			}
			t = a - b;
		}
		return a << k;
	}

	public static int computeGGT(int... params) {
		int ggt = computeGGT(params[0], params[1]);
		for(int i = 2; i < params.length; i++) {
			ggt = computeGGT(ggt, params[i]);
		}
		return ggt;		
	}

	public static int computeKGV(int param) {
		return param;
	}

	public static int computeKGV(int a, int b) {
		return (a/computeGGT(a, b))*b;
	}

	public static int computeKGV(int... params) {
		int kgv = computeKGV(params[0], params[1]);
		for(int i = 2; i < params.length; i++) {
			kgv = computeKGV(kgv, params[i]);
		}
		return kgv;		
	}

	public static void main(String[] args) {
		int[] params = new int[20];
		for(int i = 0; i < params.length; i++) {
			params[i] = i+1;
		}
		System.out.println(computeKGV(params));		
	}	
}

edit: nochmal bissel optimiert

Bruteforce kommt auf campers Zahl:

unsigned int z = 20;
 unsigned int n = 1;

 while (1) {

  if ((z % n) != 0) {
   n = 0; z += 20;
  }

  n += 1; if (n > 20) { break; }
 }