Strona główna » Algorytmy » Teoria Liczb » Ciąg Lucasa
 

Ciąg Lucasa

https://mattomatti.com/a63

Definicja

Ciąg Lucasa określa się w sposób rekurencyjny:

Pierwsze kilka liczb ciągu Lucasa to: 2, 1, 3, 4, 7, 11, 18, 29, ...

Spostrzeżenie

Ciąg Lucasa tworzy się w bardzo podobny sposób jak ciąg Fibonacciego. W obu przypadkach n-ty wyraz to suma dwóch poprzednich. Interesujący jest fakt, że stosunek i-tego wyrazu do wyrazu i - 1 wynosi Φ. Taka samą zależność można zaobserwować przy analizie ciagu Fibonacciego. Kolejne wyrazy ciągu można wyznaczyć przy pomocy wspomnianej liczby Φ. Im wartość i - 1 wyrazu jest większy to pomnożona przez Φ da dokładniejszy wynik kolejnej liczby.

Implementacja

Rozwiązanie rekurencyjne

Przy pisaniu kodu wyliczającego wyrazy według ciągu rekurencyjnego od razu nasuwa się rozwiązanie rekurencyjne:

  1. int lucas(int n){
  2.   switch(n){
  3.     case 1: return 2;
  4.     case 2: return 1;
  5.     default: return lucas(n - 1) + lucas(n - 2);
  6.   }
  7. }

(1.) Funkcja lucas() przyjmuje argument n - element, który chcemy wyznaczyć. (2.) W zależności od n: (3.) zwraca 2 dla n = 1, (4.) zwraca 1 dla n = 2. W przypadku wartości n > 2 należy zwrócić wartość dwóch poprzednich liczb o indeksie n - 1 oraz n - 2.

Rozwiązanie iteracyjne

Innym pomysłem na rozwiązanie problemu jest wyznaczanie iteracyjne, które jest szybsze od wyznaczania rekurencyjnego i nadają się do wypisywania całego ciągu. Poprzednie wyraz są przechowywane w zmiennych a i b:

  1. int lucas(int n){
  2.   if(n > 2){
  3.     int a = 2, b = 1, c = a + b;
  4.     while(n > 2){
  5.       a = b;
  6.       b = c;
  7.       c = a + b;
  8.       n--;
  9.     }
  10.     return c;
  11.   } else {
  12.     return (n == 1) ? 2 : 1;
  13.   }
  14. }

(1.) Jeśli wartość n > 2 to: (2.) deklarujemy zmienna a, b i c, które kolejno są wyrazami n - 2, n - 1 i n-tym. (3.) W pętli dopóki n > 2: (4. - 5.) przesuwa się wartości, (6.) wylicza nową, a następnie zmniejsza o 1. (8.) Po zakończeniu pętli wystarczy zwrócić c. Jednak dla n = 0 oraz n = 1 wyróżniamy (12.) oddzielny przypadek i w zależności od n zwracamy odpowiednią wartość.

Testowanie funkcji

Poniższy funkcja wywoła utworzoną funkcję lucas() i wypisze na ekran 10 wyraz:

  1. int main () {
  2.   cout << "10 wyrazem ciagu Lucasa jest ";
  3.   cout << lucas(10) << endl;
  4.   system("pause");
  5.   return 0;
  6. }

Zadania

Zadanie 1

Napisz aplikację, która wypisze na ekran n pierwszych liczb ciągu Lucasa. Kolejne wyrazy powinny być rozdzielone spacją, a liczbę n powinien wprowadzić użytkownik. Pamiętaj o komunikatach dla użytkownika, aby wiedział co aktualnie oczekuje / wykonuje program.

Dla wprowadzonego n = 10 program powinien wypisać:

  1. Pierwsze 10 wyrazow ciagu to:
  2. 2 1 3 4 7 11 18 29 47 76