Liczby fibonacciego w języku C

„Niech N będzie 0. Liczba Fibonacciego dla 0 to:

0

Niech n będzie 1. Liczba Fibonacciego dla 1 to:

1

Niech n będzie 2. Liczba Fibonacciego dla 2 to:

1 + 0 = 1

Niech n będzie 3. Liczba Fibonacciego dla 3 to:

1 + 1 = 2

Niech n będzie 4. Liczba Fibonacciego dla 4 to:

2 + 1 = 3

Niech N będzie 5. Liczba Fibonacciego dla 5 to:

3 + 2 = 5

Niech N będzie 6. Liczba Fibonacciego dla 6 to:

5 + 3 = 8

Niech n będzie 7. Liczba Fibonacciego dla 7 to:

8 + 5 = 13

Niech n będzie 8. Liczba Fibonacciego dla 8 to:

13 + 8 = 21

Niech n będzie 9. Liczba Fibonacciego dla 9 to:

21 + 13 = 34

Poniższa tabela pokazuje pierwsze dwanaście liczb Fibonacciego:

Pierwszy rząd podaje liczby Fibonacci. Drugi rząd podaje indeksy oparte na zerowej dla odpowiedniej tablicy. Indeksy te są różnymi liczbą całkowitych, zaczynając od zera. Z tabeli można zobaczyć, że liczba dziesiąta Fibonacciego wynosi 34 + 21 = 55. Również jedenastka liczba Fibonacciego wynosi 55 + 34 = 89 .

Celem tego artykułu jest wytworzenie liczby Fibonacciego w czasie O (n) i w stałym czasie O (1), przy użyciu języka komputerowego C.

Liczby fibonacciego to liczby całkowite, zaczynając od 0."

Formuła liczby Fibonacciego

Jak widać z powyższej tabeli, obecna liczba Fibonacciego jest sumą poprzednich dwóch liczb. Liczba Fibonacciego dla 0 to 0, a liczba Fibonacciego dla 1 to 1. Te dwa pierwsze liczby, w ich kolejności, muszą zostać zaakceptowane jako takie. Opracowanie następujących liczb Fibonacciego, zacznij odtąd, aby dać 1 + 0 = 1; 1 + 1 = 2; 2 + 1 = 3 itp.

Wzór dla określonej liczby Fibonacciego można podać w trzech liniach lub jednej linii. Wzór w trzech wierszach jest podany w następujący sposób:

Ta formuła jest definicją liczby Fibonacciego.

Wytwarzanie liczb Fibonacciego w czasie O (n)

Więcej niż jedna liczba Fibonacciego może być wyprodukowana od zera dla danej wartości n. W takim przypadku N jest najwyższym wskaźnikiem plus 1 dla tablicy - zakładaj indeksowanie oparte na zero. Produkowana jest liczba Fibonacciego dla i = 0 (i.e 0). Następnie produkowana jest liczba Fibonacciego dla i = 1 (i.mi., 1). Następnie produkowana jest liczba Fibonacciego dla i = 2 (i.mi., 1 ponownie). Następnie produkowana jest liczba Fibonacciego dla I = 3 (i.mi., 2). Następnie produkowana jest liczba Fibonacciego dla i = 4 (i.mi., 3). Trwa to do momentu, gdy wytworzy się liczba Fibonacciego dla podanej liczby (indeks) n, powiedzmy 12, dla najwyższego wskaźnika 11, (89) zostanie wyprodukowany (89).

Program C, który pobiera dane wejściowe z klawiatury i wysyła ją do terminalu (ekranu), zaczyna się od:

#włączać

Dzięki tej dyrektywie przed przetwarzaniem tekst wpisany na klawiaturze pojawi się na ekranie. Wyjście programu pojawi się również na ekranie. Funkcja Fibonacciego to:

void fibonacci (int a [], int n)
if (n> 0)
A [0] = 0;
if (n> 1)
A [1] = 1;
dla (int i = 2; iint NextNo = a [i - 1] + a [i - 2];
A [i] = następny no;

Pierwsze dwa stwierdzenia w funkcji są uważane za dwie operacje. Ciało na pętlę można uznać za jedną operację. Jeśli n wynosi 12, to korpus for-pętla działa 10 razy, ponieważ pierwsza i druga operacja, dla indeksu 0 i indeksu 1, miała już miejsce. Daje to złożoność czasu O (12), napisaną jako O (n).

Zwróć uwagę na stwierdzenie:

int NextNo = a [i - 1] + a [i - 2];

W ciele z powodu pętli. Dodaje dwie poprzednie liczby Fibonacciego, aby uzyskać bieżącą liczbę Fibonacciego (NextNo).

Odpowiednią główną funkcją C dla powyższego programu jest:

int main (int argc, char ** argv)

int n = 12;
int arr [12];
fibonacci (arr, n);
dla (int i = 0; iprintf („%i”, arr [i]);
printf („\ n”);
powrót 0;

Wytwarzanie jednej liczby Fibonacciego w ciągłym czasie

Powyżej indeks liczby Fibonacciego, 89, wynosi 11, a nie 12, dla indeksowania opartego na zerowym. Niech 11 będzie n. W takim przypadku obecna liczba Fibonacciego wynosi 89. Jeśli n wynosi 10, obecna liczba Fibonacciego wynosiłaby 55. Jeśli n wynosi 9, obecna liczba Fibonacci wynosiłaby 34. Trwa to w dół, aż do gdy n wyniesie 0, liczba Fibonacciego wynosi 0.

Istnieje wzór matematyczny do uzyskania bieżącej (jeden) liczby Fibonaccie. Formuła to:

Zauważ, że po prawej stronie równania nie jest to pierwiastek kwadratowy 5, który jest podniesiony do mocy N; jest to wyrażenie w nawiasach podniesionych do mocy n. Istnieją dwa takie wyrażenia.

Więc gdy n wynosi 0, fib_N będzie 0. Kiedy n wynosi 1, fib_N będzie 1. Kiedy n wynosi 2, fib_N będzie 1. Kiedy n wynosi 3, fib_N będzie 2 - i tak dalej.

Ta funkcja matematyczna jest jedną główną operacją i zwraca tylko jedną liczbę Fibonacciego, a nie sekwencję liczb odpowiadających, powiedzmy, wskaźnik 0 do indeksu 11. To jest stały kod czasowy. Nadal można go użyć do tworzenia sekwencji liczb Fibonaccie.

Złożoność czasu tej funkcji matematycznej w celu wytworzenia jednej liczby Fibonacciego jest O (1), stały czas.

Teraz ta funkcja matematyczna jest kodowana poniżej, aby wytworzyć 12 liczb Fibonacciego. Wykorzystałby mniej ogólny czas niż poprzedni algorytm.

Kod tej funkcji matematycznej do wytworzenia jednego numeru Fibonacciego jest:

#włączać
#włączać
Double Fibno (int n)
podwójne fibn = (pow (1+sqrt (5))/2, n) - pow ((1 -SQRT (5))/2, n))/sqrt (5);
powrót fibn;

Zauważ, że matematyka.W tym czasie uwzględniono bibliotekę H, która wnosi do programu do programu predefiniowane funkcje Power (Pow) i kwadratowe (SQRT). Funkcja wytwarza tylko jedną liczbę Fibonacciego, a nie ich sekwencję. Odpowiednią główną funkcją tego kodu jest:

int main (int argc, char ** argv)

int n = 11;
podwójne fibn = fibno (n);
printf („%lf \ n”, fibn);
powrót 0;

Z indeksem 11, wyjście wynosi 89.000000. Jednak, aby uruchomić ten program z kompilatorem GCC, użyj wiersza poleceń, takich jak:

GCC TEMP.c -o temp -lm

gdzie „temp.C ”jest kodem źródłowym, a„ Temp ”to opracowany program. Zwróć uwagę na użycie przełącznika, „-LM”, gdzie „L” to małe litery L.

Wniosek

Pierwszy numer Fibonacciego to 0. Druga liczba Fibonacciego to 1. Reszta otrzymuje się przez dodanie dwóch poprzednich liczb Fibonacciego. Liczby fibonacciego to liczby całkowite. Aby uzyskać sekwencję liczb fibonacciego od zera w czasie O (n), użyj funkcji z instrukcją takim:

int NextNo = a [i - 1] + a [i - 2];

gdzie następny nie jest bieżącą liczbą indeksu I, a „a” jest tablicą do przechowywania numerów sekwencji Fibonacciego. Pierwsze dwie liczby, 0 i 1, są produkowane niezależnie.

Aby uzyskać tylko jedną liczbę Fibonacciego w O (1) czas, użyj wzoru matematyki:

gdzie n jest indeksem opartym na zerowym.

Liczby fibonacciego można uzyskać za pomocą macierzy matematycznej. Jest to jednak dyskusja od jakiegoś czasu.