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

©2026 mgr Jerzy Wałaszek

Duże liczby ciągu Fibonacciego

SPIS TREŚCI

Problem

Oblicz n-tą liczbę ciągu 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:

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

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

Algorytm obliczania dużych liczb ciągu Fibonacciego

Wejście:

n : numer liczby ciągu 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; f0, f1 ∈ 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, ; dwie pierwsze wartości zwracamy bezpośrednio
     to f ← "0" i zakończ
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: ; w pętli liczymy kolejne liczby Fibonacciego
     wykonuj kroki K06…K08
K06:   f = dodaj(f0, f1) ; jako sumę dwóch poprzednich
K07:   f0 ← f1 ; przygotowujemy dwie poprzednie liczby
K08:   f1 ← f ; 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
Python (dodatek)
# Duże liczby ciągu Fibonacciego
# Data: 3.04.2024
# (C)2024 mgr Jerzy Wałaszek
#-------------------------------

# odczytujemy n
n = int(input())
# obliczamy fn
if n < 2:
    f = n
else:
    f0, f1 = 0, 1
    for i in range(n-1):
        f = f0+f1
        f0, f1 = f1, f
# wyświetlamy wynik
print(f)
print()
Wynik: 
2000
42246963333923048787067256023414827825798528402506810980102801373143085843701307
07224123599639141511088446087538909603607640194711643596029271983312598737326253
55580260699158591522949245390499872225679531698287448247299226390183371677806060
70116154978867198798583114688708762645973690867228840236544222952433479644801395
15349562972087652656069529806499841977448720155612802665404554171717881930324025
204312082516817125
JavaScript
<html>
  <head>
    <title>
      BigFibo
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>Duże liczby
          Fibonacciego</b><br/>
          &nbsp;&nbsp;(C)2026 mgr
          Jerzy Wałaszek
          &nbsp;&nbsp;
          <hr>
          n = 
			<input
              type="text"
              name="inp_n"
              size="16"
              value="2000"
              style="text-align:
              right">
          <hr>
          <input
          type="button"
          value="Oblicz"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script language=javascript
        type=text/javascript>
        
// Obliczanie dużych
// liczb Fibonacciego
// Data: 25.10.2012
// (C)2019 mgr Jerzy Wałaszek
//---------------------------

// Oblicza sumę podanych liczb
//----------------------------
function dodaj(x, y)
{
  var z, 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  = x.charCodeAt(--i) +
         y.charCodeAt(--j) +
         p - 96;
    p  = Math.floor(w / 10);
    z = (w % 10)+z;
  }

  while(i)
  {
    w  = x.charCodeAt(--i) +
         p - 48;
    p  = Math.floor(w / 10);
    z = (w % 10) + z;
  }

  while(j)
  {
    w  = y.charCodeAt(--j) + 
         p - 48;
    p  = Math.floor(w / 10);
    z = (w % 10) + z;
  }

  if(p) z = p+z;

  if(z == "") z = "0";

  // zwracamy wynik dodawania
  return z;
}

//********************
//** PROGRAM GŁÓWNY **
//********************

function main()
{
  var f0, f1, f, i, n;

  // odczytujemy n
  n = parseInt(document.frm
               .inp_n.value);

  // obliczamy fn
  if(!isNaN(n) && n>= 0)
  {
    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;
      }
    }

    t = "";
    c = 0;
    for(i = 0;
        i < f.length;
        i++)
    {
      t += f.charAt(i);
      if(++c == 80)
      {
        c = 0;
        t += " <br/> ";
      }
    }
    document.getElementById("out")
    .innerHTML = "<pre> " + t +
                 " </pre>";
  }
  else
    document.getElementById("out")
    .innerHTML = "<span style=" +
                 "'color:Red'>" +
                 "Złe dane!" +
                 "</span>";
}

</script>

  </body>
</html>
Duże liczby Fibonacciego
  (C)2026 mgr Jerzy Wałaszek   
n =
Wynik:
.

do podrozdziału  do strony 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2026 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.