Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Duże liczby Fibonacciego

SPIS TREŚCI

Problem

Oblicz n-tą liczbę Fibonacciego, gdzie n  > 100.

Rozwiązanie

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
f 1 = 1
f 2 = f 0 + f 1
f 3 = f 1 + f 2
...
f n  = f n - 2 + f n - 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

Zmienne pomocnicze:

f 0, f 1  – dwie poprzednie liczby Fibonacciego jako łańcuchy znakowe, f 0, 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

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: f 0 ← "0" ustawiamy dwie początkowe liczby Fibonacciego
K04: f 1 ← "1"  
K05: Dla i  = 2, 3, ..., n :
wykonuj kroki K06...K08
w pętli liczymy kolejne liczby Fibonacciego
K06:     f  = dodaj ( f 0, f 1 ) jako sumę dwóch poprzednich
K07:     f 0f 1 przygotowujemy dwie poprzednie liczby
K08:     f 1f dla następnego obiegu
K09: Zakończ  

Przykładowe programy

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.
C++
// 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
Duże liczby Fibonacciego
(C)2020 mgr Jerzy Wałaszek

n =

.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 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: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.