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:

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.

• Kod źródłowy Ciąg Fibonacciego
• Kod źródłowy Ciąg Tribonacci

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. }

• Kod źródłowy Przypadek ogólny

Zadania

Zadanie 1

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

• Kod źródłowy Zadanie 1