Strona główna » Algorytmy » Teoria Liczb » Ciąg Samoliczący
 

Ciąg Samoliczący

https://mattomatti.com/a0017

Definicja

Ciąg Samoliczący to ciąg, który definiuje się następująco: jedna jedynka, dwie dwójki, trzy trójki, cztery czwórki itd. Kolejne wyrazy tego ciągu to: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5....

Implementacja

Istnieje kilka metod, których wynikiem będzie napisanie kodu wypisującego kolejne wyrazy ciągu. Poniżej zostały one przedstawione wraz z krótkim komentarzem.

Pętla

Pierwsze rozwiązanie polega na zastosowaniu pętli w cleu wypisywania kolejnych wyrazów. Funkcja na bieżąco przechowuje informacje jaką liczbę wypisuje i ile jeszcze takiej liczby ma wypisać. Warunkiem stopu jest osiągnięcie wyrazu o indeksie wskazanym przez przekazany argument.

  1. void wypiszCiag(int n) {
  2.   int val = 1;
  3.   int ile = 1;
  4.   while (n--) {
  5.     if (ile == 0)
  6.       ile = ++val;
  7.     cout << val << " ";
  8.     ile--;
  9.   }
  10. }

Deklaracja zmiennych: (2.) zmienna val przechowuje jaka liczba jest aktualnie wypisywana oraz (3.) ile - ile jeszcze razy wartość val ma zostać wypisana. (4.) Dopóki zostały wyrazy do napisania to (5.) sprawdź czy wypisano wartość val odpowiednią ilość razy. Jeśli tak to (6.) zwiększ wypisywaną liczbę (tj. zmienną val) i przypisz ile razy powinna zostac wypisana. Niezależnie od zmiany wypisywanej liczby (7.) wypisz liczbę i (8.) zmniejsz ile razy powinna zostać jeszcze wypisana.

Wzór

Istnieje wzór na wyliczenie n-tego wyrazu ciągu: | 0.5 + √2n |. Poniżej został przedstawiony kod wykorzystujący wzór do obliczenia dowolnego wyrazu ciągu:

  1. int wypisznWyraz(int n) {
  2.   return (int)(0.5 + sqrt(2 * n));
  3. }

Rekurencja

Choć może to wydawać się zaskakujące to takie nie powinno być. Wzór na n-ty wyraz można wyliczyć w sposób rekurencyjny przy użyciu wzoru a(n) = 1 + a(n - a(n - 1)). Oczywiście definicja rekurencji wymaga, aby pierwszy wyraz miał przypisaną konkretną wartość. W tym przypadku dla a(1) funkcja powinna zwrócić 1. Oto kod realizujący rozwiązanie:

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

Zadania

Zadanie 1

Na podstawie kodu źródłowego Implementacja Pętla napisz funkcję o nagłówku void wypiszCiag(int n_od, int n_do). Przykładowo dla wywołania wypiszCiag(10, 16) program powinien wypisać:

  1. 4 5 5 5 5 5 6