Rekursion Overflow

XaTrIxX

Hi!

Ich suche die kleinste Zahl, die durch alle Zahlen von 1-20 teilbar sind.
Folgende Rekursion habe ich.
für die Zahlen von 1-10 gehts noch, aber bei 20 overflowt der Stack.

Denkanstoß ist gefragt.

Code:

// i=10 beim ersten Aufruf

void func(int i)
{

	for(int counter=2; counter<=20; counter++) //counter<=10 geht noch
	{
		if(i%counter!=0)
		func(i+1);
	}

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

Don06

Ich würde das ganze etwas modularer (;)) aufbauen.
Zuerst eine Funktion, die auf Teilbarkeit durch einen Bereich überprüft:

template <unsigned int lower_bound,
		  unsigned int upper_bound>
bool is_divisible_by_range(unsigned int number)
{
	for (unsigned int divisor = lower_bound; 
					  divisor <= upper_bound;
					  ++divisor)
	{
		if (number % divisor != 0)
			return false;
	}

	return true;
}

Dann eine, die die kleinste Zahl sucht, für die diese Bedingung erfüllt ist:

template <unsigned int lower_bound,
		  unsigned int upper_bound>
unsigned int smallest_divisible_by_range()
{
	for (unsigned int i = 1; 
		i <= std::numeric_limits <unsigned int>::max(); ++i)
	{
		if (is_divisible_by_range <lower_bound, upper_bound> (i))
			return i;
	}

	return 0;
}

Das Ergebnis lässt du dir dann anzeigen (;)):

int main()
{
	std::cout << smallest_divisible_by_range <1, 20> () << std::endl;
}

(Achtung, es können noch Fehler im Code sein)

Gruß
Don06

XaTrIxX

ich will was lernen, und keinen fertigen code haben:

also warum bei meinem beispiel overflow?
und was bringts bei dem beispiel modular zu sein?

Don06

XaTrIxX schrieb:

also warum bei meinem beispiel overflow?

Die Frage sollte eher sein: Warum kommt es bei manchen Rekursionen nicht zu einem Stackoverflow? Das liegt daran, dass die Rekursionstiefe noch recht klein ist. Ab wann der Stack nicht mehr ausreicht, ist leider nicht gut festzustellen, sprich man kann nicht einfach wie bei der dynamischen Speicherverwaltung eine Exception vom Typ bad_alloc fangen, das Programm stürzt einfach ab. Wenn du halbwegs weisst, wie Rekursion funktioniert, dürfte dir klar sein, warum Rekursion anfällig für Stackoverflows ist.

XaTrIxX schrieb:

und was bringts bei dem beispiel modular zu sein?

Auch hier ist die Frage etwas undeutlich gestellt. Es bringt natürlich Vorteile. Wiederverwendbarkeit, Wartbarkeit, leicht verständlicher Code (dein Beispielcode hat mich erst etwas verwirrt: eine Funktion mit dem vielsprechenden Namen func, die eine simple Schleife rekursiv implementiert, einen Wert ausgeben soll (laut Beschreibung), aber in jedem Rekursionsdurchlauf einen Wert ausgibt).

Gruß
Don06

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