Ciąg Newman-Conway

Ciąg

Ciąg Newman-Conway dany jest wzorem rekurencyjnym o wyrazach początkowych a(1) = a(2) = 1, a każdy następny jest dany wzorem:

a(n) = a(a(n - 1)) + a(n - a(n - 1))

Wartości ciągu można ustawić w następujący ciąg:

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, ..

Analiza ciągu

Ciąg Newman-Conway jest ciągiem rekurencyjnym o bardzo dużej złożoności. Chcąc obliczyć n-ty wyraz trzeba obliczyć 4 inne. Można się o tym przekonać już dla wyrazu a(3):

a(3) = a(a(3 - 1)) + a(3 - a(3 - 1)) = a(a(2)) + a(3 - a(2)) = a(1) + a(3 - 1) = a(1) + a(2) = 2

Jak można zauważyć obliczanie każdego następnego wyrazu nie posiadających zapisanych poprzednich jest procesem bardzo żmudnym i czasochłonnym. Z tego powodu wyrazy najlepiej wyliczać jeden po drugim. Interesujący jest fakt, że jeśli k-ty wyraz ma wartość k/2. Warunkiem jest, że k-ty wyraz jest potęgą liczby 2.

Implementacja

Rekurencja

Wzory rekurencyjne bardzo łatwo przenosi się na kod programu. Jednak na przykładzie ciągu Fibonacciego łatwo się przekonać, że nie jest najbardziej efektywne rozwiązanie, ponieważ wiele obliczeń bardzo dużo się powtarza. Dla ciągu Newman-Conway złożoność ta jest jeszcze większa, bo jak zostało wcześniej zauważone trzeba obliczyć rekurencyjnie, aż cztery inne wyrazy, aby uzyskać wyraz.

1. int NewmanConway(int n) {
2.   if (n <= 2)
3.     return 1;
4.   return NewmanConway(NewmanConway(n - 1)) + NewmanConway(n - NewmanConway(n - 1));
5. }

Funkcja NewmanConway() zwraca n-ty wyraz ciągu. Wewnątrz znajduje się warunek, który zwraca wartości początkowe dla pierwszego i drugiego wyrazu, a jeśli n jest większe od 2 to zwracana jest wartość obliczona ze wzoru.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższych kilku linijek, które wczytują liczbę k i wypisuje k pierwszych wyrazów ciągu.

1. int main () {
2.   int k;
3.   cout << "Ile wyrazow wypisac?\n k = ";
4.   cin >> k;
5.   for (int i = 1; i <= k; i++)
6.     cout << NewmanConway(i) << " ";
7.   system("pause");
8.   return 0;
9. }

Programowanie dynamiczne

W celu ograniczenia liczenia tych samych wartości w kółko w sposób rekurenycjny potrzebna jest tablica, która pozwoli na zapamiętanie obliczonych do tej pory wartości. Gwarantowane jest to, że do obliczenia n-tego wystarczy znać jedynie poprzednie wyrazy. W tym przypadku funkcja generujNewmanConway() zwraca tablicę, gdzie każdy kolejny element to kolejny wyraz ciągu Newman-Conway. Oto przykładowa implementacja:

1. int* generujNewmanConway(int k) {
2.   int* dane = new int[k + 1];
3.   dane[0] = 0;
4.   dane[1] = dane[2] = 1;
5.   for (int i = 3; i < k; i++)
6.     dane[i] = dane[dane[i - 1]] + dane[i - dane[i - 1]];
7.   return dane;
8. }

Początkowo deklarowana jest tablica pod zapisywane elementy, ustalane są wartości początkowe, a następnie tablica jest wypełniana korzystając z podanego wcześniej wzoru. Elementy w tablicy są indeksowane od pozycji 0, ale elementy ciągu są zapisywane od drugiego elementu tablicy. Przyjmujemy, że a(0) = 0.

Testowanie funkcji

Funkcja testująca musi zostać zmodyfikowana, aby wypisywała zwróconą tablicę przez funkcję generujNewmanConway().

1. int main() {
2.   int k;
3.   cout << "Ile wyrazow wypisac?\n k = ";
4.   cin >> k;
5.   int* dane = generujNewmanConway(k);
6.   for (int i = 1; i < k; i++)
7.     cout << dane[i] << " ";
8.   system("pause");
9.   return 0;
10. }

• Kod źródłowy Implementacja