Ciąg Gradowy

Wstęp

Ciąg Gradowy to taki ciąg, którego następny wyraz jest wyliczany na podstawie reguły zależnej od parzystości poprzedniego wyrazu. Zakłada się, że ciąg Gradowy dla dowolnej liczby zawsze ma skończoną liczbę elementów.

Definicja

Ciąg Gradowy dla pewnego wyrazu początkowego n generuje się w następujący sposób:

1. jeśli n wynosi 1 to generowanie ciągu się kończy
2. jeśli n parzyste to następny wyraz wynosi n/2
3. jeśli n nieparzyste to następny wyraz wynosi 3n + 1

Przykład 1

Przykładowo dla pierwszego elementu 4 otrzymuje się kolejno: 4, 2, 1. Jak widać ciag bardzo szybko się kończy, ponieważ już trzeci element wynosi 1. Generalnie dla elementów początkowych, które można zapisać w postaci 2ⁿ ciag będzie składał się z n + 1 elementów co wynika z faktu, że każdy następny wyraz to połowa poprzedniego.

Przykład 2

Z kolei dla pierwszego elementu 6 otrzymuje się kolejno: 5, 16, 8, 4, 2, 1. Tym razem ciąg jest zdecydowanie dłuższy co wynika z faktu, że 5 jest liczbą nieparzystą.

Uwagi

Istnieje nie udowodnione przypuszczenie Collatza, że dla dowolnej liczby n ciąg Gradowy zawsze się kończy. Ciekawostką jest fakt, że każdy ciąg kończy się wyrazami 4, 2, 1. Ponadto, gdyby generowanie ciągu nie kończyło się na wartości 1 to wyrazy 4, 2, 1 możnaby wypisywać w tej samej kolejności bez końca, ponieważ 1 jest nieparzyste, więc 3·1 + 1 = 4, a następnie 4/2 = 2, a 2/2 = 1 i koło się zamyka.

Implementacja

Zadanie

Napisz program, który dla zadanej pierwszej wartości wygeneruje ciąg Gradowy, a następnie go wypisze. Pierwsza wartość powinna zostać wczytana od użytkownika.

Rozwiązanie

Dla podanej wartości n poniższa funkcja ciagGradowy() generuje ciąg Gradowy o pierwszym wyrazie n. Wynikiem działa funkcji jest lista liczb.

1. vector<int> ciagGradowy(int n) {
2.   vector<int> v;
3.   v.push_back(n);
4.   while (v[v.size() - 1] != 1) {
5.     if (n % 2 == 0) {
6.       n /= 2;
7.     } else {
8.       n = 3 * n + 1;
9.     }
10.     v.push_back(n);
11.   }
12.   return v;
13. }

(2.) Przygotuj listę i (3.) umieść na niej pierwszy element. Dopóki (4.) ostatni element jest różny od 1 to (5. - 9.) wylicz następny i (10.) dopisz go na listę. Na koniec (12.) zwróć utworzoną listę.

Testowanie funkcji

Działanie funkcji można przetestować przy pomocy poniższego fragmentu kodu, który wczyta od użytkownika pierwszy element, a następnie wypisze wyrazy znalezionego ciągu.

1. int main () {
2.   int n;
3.   cout << "Podaj wartosc pierwszego elementu\n n = ";
4.   cin >> n;
5.   cout << "Kolejne wyrazy tego ciagu to:" << endl;
6.   vector<int> v = ciagGradowy(n);
7.   for (int i = 0; i < v.size(); i++)
8.     cout << v[i] << " ";
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję najdluzszyCiag(), która znajdzie dla przekazanej liczby k ciąg Gradowy, który jest nadłuższy dla dowolnej liczby z przedziału [1, k].

Przykładowo dla k = 1000 poprawnym wynikiem jest:

1. Najdłuższy ciąg jest dla 871, długość wynosi 179

• Kod źródłowy Zadanie 1