Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemOblicz n-tą liczbę Fibonacciego, gdzie n > 100. |
Wykorzystując arytmetykę dużych liczb, zadanie jest dosyć łatwe, jeśli n nie jest specjalnie duże. Liczby Fibonacciego obliczamy dynamicznie:
f 0 = 0
f1 = 1
f2
=
f 0 + f 1
f3 =
f1
+
f2
…
fn = f n - 2
+
fn - 1
Z powyższego wzoru wynika, że program powinien pamiętać dwie ostatnie liczby Fibonacciego, aby policzyć kolejną.
n | : | numer liczby Fibonacciego do wyznaczenia, n ∈ N |
f | : | łańcuch znakowy zawierający kolejne cyfry n-tej liczby Fibonacciego |
f0, f1 | : | dwie poprzednie liczby Fibonacciego jako łańcuchy znakowe, f0, f 1 ∈ N |
i | : | zlicza obiegi pętli, i ∈ N |
dodaj (x, y) | : | dodaje dwie duże liczby jako łańcuchy i zwraca wynik jako łańcuch |
K01: | Jeśli n = 0, to f ← "0" i zakończ |
dwie pierwsze wartości zwracamy bezpośrednio |
K02: | Jeśli n = 1, to f ← "1" i zakończ |
|
K03: | f0 ← "0" | ustawiamy dwie początkowe liczby Fibonacciego |
K04: | f1 ← "1" | |
K05: | Dla i = 2, 3, …,
n : wykonuj kroki K06…K08 |
w pętli liczymy kolejne liczby Fibonacciego |
K06: | f = dodaj (f0, f 1) | jako sumę dwóch poprzednich |
K07: | f0 ← f 1 | przygotowujemy dwie poprzednie liczby |
K08: | f1 ← f | dla następnego obiegu |
K09: | Zakończ |
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program odczytuje liczbę n i wylicza n-tą liczbę Fibonacciego. |
Pascal// Duże liczby Fibonacciego // Data: 25.10.2012 // (C)2020 mgr Jerzy Wałaszek //--------------------------------------- program bigfibo; // Oblicza sumę podanych liczb //---------------------------- function dodaj (var x, y : ansistring) : ansistring; var z : ansistring; p, w, i, j, k, n : integer; begin i := length (x); j := length (y); n := i; if j < i then n := j; p := 0; z := ''; for k := 1 to n do begin w := ord (x [i]) + ord (y [j]) + p - 96; dec (i); dec (j); p := w div 10; z := chr ((w mod 10) + 48) + z; end; while i > 0 do begin w := ord (x [i]) + p - 48; dec (i); p := w div 10; z := chr ((w mod 10) + 48) + z; end; while j > 0 do begin w := ord (y [j]) + p - 48; dec (j); p := w div 10; z := chr ((w mod 10) + 48) + z; end; if p > 0 then z := chr (p + 48) + z; if z = '' then z := '0'; dodaj := z; // zwracamy wynik dodawania end; //******************** //** PROGRAM GŁÓWNY ** //******************** var f0, f1, f : ansistring; i, n : dword; begin // odczytujemy n readln(n); // obliczamy fn if n = 0 then f := '0' else if n = 1 then f := '1' else begin f0 := '0'; f1 := '1'; for i := 2 to n do begin f := dodaj (f0, f1); f0 := f1; f1 := f; end; end; // wyświetlamy wynik writeln(f); end. |
// Duże liczby Fibonacciego // Data: 25.10.2012 // (C)2020 mgr Jerzy Wałaszek //--------------------------------------- #include <iostream> #include <string> using namespace std; // Oblicza sumę podanych liczb //---------------------------- string dodaj (string & x, string & y) { string z; int p, w, i, j, k, n; i = x.length(); j = y.length(); n = i; if(j < i) n = j; p = 0; z = ""; for(k = 1; k <= n; k++) { w = (int) (x [--i]) = (int) (y [--j]) + p - 96; p = w / 10; z = (char) ((w % 10) + 48) + z; } while(i) { w = x [--i] + p - 48; p = w / 10; z = (char) ((w % 10) + 48) + z; } while(j) { w = y [--j] + p - 48; p = w / 10; z = (char) ((w % 10) + 48) + z; } if(p) z = (char) (p + 48) + z; if(z == "") z = "0"; return z; // zwracamy wynik dodawania } //******************** //** PROGRAM GŁÓWNY ** //******************** int main() { string f0, f1, f; unsigned int i, n; // odczytujemy n cin >> n; // obliczamy fn if(!n) f = "0"; else if(n == 1) f = "1"; else { f0 = "0"; f1 = "1"; for(i = 2; i <= n; i++) { f = dodaj (f0, f1); f0 = f1; f1 = f; } } // wyświetlamy wynik cout << f << endl; return 0; } |
Basic' Duże liczby Fibonacciego ' Data: 25.10.2012 ' (C)2020 mgr Jerzy Wałaszek '--------------------------------------- ' Oblicza sumę podanych liczb '---------------------------- Function dodaj (ByRef x As String, ByRef y As String) As String Dim As string z Dim As Integer p, w, i, j, k, n i = Len (x) j = Len (y) n = i: If j < i Then n = j p = 0 z = "" For k = 1 To n w = Asc (Mid (x, i, 1)) + Asc (Mid (y, j, 1)) + p - 96 i -= 1: j -= 1 p = w \ 10 z = Chr ((w Mod 10) + 48) + z Next While i > 0 w = Asc (Mid (x, i, 1)) + p - 48 i -= 1 p = w \ 10 z = Chr ((w Mod 10) + 48) + z Wend While j > 0 w = Asc (Mid (y, j, 1)) + p - 48 j -= 1 p = w \ 10 z = Chr ((w Mod 10) + 48) + z Wend If p > 0 Then z = Chr (p + 48) + z If z = "" Then z = "0" dodaj = z End Function '******************** '** PROGRAM GŁÓWNY ** '******************** Dim As String f0, f1, f Dim As UInteger i, n ' odczytujemy n Open Cons For Input As #1 Input #1, n Close #1 ' obliczamy fn If n = 0 Then f = "0" ElseIf n = 1 Then f = "1" Else f0 = "0" f1 = "1" For i = 2 To n f = dodaj (f0, f1) f0 = f1 f1 = f Next End If ' wyświetlamy wynik Print f End |
Wynik: |
2000 42246963333923048787067256023414827825798528402506810980102801373143085843701307 07224123599639141511088446087538909603607640194711643596029271983312598737326253 55580260699158591522949245390499872225679531698287448247299226390183371677806060 70116154978867198798583114688708762645973690867228840236544222952433479644801395 15349562972087652656069529806499841977448720155612802665404554171717881930324025 204312082516817125 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.