4. Erste 1000 Stellige Fibonacci Zahl in C

Erste 1000 Stellige Fibonacci Zahl in C

  • L

    Hallo Leute.
    Ich studiere Informatik und habe dieses Semester einen Kurs über c Programmierung begonnen. Wir haben jetzt die Aufgabe bekommen den Index der ersten 1000 Stelligen Fibonacci Zahl zu ermitteln. Ich habe es schon auf verschiedenste Arten versucht, aber mein aktuellster und meiner Meinung nach auch logischster Ansatz ist der hier:

    #define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main()
{
	int prepre[1001];
	int pre[1001];
	int now[1001];
	int temp[1001];

	for(int i = 0; i < 1001; i++) {
		prepre[i] = 0;
		pre[i] = 0;
		now[i] = 0;
		temp[i] = 0;
	}
	prepre[0] = -1;
	pre[0] = -1;
	now[0] = -1;
	
	prepre[1000] = 1;
	pre[1000] = 1;
	now[1000] = 2;
	unsigned long long count = 2;
	int r = 0;

	do {
		count++;
		
		for (int i = 1000; i >= 0; i--) {
			temp[i] = now[i];
			if (prepre[i] + pre[i] + r >= 10) {
				now[i] = (prepre[i] + pre[i]+r) / 10;
				r = (prepre[i] + pre[i]+r) % 10;
			}
			else now[i] = prepre[i] + pre[i];
			prepre[i] = pre[i];
			pre[i] = temp[i];
		}

	} while (now[0] == -1);

	printf("%llu", count);
[Link Text]([Link Adresse]([Link Adresse]([Link Adresse]([Link Adresse]([Link Adresse]([Link Adresse]([Link Adresse]([Link Adresse](Link Adresse)))))))))
	return 0;
}

    Aus irgendeinem Grund kommt am Ende immer 3 heraus, aber ich kann den Fehler nicht mehr finden. Falls ich es unnötig kompliziert mache bitte auch einfach sagen; ich muss es nicht unbedingt genau so machen.
    Danke schon einmal im Voraus und LG.

    0
  • Mod

    Das ist so ja nicht ganz einfach nachzuvollziehen. Daher Vorschlag, der fremden Programmierern beim Lesen, und dir ganz gewaltig beim Programmieren helfen wird:
    Teile das Problem in kleine Funktionen mit genau definierter Aufgabe ein: Einer "Zahl" einen Wert zuweisen. Zwei Zahlen addieren. Eine Zahl einer anderen Zuweisen. Stellen einer Zahl ermitteln. Und gegebenenfalls mehr. So dass am Ende im Hauptprogramm nur die Grundidee steht, wie man die erste Fibonaccizahl mit 1000 Stellen ermittelt, und die ganze Komplexität mit den Arrays in kurze Funktionen ausgelagert ist. So ist das Hauptprogramm gut verständlich, so dass man keine Logikfehler macht. Und die kleinen Einzelfunktionen sind einfach zu programmieren und testen, so dass man keine technischen Fehler bei der Umsetzung macht. Wenn du die Einzelfunktionen wirklich gewissenhaft testest, dann wird es wahrscheinlich auch direkt funktionieren, so dass du gar keine Hilfe mehr brauchst.

    1
    L
     1 Antwort
  • L

    @SeppJ Okay danke. Ich werde morgen mal versuchen das umzusetzten. Der Ansatz mit den Arrays ist aber schon einmal richtig oder?

    0
  • W

    Worum geht es hier eigentlich?

    a) sollst du versuchen, eine eigene BigInt-Implementierung zu erstellen? Dann abstrahiere das in eigene Operationen. Insbesondere scheinst du ja mit int-Arrays die Ziffern nachbilden zu wollen. Abstrahiere die entsprechenden Operationen in Funktionen, also zum Beispiel in eine Funktion bigint_add(a, b), die dir a += b berechnet. Überlege dir auch sinnvolle Typen. Ein Array von int erscheint nicht sinnvoll, wenn jedes Array-Element nur eine Ziffer enthalten soll - dann brauchst du nicht so einen großen Datentyp wie int.

    b) sollst du eine fertige Implementierung von BigInt verwenden? Der schnellste Weg, um zur n-ten Fibonacci-Zahl zu gelangen, geht über das Berechnen von [1110]n\left[\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}\right]^n, siehe auch https://www.youtube.com/watch?v=QIHy8pXbneI&t=2107s (Video ist allerdings für C++ und mit Templates - die generelle Idee passt aber in jeder Sprache). Und dann kannst du schnell ne binäre Suche machen.

    c) Du kannst mit Binets Formel die n-te Zahl direkt berechnen: Fn=(1+52)n−(1−52)n5F_n = \frac{ (\frac{1+\sqrt 5}{2})^n - (\frac{1-\sqrt 5}{2})^n}{\sqrt 5} (hoffe, das passt so...) - und rückwärts kannst du aus einer Zahl dann auch nn bestimmen - wenn du groß genuge Floatingpoint-Operationen hast. Problem: das IEEE double kann nicht mit 1e1000 rechnen. => Du musst also erst den log bilden und nie mit 1e1000 rechnen. Die Näherung (1000 + log(sqrt(5))/log(10)) / log((1+ sqrt(5)) / 2)*log(10) = 4786.6... ist schon fast richtig. Dabei habe ich angenommen, dass der Term (1−52)n≈0(\frac{1-\sqrt 5}{2})^n \approx 0 für große nn.

    d) Irgendeine andere Lösung, die ausnutzt, dass nicht die Fibonaccizahl selbst, sondern nur der Index gesucht wird.

    Du kannst das Ergebnis übrigens leicht mit Wolframalpha testen:
    Log(10, fibonacci(4787)) liefert 1000.07...., wärend bei 4786 nur 999.86... rauskommt.

    1
Anmelden zum Antworten