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

Ciąg Powrotny

Definicja

Ciąg Powrotny to taki ciąg, który polega na zapisaniu kolejnych liczb naturalnych, ale jeśli zostanie wypisana liczba, która do tej pory w ciągu nie wystąpiła to należy rozpocząć liczenie od nowa.

Ciąg liczb

Ciąg ma następującą postać: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ...

Oto wyjaśnienie wyznaczania kolejnych wyrazów:

nWartośćKomentarz
111 wystąpiło pierwszy raz, więc następny wyraz to 1
21zwiększamy wartość
322 wystąpiło pierwszy raz, więc następny wyraz to 1
41zwiększamy wartość
52zwiększamy wartość
633 wystąpiło pierwszy raz, więc następny wyraz to 1
71zwiększamy wartość

Ciekawostka

Zauważmy, że po pierwszym wystąpieniu k-tej liczby następne wystąpienie jest po k wyrazach, potem kolejno po k+1, k+2, .. wyrazach. Ilustruje to poniższa tabelka w której oznaczone zostały liczby 2.

1121231234..

Implementacja

n-ty wyraz

Opisywany ciąg liczb można przedstawić w postaci tabelki, gdzie przejście do następnego wiersza następuje w chwili rozpoczęcia liczenia od nowa.

1
12
123
1234
itd.

W celu wyznaczenia n-tego wyrazu należy sprawdzić ile wyrazów znajduje się przed nim. Nie istnieje potrzeba wyznaczania ich wszystkich po kolei, ponieważ każdy wiersz zaczyna się od wyrazu 1. Z kolei i-ty wiersz ma dokładnie i-wyrazów. Wystarczy tak długo odejmować liczbę wyrazów w kolejnych wierszach, aż uzyskamy wartość, która może się znajdować w kolejnym wierszu. Jest to analogiczne do wyznaczania reszty z dzielenia - różnica tutaj polega na tym, że w każdej iteracji odejmujemy coraz większą liczbę, a w dzieleniu zawsze dzielnik.

Funkcja ntywyraz() akceptuje tylko jeden argument n. Wynikiem działania funkcji jest n-ta wartość Ciągu Powrotnego:

C++
C#
  1. int ntywyraz(int n) {
  2.   int odjemna = 0;
  3.   while (odjemna <= n) {
  4.     n -= odjemna;
  5.     odjemna++;
  6.   }
  7.   return n + 1;
  8. }

(2.) Z pierwszego wyrazu nie trzeba odejmować żadnej wartości. (3. - 5.) Odejmuj kolejne ilości elementów z kolejnych wierszy od wartości n. Na koniec (7.) należy zwrócić wartość n + 1, ponieważ wynikowa reszta jest z przedziału [0, i-1], gdzie i to numer wiersza w którym n-ta wartość się znajduje.

k wyrazów

Poprzednia metoda jest efektywna do wyznaczania pojedynczego wyrazu, ale mało efektywna do wyznaczania k pierwszych wyrazów, ponieważ im większe n tym rośnie ilość iteracji potrzebna do wyznaczenia wartości elementu ciągu.

Istnieje możliwość wyznaczania kolejnego wyrazu na podstawie poprzedniego oraz znajomości numeru wiersza w którym się znajdujemy. W ten sposób gwarantowana jest złożoność liniowa wyznaczania k-wyrazów. Funkcja kwyrazow() to przykładowa implementacja, która zwraca tablicę k pierwszych wyrazów Ciągu Powrotnego.

C++
C#
  1. int* kwyrazow(int k) {
  2.   int* tab = new int[k];
  3.   int n = 1, max = 1;
  4.   for(int i = 0; i < k; i++) {
  5.     tab[i] = n;
  6.     if (n == max) {
  7.       n = 1;
  8.       max++;
  9.     } else {
  10.       n++;
  11.     }
  12.   }
  13.   return tab;
  14. }

(2.) Przygotuj tablice pod wynik, a następnie (3.) przypisz zmiennej n - aktualny wyraz, a zmiennej max - numer aktualnego wiersza. (4.) Kolejne elementy wyznaczamy w pętli: (5.) zapisz aktualny wyraz i (6.) jeśli jest to ostatni element w wierszu to (7.) ustaw aktualny wyraz na 1 i (8.) zwiększ numer wiersza. (9.) Jednak jeśli nie jest to ostatni element w wierszu to (10.) zwiększ wartość aktualnego elementu. Na koniec (13.) funkcja zwraca wskaźnik na tablicę, gdzie dane są przechowywane.

Testowanie funkcji

Poniższy fragment kodu prezentuje zastosowanie obydwu napisanych funkcji.

C++
C#
  1. int main () {
  2.   int n;
  3.   cout << "Ktory wyraz wypisac ?\n n = ";
  4.   cin >> n;
  5.   cout << n << " wyraz to " << ntywyraz(n);
  6.   int k;
  7.   cout << endl << "Ile wyrazow wypisac ?\n k = ";
  8.   cin >> k;
  9.   int* tab = kwyrazow(k);
  10.   cout << tab[0];
  11.   for (int i = 1; i < k; i++)
  12.     cout << ", " << tab[i];
  13.   system("pause");
  14.   return 0;
  15. }

Zadania

Zadanie 1

Napisz funkcję ntywyraz() w której zostanie wykorzystany wzór na sumę n pierwszych liczb naturalnych, aby przyśpieszyć pracę. Przetestuj napisaną funkcję.