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:

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.

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.

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:

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.

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.

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

• Kod źródłowy Implementacja

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

• Kod źródłowy Zadanie 1