Strona główna » Algorytmy » Teoria Liczb » Liczby Perrinego
 

Liczby Perrinego

https://mattomatti.com/a0015

Definicja

Liczby Perrinego to w matematyce liczby opisywane następującym wzorem rekurencyjnym:

P(n) = P(n - 2) + P(n - 3), n > 2
Początkowe wartości to: P(0) = 3, P(1) = 0, P(2) = 2.

Liczby Perrinego służą do określania maksymalnej liczby zbiorów niezależnych w n elementowym grafie cyklicznym dla wartości n większych od 1.

Ciąg

Liczby Perrinego można ustawić w ciąg: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, ...

Implementacja

Wyznaczanie kolejnych liczb jest bardzo podobne do wyznaczania ciągu Fibonacciego ze względu na zależność rekurencyjną. Należy pamiętać, że rozwiązanie rekurencyjne jest proste w zapisie, ale nie tak efektywne jak wersja iteracyjna algorytmu.

Rozwiązanie rekurencyjne

Zapis rekurenycjny algorytmu zajmuje zaledwie kilka linijek i jest bardzo podobne do zapisu matematycznego. Warto zwrócić uwagę, że indeks wymienionych pierwszych wartości wzoru zaczyna się od zera.

  1. int liczbaPerrinego(int n) {
  2.   if (n == 0)
  3.     return 3;
  4.   if (n == 1)
  5.     return 0;
  6.   if (n == 2)
  7.     return 2;
  8.   return liczbaPerrinego(n - 2) + liczbaPerrinego(n - 3);
  9. }

(1.) Napisana funkcja zwraca n-tą liczbę Perrinego. Wyszczególnione zostały w niej (2. - 7.) przypadki trzech pierwszych wyrazów oraz (8.) wzór rekurencyjny służący do wyliczania kolejnych wartości ciągu.

Rozwiązanie iteracyjne

Rozwiązanie rekurencyjne nie jest zby efektywne, ponieważ ten sam wyraz może być wyliczany kilk razy. Lepszym rozwiązaniem jest wersja iteracyjny, która tworzy tymczasową tablicę trzech liczb i operuje na niej, aby wyliczyć kolejne wyrazy. Poniżej znajduje się kod wykorzystujący te założenia:

  1. int liczbaPerrinego(int n) {
  2.   int* tab = new int[3];
  3.   tab[2] = 2;
  4.   tab[1] = 0;
  5.   tab[0] = 3;
  6.   int temp;
  7.   while (n > 2) {
  8.     temp = tab[1] + tab[0];
  9.     tab[0] = tab[1];
  10.     tab[1] = tab[2];
  11.     tab[2] = temp;
  12.     n--;
  13.   }
  14.   temp = tab[n];
  15.   delete tab;
  16.   return temp;
  17. }

(2. - 5.) Inicjalizacja tablicy dynamicznej z początkowymi wartościami. Pierwszy wyraz na tablicy jest wyrazem o najniższym indeksie. (6.) Deklaracja zmiennej używanej jako kontener na wyliczany kolejny wyraz. (7.) Dopóki wartość n > 2, czyli dopóki na liście nie ma szukanego wyrazu to: (8.) wylicz nowy wyraz, (9. - 10.) przesuń dwa pierwsze wyrazy o jedno miejsce do tyłu i (11.) umieść na tablicy nowy wyraz. Na koniec każdej iteracji (12.) zmniejsz wartość zmiennej n. Po zakończeniu pętli (14.) pobierz odpowiednią wartość, (15.) usuń tablicę i (16.) zwróć wyliczoną wartość.

Testowanie funkcji

W celu wypisania pierwszych dziesięciu liczb Perrinego wystarczy poniższy kod:

  1. int main() {
  2.   for (int i = 0; i < 10; i++) {
  3.     cout << liczbaPerrinego(i) << endl;
  4.   }
  5.   system("pause");
  6.   return 0;
  7. }

Zadania

Zadanie 1

Napisz funkcją int sumaLiczbPerrinego(int k), która zsumuje pierwsze k liczb Perrinego. W rozwiązaniu nie używaj tablicy dynamicznej.

Przykładowo dla parametru k = 5 program wypisze 10.