Duże liczby Fibonacciego


Tematy pokrewne
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
 

Problem

Oblicz 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:

 

f0 = 0
f1 = 1
f2 = f0 + f1
f3 = f1 + f2
...
fn = fn-2 + fn-1

 

Z powyższego wzoru wynika, że program powinien pamiętać dwie ostatnie liczby Fibonacciego, aby policzyć kolejną.

 

Algorytm obliczania dużych liczb Fibonacciego

Wejście:
n    numer liczby Fibonacciego do wyznaczenia, n N
Wyjście:

f - łańcuch znakowy zawierający kolejne cyfry n-tej liczby Fibonacciego

Elementy pomocnicze:
f0, f1  – dwie poprzednie liczby Fibonacciego jako łańcuchy znakowe
i  – zlicza obiegi pętli
dodaj(x,y)  –  dodaje dwie duże liczby jako łańcuchy i zwraca wynik jako łańcuch
Lista kroków:
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 K06...K08 ; w pętli liczymy kolejne liczby Fibonacciego
K06:     f = dodaj(f0,f1) ; jako sumę dwóch poprzednich
K07:     f0f1 ; przygotowujemy dwie poprzednie liczby
K08:     f1f ; dla następnego obiegu
K09: Zakończ  

 

Program

Ważne:

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.

 

Lazarus
// Duże liczby Fibonacciego
// Data: 25.10.2012
// (C)2012 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.
Code::Blocks
// Duże liczby Fibonacciego
// Data: 25.10.2012
// (C)2012 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;
}
Free Basic
' Duże liczby Fibonacciego
' Data: 25.10.2012
' (C)2012 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

 

Duże liczby Fibonacciego
(C)2012 mgr Jerzy Wałaszek

n =

.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.