Strona główna » Algorytmy » Teoria Liczb » Ciąg Recamána
 

Ciąg Recamána

https://mattomatti.com/a0023

Definicja

Ciąg Recamána to ciąg liczb naturalnych, którego pierwszy wyraz to 0. Każdy następny wyraz jest określony rekurencyjnie. Jeśli wyliczona wartość w = an - 1 - n jest dodatnia i nie jest wartość żadnego poprzedniego wyrazu ciągu to ustal jako an. W przeciwnym razie ustal an = an - 1 + n. Ciąg Recamána to ciąg, który można opisać słowami "odejmij jeśli możesz, w przeciwnym razie dodaj".

Wyrazy ciągu

Ciąg Recamána to kolejno: 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, ..

Implementacja

w celu optymalizacji kodu generującego kod funkcja tworzy nową dynamiczną tablicę liczb, która będzie przechowywać wyniki cząstkowe. W ten sposób zostanie zaoszczędzona moc obliczeniowa. Gdyby każdy wyraz wyliczać oddzielnie to złożność czasowa byłaby O(n2), ponieważ do wyliczenia n-tego wyrazu należałoby wyliczyć wszystkie n - 1 poprzednich wyrazów.

Poniższy kod generuje listę zawierającą k pierwszych wyrazów ciągu Recamána.

  1. int* ciagRecamana(int k) {
  2.   int* lista = new int[k];
  3.   lista[0] = 0;
  4.   for (int i = 1; i < k; i++) {
  5.     int wartosc = lista[i - 1] - i;
  6.     if (wartosc > 0 && !wystepuje(lista, i, wartosc)) {
  7.       lista[i] = wartosc;
  8.     } else {
  9.       lista[i] = lista[i - 1] + i;
  10.     }
  11.   }
  12.   return lista;
  13. }

(2.) Alokacja tablicy i (3.) przypisanie pierwszego wyrazu ciągu. (4.) Dla każdego kolejnego wyrazu: (5.) wylicz wartość w. (6.) Jeśli dana wartość jest dodatnia i nie występowała wcześniej w wyliczonych wyrazach to (7.) przypisz wyliczoną wartość, a w przeciwnym razie (9.) ustal na wartość poprzedni wyraz + i. Na koniec (12.) zwróć wskaźnik na listę.

Wyszukiwanie

W celu sprawdzenia czy dana wartość nie występuje już w tablicy została dopisana specjalna funkcja wystepuje(), która w podanej liście lista o długości n sprawdza czy występuje wartość a.

  1. bool wystepuje(int* lista, int n, int a) {
  2.   for (int i = 0; i < n; i++)
  3.     if (lista[i] == a)
  4.       return true;
  5.   return false;
  6. }

Jeśli dana wartość występuje to (4.) zwracana jest prawda, a w przeciwnym wypadku (5.) wartość 5.

Testowanie funkcji

Poniższa funkcja main() demonstruje jak wypisać pierwsze 20 wyrazów przy pomocy napisanej funkcji:

  1. int main () {
  2.   int k = 20;
  3.   int* lista = ciagRecamana(k);
  4.   for (int i = 0; i < k; i++)
  5.     cout << lista[i] << endl;
  6.   system("pause");
  7.   return 0;
  8. }

Zadania

Zadanie 1

Napisz przeciążenie funkcji int* ciagRecamana(int k, int p), gdzie parametr p będzie określał wartość pierwszego wyrazu ciągu.

Przykładowo dla k = 10 oraz p = 3 program wypisze* ciąg:

  1. 3, 2, 4, 1, 5, 10, 16, 9, 17, 8

* sposób wypisania pozostaje dowolny

Zadanie 2

Napisz funkcje int podajIndeks(int a), która zwróci na której pozycji występuje wskazana wartość a w ciągu Recamána. Dopisz przeciążenie funkcji int podajIndeks(int a, int p), która będzie szukać wyrazu a w ciągu utworzonym na zasadach z zadania 1.

Przykładowo dla a = 7 program zwróci:

  1. a(5) = 7

Z kolei dla a = 7 i p = 3 poprawny wynik to:

  1. a(11) = 7