Liczby Leonardo

Definicja

Liczby Leonardo powstają poprzez wyliczanie kolejnych wyrazów ze wzoru rekurencyjnego. Dwa początkowe wyrazy to 1, 1, a każdy kolejny to suma dwóch poprzednich powiększona o 1. Wzór matematyczny wygląda następująco:

Ciąg liczb

Liczby Leonardo tworzą następujący ciąg: 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, ..

Analiza

Jak można zauważyć ciąg Leonardo jest bardzo podobny do ciągu Fibonnaciego. Oznacza to, że kody do generowania obu ciągów będą bardzo podobne i różnić się będą jedynie powiększeniem sumy dwóch poprzednich wyrazów o 1. Podczas wyliczania wielu wyrazów ciągu należy pamiętać, że nie należy wyliczać każdego elementu oddzielnie, ponieważ rekurencja bardzo szybko zwiększa złożoność algorytmu!

Implementacja

n-ty wyraz

Funkcja Leonardo() ma za zadanie wyliczyć n-ty wyraz ciągu. Oto przykładowa funkcja:

1. int Leonardo(int n) {
2.   if (n <= 2)
3.     return 1;
4.   int a = 1;
5.   int b = 1;
6.   while (n-- > 2) {
7.     int c = a + b + 1;
8.     a = b;
9.     b = c;
10.   }
11.   return b;
12. }

W funkcji dla n mniejszego, równego 2 zwracana jest wartość 1. Dla wyrazów o większym indeksie wyliczana jest w pętli wartość kolejnego wyrazu. Warto zauważyć, że podany algorytm iteracyjny wylicza żądany wyraz w czasie liniowym O(n).

k pierwszy wartości

Zastosowanie poprzednio napisanej funkcji Leonardo() w celu wypisania kolejnych k wyrazów ciągu Leonardo jest możliwe przy użyciu pętli, ale nie będzie to rozwiązanie efektywne rzędu O(n²). Warto jednak zauważyć, że poprzedni algorytm wyszukuje wszystkie liczby Leonardo, aż do n, więc można je pomiędzy kolejnymi obliczeniami zapisywać na listę:

1. vector<int> tablicaLeonardo(int k) {
2.   vector<int> lista;
3.   if (k >= 1) lista.push_back(1);
4.   if (k >= 2) lista.push_back(1);
5.   int a = 1;
6.   int b = 1;
7.   while (k-- > 2) {
8.     int c = a + b + 1;
9.     a = b;
10.     b = c;
11.     lista.push_back(c);
12.   }
13.   return lista;
14. }

Funkcja tablicaLeonardo() na początku deklaruje pustę liczb, którą następnie uzupełnia kolejno obliczonymi wartościami. Algorytm znajduje wszystkie liczby ma złożoność liniową O(n).

Testowanie funkcji

W celu przetestowania napisanych funkcji można skorzystać z poniższego fragmentu kodu:

1. int main() {
2.   int n, k;
3.   cout << "Ktora liczbe Leonardo wypisac?\n n = ";
4.   cin >> n;
5.   cout << "L(" << n << ") = " << Leonardo(n);
6.   cout << "\nIle pierwszych liczb wypisac?\n k = ";
7.   cin >> k;
8.   vector<int> lista = tablicaLeonardo(k);
9.   for each (int x in lista) {
10.     cout << x << " ";
11.   }
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja