Strona główna » Algorytmy » Artykuły » Ciągi Fibonacciego wyższego rzędu

Ciągi Fibonacciego wyższego rzędu

Wstęp

Ciąg Fibonacciego

Dotychczas poznany ciąg Fibonacciego był określony następującym wzorem:

Ciąg Tribonacciego

Na podstawie tego ciągu można określić inne ciągi. Przykładowo ciąg Tribonacci ma określone trzy pierwsze wyrazy ciągu, a każdy kolejny wyraz jest sumą trzech pozostałych. Matematycznie można to zapisać jako:

Ogólny wzór

Na podstawie dwóch powyższych wzorów istnieje możliwość wyprowadzenia wzoru na wzór ciągu, którego każdy kolejny wyraz będzie sumą k poprzednich. Wtedy taki ciag byłby opisany następująco:

W przypadku, gdyby k wyniosło 1 to powstałby ciąg stały o wszystkich wyrazach równych 1. W poniższej tabelce zostały wypisane nazwy kolejnych ciągów oraz ich początkowe wyrazy. Liczba k oznacza w tym przypadku ile poprzednich wyrazów się sumuje w opisywanym ciągu:

kNazwa ciąguPoczątkowe wyrazy
2Fibonacci0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
3Tribonacci0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, ...
4Tetranacci0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, ...
5Pentanacci0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, ...
6Hexanacci0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, ...
7Heptanacci0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, ...
8Octanacci0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, ...
9Nonacci0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, ...

Implementacja

Cel

Celem jest napisanie funkcji, która będzie obliczała n-ty wyraz ciągu k-anacciego.

Ciąg Fibonnaciego

Na początku warto przeanalizować wzór na najprostszy przypadek opisywanych ciągów. Najprostsza iteracyjna wersja tego równania wygląda następująco:

  1. int Fibonacci(int n) {
  2.   int an = 1, an_1 = 0, pom;
  3.   if (n == 0)
  4.     return an_1;
  5.   if (n == 1)
  6.     return an;
  7.   for (int i = 1; i < n; i++) {
  8.     pom = an + an_1;
  9.     an_1 = an;
  10.     an = pom;
  11.   }
  12.   return an;
  13. }

(1.) Funkcja Fibonacci() przyjmuje argument n i na jego podstawie zwraca n-ty wyraz ciągu Fibonacciego. (2.) Zadeklaruj zmienne an, an_1 czyli kolejno n-ty oraz poprzedni wyraz ciągu. Zmienna pom jest zmienną pomocniczą. (3.) Jeśli użytkownik chce wyrazu o indeksie 0 to (4.) zwróć go. Analogicznie dla (5. - 6.) wyrazu o indeksie 1. Jeśli jednak użytkownik chce inny wyraz to: (7. - 11.) dopóki an nie jest n-tym wyrazem to: (8.) oblicz kolejny wyraz i przechowaj w pom.

Ciąg Tribonacci

Kod wyliczający ciąg Tribonacci można napisać bardzo szybko ściągając niemalże cały poprzedni kod.

  1. int Tribonacci(int n) {
  2.   int an = 1, an_1 = 0, an_2 = 0, pom;
  3.   if (n == 0)
  4.     return an_2;
  5.   if (n == 1)
  6.     return an_1;
  7.   if (n == 2)
  8.     return an;
  9.   for (int i = 2; i < n; i++) {
  10.     pom = an + an_1 + an_2;
  11.     an_2 = an_1;
  12.     an_1 = an;
  13.     an = pom;
  14.   }
  15.   return an;
  16. }

W kodzie należy dokonać niewielkich zmian: (2.) zadeklarować nową zmienną an_2, ponieważ istnieje potrzeba przechowywania trzech, a nie tylko dwóch ostatnich wartości. To powoduje również potrzebę dodania kolejnego przypadku jeśli . Należy też pamiętać, że podczas obliczania kolejnego wyrazu należy uwzględnić trzy poprzednie wyrazy.

Przypadek ogólny

Implementacja

Warto zauważyć, że dla k-anacciego ciągu trzeba pamiętać k wyrazów, dokonać k - 1 przesunięć. Dla zwróć zero itd. W takim razie warto spróbować napisać funkcję k_annacci(), która będzie przyjmowała dwa argumenty: k - określi typ ciągu oraz n - określi, który wyraz ciągu ma zostać zwrócony.

  1. int k_anacci(int k, int n) {
  2.   int pom;
  3.   if (n <= k - 2)
  4.     return 0;
  5.   if (n == k - 1)
  6.     return 1;
  7.   int* lista = new int[k];
  8.   for (int i = 0; i + 1 < k; i++)
  9.     lista[i] = 0;
  10.   lista[k - 1] = 1;
  11.   for (int i = k; i < n; i++) {
  12.     pom = 0;
  13.     for (int j = 0; j + 1 < k; j++) {
  14.       pom += lista[j];
  15.       lista[j] = lista[j + 1];
  16.     }
  17.     lista[k - 1] += pom;
  18.   }
  19.   return lista[k - 1];
  20. }

(1.) Funkcja przyjmuje teraz dwa argumenty: k - określa na podstawie ilu poprzednich wyrazach powstaje n wyraz oraz n - wyraz do wyliczenia. (2.) Zadeklaruj zmienną pomocniczą. (3. - 4.) Dla k - 2 pierwszych wyrazów zwróć 0, a (5. - 6.) dla następnego: 1. Jeśli jednak to: (7.) zaalokuj pamięć pod tablicę i (8. - 9.) wypełnij wszystko zerami prócz ostatniego elementu, który zostaje ustalony (10.) oddzielnie. Następnie (11.- 18.) obliczaj tak długo kolejne wyrazy, aż do zostanie wyliczony n-ty wyraz. W celu obliczenie wyrazu i-tego wyrazu: (12.) wyzeruj zmienną pomocniczą i (13. - 16.) dla każdej pary dwóch kolejnych wyrazów dodaj wartość j-tego elementu listy i przesuń na jego miejsce kolejny wyraz. Na koniec (17.) dodaj wartość pom do ostatniego wyrazu na liście. (18.) zwróć wartość ostatniego wyrazu.

Testowanie funkcji

Napisaną funkcję k_anacci() można przetestować przy pomocy poniższej funkcji main(). Po uruchomieniu program zapyta się ile k poprzednich wyrazów ma zostać zsumowanych oraz który n-ty wyraz ciągu wypisać.

  1. int main () {
  2.   int k, n;
  3.   cout << "Ile poprzednich wyrazow sumowac?\n";
  4.   cin >> k;
  5.   cout << "Ktory wyraz wypisac?\n";
  6.   cin >> n;
  7.   cout << k_anacci(k, n) << endl;
  8.   system("pause");
  9.   return 0;
  10. }

Zadania

Zadanie 1

Napisz nową wersję funkcji k_anacci(), która nie będzie korzystała z przesuwania / przepisywania przechowywanych wartości.