Abgewandelte Fibonacci Reihe

[Ulfmann]

Hallo,

ich verzweifel hier an einer Übungsaufgabe. Die Fibonacci Reihe wird wohl bekannt sein, zur Sicherheit hier das Basisbeispiel:

Angenommen, ein weibliches Kaninchen ist 2 Monate nach der Geburt fruchtbar und wirft dann jeden Monat genau ein neues, weibliches Kaninchen-Baby. Wenn mit einem Weibchen begonnen wird, sind es wie viele Weibchen nach 10 Monaten? Man geht davon aus, dass es ausreichend männliche Kaninchen gibt um die maximale "Produktion" zu gewährleisten und kein Hase stirbt.

Damit kommt man ja schnell auf die Reihe 1,1,2,3,5,8,13,21,34,55 und das n-te Glied kann mit fib(n) = fib(n-1) + fib(n-2) definiert werden.

Soweit, so gut. Nun - und da komm ich zu meinem Problem - sterben die Weibchen nach 4 Monaten. Es gilt also, eine Sterberate zu berücksichtigen. Mein erster Ansatz war fib(n) = fib(n-1) + fib(n-2) - fib(n-3) aber das kann nicht hinhauen.

Das Ganze ist eine Übungsaufgabe zur Rekursion in Java. Da die Formulierung in Quelltext trivial ist, sobald man die Algorithmus gerafft hat, lass ich das auch erstmal weg.

Ich bedanke mich für jede hilfreiche Idee.

Gruß.

[dark-man]

Hallo,

meine Ausbildung ist schon etwas her.

aber was du bei der Fibonacci-folge bedenken musst ist, dass die Werte fuer f0=0 und fuer f1=1 festgelegt sind und nicht berechnet werden.

deine Formel gilt nur fuer n >=2.

Quelle:

Fibonacci-Folge ? Wikipedia

Wenn du in deiner abgewandelten reihe fuer f0=0, f1=0(oder f1=1) und f2=1 einsetzt, funktioniert deine reihe fuer n>=3.

gruss

Dark-man

[Ulfmann]

Hi,

ja, das sind ja die Base Cases, bzw. die Abbruchbedingungen. Die Hürde, oder die beiden Fragen, an denen ich mit meinem Ansatz nicht weiter kam, ist (1) stirbt ein Weibchen im 4. Monat oder im darauffolgenden? und (2) da in den ersten beiden Monate ja jeweils nur ein Weibchen vorhanden ist, wird es dann in Monat 4 und 5 bzw. 5 und 6 zweimal als "gestorben" gezählt oder dann abgezogen? Ich weiß, ich mach es sicherlich komplizierter als es ist, aber mein neuer Ansatz ging dann in die richtung:

n = (n-1) + (n-2) - (zuwachs von (n-3))

Das stimmte auch mit meinen Skizzen und Nebenrechnungen überein.

Nach etwas googeln und weiterer Hilfe hab ich dann ein ähnliches Beispiel gefunden, sodass die Lösung ziemlich sicher Folgendes ist:

public int fib(int n)

{

	if (n <= 0)

		return 0;


	if (n == 1)

		return 1;


	if (n == 2)

		return 1;


	else

	{

		return fib(n-1) + fib(n-2) - fib(n-5);

	}

}

[Klotzkopp]

Die Hürde, oder die beiden Fragen, an denen ich mit meinem Ansatz nicht weiter kam, ist (1) stirbt ein Weibchen im 4. Monat oder im darauffolgenden?

Es stirbt am Ende des 4. Monats, d.h. es bekommt nur zweimal Nachwuchs: Im 3. und im 4. Monat.

[MidnightRun]

Hey,

hab mal grad das schnell nachprogrammiert, also nicht den Algorithmus sonder, das Verhalten der Hasen.

Habe eine Hasen Klasse erstellt, die nur ein Alter festhält, was im Konstruktor auf 0 gestellt wird.

Ausserdem gibt es meine Methode "Laufen" diese zählt das Alter einmal hoch. Überprüft ob das Alter nicht über 4 ist, sonst weg =D Wenn der Hase älter als 2 ist kann er Kinder kriegen.

Ich habe alle Hasen in einer List<> die im Formular instantieert wird.

Meine Ausgabe ist folgende :

Ausgabe

Müsste eigentlich stimmen, soweit =D Frage ja nicht allzuviel ab.

Mfg

Edit ;

Sehe grad das es Fehlerhaft ist -.- Da ich meine List durch laufe mit einer for schleifer, aber in dieser auch Hasen hinzufügen funzt es nicht so =(

:bimei

so ist es richtig :

Richtig

Bearbeitet 15. April 2009 von MidnightRun

[Ulfmann]

Cool, aber - nur damit ich das richtig verstehe - das bezieht sich jetzt nich 100%ig auf mein konretes Beispiel oder ? Weil dann haut meine Lösung wieder nicht hin.

Kannst du zur Not mal Quelltext dazu posten?

[MidnightRun]

Also ich habe einfach nur mal deine Aufgabenstellung nach Programmiert. Sprich 1 Hase, nach 2 Monaten kriegt er ein Kind, nach dem 4 stirbt es.

Habe eben ein Formular gemacht, mit einer Collection ( List<>), dieses nimmt Instanzen der Klasse Hase an.

Hase hat ein Feld, Alter. Und Hase hat eine Methoder Laufen(), Laufen Zählt das Alter um 1 hoch und überprüft dann, ob es stirbt oder ein Kind kriegt, kriegt es ein Kind wird der Formular Liste ein neues Hasen Objekt zugefügt, wenn es stirbt eben dieses aus der Liste entfernt.

Das Formular hatte auch ne Timer, weil ich das Tick Event mit einem Event Handler verbunden hatte um die Laufen Methoden, der Hasen zu durchlaufen =D

Sprich ich wollte nur sehen, wei die Reihenfolge sein muss. Rekursion ist für mich immer noch ein Buch mit 7 Siegeln =D

Mfg

[Ulfmann]

Entschuldige, wenn ich Dich missverstehe, aber deine Ausgabe kann nich richtig sein. Du hast im 2. Monat z.B. nicht 2 Hasen, sondern erst den einen - der sich nicht vermehren konnte, da noch nicht fruchtbar. Wie Klotzkopp schon richtig bemerkte, kriegt ein Hase nur im 3. und 4. Monat Nachwuchs. An anderen Stellen (ab dem 6. Monat aufwärts eigentlich) zweifel ich deine Werte auch stark an.

Wie würde deine Ausgabe denn aussehen, wenn du das Sterben nicht berücksichtigst oder anders - davon ausgehst, dass kein Hase stirbt?

[DominikJ]

So Siehts bei mir aus:

Ohne Versterben

Hasen gestartet! Lasst sie rammeln wie die Karnickel  

Monat 0: Zuwachs: 0 Gesamt: 1

Monat 1: Zuwachs: 0 Gesamt: 1

Monat 2: Zuwachs: 1 Gesamt: 2

Monat 3: Zuwachs: 1 Gesamt: 3

Monat 4: Zuwachs: 2 Gesamt: 5

Monat 5: Zuwachs: 3 Gesamt: 8

Monat 6: Zuwachs: 5 Gesamt: 13

Monat 7: Zuwachs: 8 Gesamt: 21

Monat 8: Zuwachs: 13 Gesamt: 34

Monat 9: Zuwachs: 21 Gesamt: 55

Monat 10: Zuwachs: 34 Gesamt: 89

Monat 11: Zuwachs: 55 Gesamt: 144

Monat 12: Zuwachs: 89 Gesamt: 233

Monat 13: Zuwachs: 144 Gesamt: 377

Monat 14: Zuwachs: 233 Gesamt: 610

Monat 15: Zuwachs: 377 Gesamt: 987

Monat 16: Zuwachs: 610 Gesamt: 1597

Monat 17: Zuwachs: 987 Gesamt: 2584

Monat 18: Zuwachs: 1597 Gesamt: 4181

Monat 19: Zuwachs: 2584 Gesamt: 6765

Monat 20: Zuwachs: 4181 Gesamt: 10946

Monat 21: Zuwachs: 6765 Gesamt: 17711

Monat 22: Zuwachs: 10946 Gesamt: 28657

Monat 23: Zuwachs: 17711 Gesamt: 46368

Monat 24: Zuwachs: 28657 Gesamt: 75025[/code]




Mit Absterben:

[code]Hasen gestartet! Lasst sie rammeln wie die Karnickel Monat 0: Zuwachs: 0 Verstorben: 0 Gesamt: 1 Monat 1: Zuwachs: 1 Verstorben: 0 Gesamt: 2 Monat 2: Zuwachs: 1 Verstorben: 0 Gesamt: 3 Monat 3: Zuwachs: 1 Verstorben: 1 Gesamt: 4 Monat 4: Zuwachs: 2 Verstorben: 1 Gesamt: 6 Monat 5: Zuwachs: 2 Verstorben: 2 Gesamt: 8 Monat 6: Zuwachs: 3 Verstorben: 3 Gesamt: 11 Monat 7: Zuwachs: 4 Verstorben: 4 Gesamt: 15 Monat 8: Zuwachs: 5 Verstorben: 6 Gesamt: 20 Monat 9: Zuwachs: 7 Verstorben: 8 Gesamt: 27 Monat 10: Zuwachs: 9 Verstorben: 11 Gesamt: 36 Monat 11: Zuwachs: 12 Verstorben: 15 Gesamt: 48 Monat 12: Zuwachs: 16 Verstorben: 20 Gesamt: 64 Monat 13: Zuwachs: 21 Verstorben: 27 Gesamt: 85 Monat 14: Zuwachs: 28 Verstorben: 36 Gesamt: 113 Monat 15: Zuwachs: 37 Verstorben: 48 Gesamt: 150 Monat 16: Zuwachs: 49 Verstorben: 64 Gesamt: 199 Monat 17: Zuwachs: 65 Verstorben: 85 Gesamt: 264 Monat 18: Zuwachs: 86 Verstorben: 113 Gesamt: 350 Monat 19: Zuwachs: 114 Verstorben: 150 Gesamt: 464 Monat 20: Zuwachs: 151 Verstorben: 199 Gesamt: 615 Monat 21: Zuwachs: 200 Verstorben: 264 Gesamt: 815 Monat 22: Zuwachs: 265 Verstorben: 350 Gesamt: 1080 Monat 23: Zuwachs: 351 Verstorben: 464 Gesamt: 1431 Monat 24: Zuwachs: 465 Verstorben: 615 Gesamt: 1896

Mit Java

Bearbeitet 15. April 2009 von DominikJ

[Gooose]

       private int fib(int anz)

        {

            return anz > 1 ? fib(anz - 1) + fib(anz - 2) : anz;

        }

[Ulfmann]

Es freut mich ja, dass Ihr Euch so hierdran beteiligt, obwohl ich schon ziemlich genervt von dieser Aufgabe bin.

@ DominikJ: Ich will partout nicht kapieren, wieso du in Monat 1 schon Zuwachs hast. Der Hase braucht doch 2 Monate um fruchtbar zu werden und erst dann gibts Kinder, sprich in Monat 3 und 4. Als Folge daraus dürfte (bei dir) in Monat 4 auch kein Hase sterben, weil ja keiner im 2. Monat geboren wurde.

Also entweder lieg ich falsch und eure Variante passt so, oder meine Einwände stimmen und Euer Algorithmus damit nicht.

[DominikJ]

Also ich habe halt Kaninchen Population von wikipedia genommen...

Fibonacci-Folge ? Wikipedia

Dort steht im zweiten Lebensmonat. D.h. Geburt = 1. Lebensmonat.

Aber ist doch auch nicht so wild... stell doch meiner Ausgabe ein

Monat -1: Zuwachs: 0 Gesamt: 1

voran und schon stimmt es wieder

Ich füge die Hasen auch schon im ersten Lebensmonat hinzu ...

Ist also ne Verständnisfrage.

MasterHase 'initialisiert' (1 Monat alt) -> Monat vergeht (2 Monate alt) -> Monat vergeht (3 Monate alt) -> geschlechtsreif -> rammelt -> neuer Hase -> Monat vergeht (4 Monate alt) -> rammelt -> neuer Hase -> Monat vergeht -> Tod!

Edit: Ach die Differenzen zwischen der Ausgbae mit und ohne versterben, liegen daran, das ich im nachhinein das alles nochmal bissl weiter und anders aufgebaut hatte.

@ Goose: Das ist ja der Algo für die Standard Folge

[Ulfmann]

Ok, mit der Begründung kann ich leben. Nichtsdestotrotz seh ich es anders - wie du schon sagst, das ist tatsächlich ne Verständnisfrage und ich habs anders aufgefasst.

Wenn ich dran denk, werd ich die Aufgabe demnächst meinem AS-Lehrer ma auf den Tisch packen, mal sehen was der meint.

Bis dahin genießt die Sonne :cool:

[AndiE]

Hallo,

ich habe diese Folge:

1,

1,2,3,3,5,

6(5+1),8(6+2),11(8+3),14(11+3),19(14+5)

...

Die Folge müßte so weitergehen:

25(19+6),33(25+8),44(33+11),58(44+14),77(58+19)

[SoL_Psycho]

Monat 0: Zuwachs: 0 Verstorben: 0 Gesamt: 1

Monat 1: Zuwachs: 1 Verstorben: 0 Gesamt: 2

Monat 2: Zuwachs: 1 Verstorben: 0 Gesamt: 3

Monat 3: Zuwachs: 1 Verstorben: 1 Gesamt: 4

Monat 4: Zuwachs: 2 Verstorben: 1 Gesamt: 6

Wenn die Hasen nach 4 Monaten sterben, dann stirbt dein "Initialhase" nach Monat 3 (0,1,2,3). Welcher Hase stirbt dann nach Monat 4? Da stirbt keiner, wenn ich nicht grad nen Brett vorm Kopf habe

[Ulfmann]

Wenn die Hasen nach 4 Monaten sterben, dann stirbt dein "Initialhase" nach Monat 3 (0,1,2,3). Welcher Hase stirbt dann nach Monat 4? Da stirbt keiner, wenn ich nicht grad nen Brett vorm Kopf habe

Endlich jemand meiner Meinung. Das hab ich auch schon versucht, dem Herrn zu erklären :-) Wir haben uns darauf geeinigt, dass es in erster Linie eine Verständnisfrage ist. In meinen Augen gibt es aber auch keinen Nachwuchs in Monat 1 (bzw. im 2. Monat). Denn wenn ein Hase 2 Monate braucht, um fruchtbar zu werden, kann es definitiv erst in Monat 3 Nachwuchs geben. Aber das hatten wir alles schon ...

Nächste Woche is wieder Berufsschule, mal gucken was mein Lehrer meint. Im Übrigen schreiben wir Montag auch ne Klausur über (u.A.) Rekursion, ich krieg die Krise wenn sowas rankommt!

[DominikJ]

Ohhh,

nee da hast du auch recht.

Ich dachte wir haben über was anderes geschrieben

Aber fällt mir erst jetzt auf, das in 2 aufeinander folgenden Monaten Hasen sterben.^^

Evtl. so:

Monat 0: Zuwachs: 0 Verstorben: 0 Gesamt: 1

Monat 1: Zuwachs: 0 Verstorben: 0 Gesamt: 1

Monat 2: Zuwachs: 1 Verstorben: 0 Gesamt: 2

Monat 3: Zuwachs: 1 Verstorben: 0 Gesamt: 3

Monat 4: Zuwachs: 1 Verstorben: 1 Gesamt: 4

Monat 5: Zuwachs: 2 Verstorben: 0 Gesamt: 6

Monat 6: Zuwachs: 2 Verstorben: 1 Gesamt: 8

Monat 7: Zuwachs: 3 Verstorben: 1 Gesamt: 11

Monat 8: Zuwachs: 4 Verstorben: 1 Gesamt: 15

Monat 9: Zuwachs: 5 Verstorben: 2 Gesamt: 20

Monat 10: Zuwachs: 7 Verstorben: 2 Gesamt: 27

Monat 11: Zuwachs: 9 Verstorben: 3 Gesamt: 36

Monat 12: Zuwachs: 12 Verstorben: 4 Gesamt: 48

Monat 13: Zuwachs: 16 Verstorben: 5 Gesamt: 64

Monat 14: Zuwachs: 21 Verstorben: 7 Gesamt: 85

Monat 15: Zuwachs: 28 Verstorben: 9 Gesamt: 113

Monat 16: Zuwachs: 37 Verstorben: 12 Gesamt: 150

Monat 17: Zuwachs: 49 Verstorben: 16 Gesamt: 199

Monat 18: Zuwachs: 65 Verstorben: 21 Gesamt: 264

Monat 19: Zuwachs: 86 Verstorben: 28 Gesamt: 350

Monat 20: Zuwachs: 114 Verstorben: 37 Gesamt: 464

Monat 21: Zuwachs: 151 Verstorben: 49 Gesamt: 615

Monat 22: Zuwachs: 200 Verstorben: 65 Gesamt: 815

Monat 23: Zuwachs: 265 Verstorben: 86 Gesamt: 1080

Monat 24: Zuwachs: 351 Verstorben: 114 Gesamt: 1431

Fehler war, dass ich den Hasen hab sterben lassen aber er nicht gelöscht wurde

Bearbeitet 23. April 2009 von DominikJ

[Ulfmann]

Was tot ist, muss auch weggeräumt werden. Das riecht doch sonst.

Aber mich würd mal interessieren, wie ist denn nun dein Algorithmus für die Gesamtanzahl der Hasen im n-ten Monat?

[DominikJ]

Was tot ist, muss auch weggeräumt werden. Das riecht doch sonst.

Ja, das ist mir auch aufgefallen das mein Rechner plötzlich nach Verwesung roch... Musste erstmal den Garbage Collector laufen lassen

Aber mich würd mal interessieren, wie ist denn nun dein Algorithmus für die Gesamtanzahl der Hasen im n-ten Monat?

Nuja, ist nun kein wirklicher Algo... War ja eigentlich auch erstmal nur dafür gedacht, zu testen wie es denn sein muss ... Das sich dies als so 'langwierig' ist hätte ich nicht gedacht ...

Aber trotzdem hier mal mein Code:

import java.util.LinkedList;



public class Hase {


	private LinkedList<Integer> familie = new LinkedList<Integer>();


	public static void main(String[] args) {

		System.out.println("Hasen gestartet!");

		@SuppressWarnings("unused")

		Hase h = new Hase(24);

	}


	public Hase(int monate) {

		int alter, curCount, died, count = 1;

		familie.add(0);

		for (int i = 0; i <= monate; i++) {

			curCount = 0;

			died = 0;

			System.out.print("Monat " + i + ": ");

			for (int j = familie.size() - 1; j >= 0; j--) {

				alter = familie.get(j) + 1;

				if (alter == 5) {

					/* Hier war der Fehler */

					familie.remove(j);

					died++;

				}

				if (alter <= 4) {

					familie.set(j, alter);

					if (alter == 3 || alter == 4) {

						familie.add(1);

						curCount++;

					}

				}

			}

			count += curCount;

			System.out.println("Zuwachs: " + curCount + " Verstorben: " + died + " Gesamt: " + count);

		}

	}

}