Fibonacci Zahlen

[criminal]

Hallo an alle,

habe eine Frage und komme echt nicht zurecht:

ich muss Fibonacci Zahlen berechnen, anfangs klein und später größer


Habe folgenden Code gefunden und genutzt

Zahl fib()
	{
		StringBuilder rueckgabe = new StringBuilder();
		int zahl = Integer.parseInt(umwandlung);
		
		int a = 0;
		int b = 1;
		int c = 1;
		for(int i = 0; i < zahl; i++) 
		{
			c = a + b;
			a = b;
			b = c;
		}
		rueckgabe.insert(0, c);
		return new GrosseZahl(rueckgabe.toString());
	}

meine Frage ist jetzt:

Das klappt eigentlich hervorragend, aber z.B. bei der zahl 100 erwartet das Testprogramm: 573147844013817084101


wo liegt jetzt mein Fehler??

Es geht nur um die Berechung.


Danke im vorraus

 

[AquaBall]

Da Problem ist, dass nicht nur die Rückgabe eine "großeZahl" werden kann, sondern schon viel früher die Berechnungsvariablen a,b,c.

Schon bei 24 kommst du über die Short-Grenze. Und dann geht's weiter exponentiell . Das würde ein wenig Probieren bei der Fehlersuche schon ergeben.

Die musst du auch als große Zahl führen.

 

[Kevin94]

Du verwendest int zum berechnen. Die größte von einem int repräsentierbare Zahl ist 2^31-1=2 147 483 647 und das ist deutlich kleiner als dein erwarteter Wert, du must also intern (und wahrscheinlich auch in GrosseZahl) einen größeren Datentyp nehmen, z.B. long (das reicht gerade noch, wenn ich mich nicht verzählt habe) oder eben BigInteger.

 

[criminal]

Problem ist BigInteger ist durch die Aufgabe verboten und die nächste Zahl wäre noch größer deshalb fällt long auch flach.

Gut, dann habe ich also schon viel früher ein Problem, mist

 

[AquaBall]

Vielleicht ist das der Sinn der Aufgabe, dass du eine StringAdditions-Algorithmus programmierst.
Ist ganz interessant, und gar nicht so schwer. (wenn du nicht totaler Anfänger bist)

 

[Kevin94]

Du könntest double nehmen, dann ist das Ergebnis aber nichtmehr genau. Die einzige andere Alternative, wenn BigInteger und andere Klassen aus anderen Bibliotheken verboten sind, sich diese selbst zu Programmieren. Da du nur Addition brauchst, wird das nicht ganzsoviel Aufwand, kannst ja mal schauen wie BigInteger intern seine Daten speichert.

[EDIT]Das mit dem speichern als String und dann sozusagen "schriftliche Addition" nachzuprogrammieren wäre mir jetzt als worst-case für eine Selbstimplementation auch einefallen, wollte das aber nicht mit ins Gespräch bringen.[/EDIT]

 

[criminal]

Danke für den Tip, werde ich mir mal anschauen

 

[AquaBall]

Du könntest double nehmen, dann ist das Ergebnis aber nichtmehr genau.

FibonacciZahlen die

nichtmehr genau

sind, sind halt nicht sehr prickelnd.
Außerdem ist hier auch hier nur eine Frage der Zeit bis die Grenzen erreicht sind.

Ich habs nun mal (spaßhalber) ausprogrammiert.
Mein Ergebnis für 1000. Fibonacci hat 207 Stellen:
35341000917875257533994483352045906828494504635815
49776041091752538906966342713601215835661100647255
10836075851584985143412396868586425109102723291106
57061875007539271063332172999210674332164028135679
4177320

Damit du's nicht einfach 1zu1 kopierst hab ich im Code 2-3 Fehler eingebaut!

public class StringAdd {
	public static void main(String[] args) {
		StringAdd sa=new StringAdd();
		String a="1";
		String b="1";
		for (int i=0 ;i<1000; i++) {
			String c= sa.stringAdd(a,b);
			b=c;
		}
		System.out.println("1000. Fibonacci hat "+b.length()+" Stellen:");
		System.out.println(b);
	}
	
	String stringAdd(String a, String b) {
		int maxA =a.length();
		int maxB =b.length();
		String neu="", ausgleich="";
		
		// Sicherstellen, dass Zahlen gleich lang sind
		int diff=Math.abs(maxA-maxB);
		for ( ; diff>0; diff--) {	// Füllstring erzeugen
			ausgleich += "0";
		}
		
		if (maxA>maxB) {		// Strings gleich lang machen
			b=ausgleich+b;
		} else {
			a=ausgleich+a;
			maxA =a.length();
		}
		
		int uebertrag=0;
		for (int idx=maxA-1; idx>=0; idx--){
			int zifferA=a.charAt(idx)-'0';
			int zifferB=b.charAt(idx)-'0';
			int pos=zifferA+zifferB + uebertrag;
			uebertrag=0;
			if (pos>9) {
				pos+=10;
				uebertrag=1;
			}
			neu = pos+neu;
		}
		if (uebertrag>0) {
			neu = "1"+neu;
		}
		return neu;
	}
}