Ciąg Collatza

Zadanie 9 z 10 · rozdział 4Trudność: 1 z 3whilepętlewarunki

Treść zadania

Ciąg Collatza zaczyna się od liczby n. Każdy kolejny wyraz powstaje z poprzedniego x według reguły:

  • jeśli x jest parzyste, następny wyraz to $\frac{x}{2}$,
  • jeśli x jest nieparzyste, następny wyraz to $3x + 1$.

Ciąg kończy się, gdy osiągnie wartość 1.

Wczytaj n i wypisz, ile kroków (przejść do kolejnego wyrazu) potrzeba, aby dojść do 1, oraz jaka jest największa wartość, która pojawiła się w ciągu (łącznie z samym n).

Dane wejściowe

  • 1. linia: n — liczba naturalna (n ≥ 1)

Dane wyjściowe

Dwie liczby całkowite, każda w osobnej linii:

  1. liczba kroków potrzebnych do osiągnięcia 1,
  2. największa wartość w ciągu.

Ograniczenia

  • 1 ≤ n ≤ 1000000

Uwagi

  • Nie wiadomo z góry, ile kroków wykona pętla — to typowe zastosowanie pętli while.
  • Dla n = 1 ciąg od razu jest w 1: wypisz 0 i 1.
  • Do dzielenia używaj //, żeby wyrazy ciągu pozostały liczbami całkowitymi.
  • Nikt nie udowodnił, że ciąg Collatza zawsze dochodzi do 1 (to słynna hipoteza Collatza), ale sprawdzono to dla wszystkich liczb z zakresu zadania.

Przykład

Wejście
6
Wyjście
8
16

Ciąg ma postać $6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$: to 8 kroków, a największy wyraz to 16.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 4

Zadania w tym rozdziale ćwiczą powtarzanie instrukcji za pomocą pętli while i for: wczytywanie danych aż do spełnienia warunku, wypisywanie ciągów liczb, sumowanie i proste obliczenia.

Konwencje wspólne:

  • Każde zadanie (i każdy podpunkt) to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
  • Dane wejściowe wczytuj dokładnie w podanej kolejności, każdą wartość z osobnej linii (o ile nie napisano inaczej).
  • Jeśli wynik ma być „każdy w osobnej linii”, po każdej wartości wypisz znak nowej linii.
  • Jeśli zadanie mówi, że w danym przypadku nic nie trzeba wypisywać, program nie wypisuje nic (nawet pustej linii).

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
1
Oczekiwane wyjście
0
1

Test 2

Nie uruchomiono
Wejście
2
Oczekiwane wyjście
1
2

Test 3

Nie uruchomiono
Wejście
7
Oczekiwane wyjście
16
52

Test 4

Nie uruchomiono
Wejście
16
Oczekiwane wyjście
4
16

Test 5

Nie uruchomiono
Wejście
27
Oczekiwane wyjście
111
9232
Uruchom z własnymi danymi