Rekursion Overflow

[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

[Gast]

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