0654 - Collatz

Sursa: [1]

Cerinţa

Fie număr natural n. Acestuia i se aplică în mod repetat următoarele transformări:

dacă n este par, devine n/2 dacă n este impar, devine 3*n+1

În 1937 matematicianul Lothar Collatz a formulat următoarea conjectură : pentru orice număr natural, în urma transformărilor numărul devine 1.

De exemplu, pentru n=6 se obține șirul: 6 3 10 5 16 8 4 2 1, șir care are 9 termeni.

Pentru un n dat, determinați numărul de termeni din șirul de transformări după regula de mai sus.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând numărul de termeni din șirul transformărilor de mai sus.

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează numărul de termeni din șirul de transformări după regula de mai sus.

În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."

Restricţii şi precizări

1 ≤ n ≤ 1 000 000

Exemplul 1

Intrare

6

Ieșire

9

Rezolvare

<syntaxhighlight lang="python" line>

1. 0654

def collatz_length(n):

   count = 1  # numărul inițial de termeni este 1
   while n != 1:
       if n % 2 == 0:
           n = n // 2
       else:
           n = 3 * n + 1
       count += 1
   return count

if __name__ == '__main__':

   n = int(input())
   if not (1 <= n <= 1000000):
       print("Datele nu corespund restricțiilor impuse.")
   else:
       print("Datele sunt introduse corect.")
       print(collatz_length(n))

</syntaxhighlight>

Explicatie cod:

Acest cod calculează lungimea secvenței Collatz pentru un număr dat. Secvența Collatz a unui număr începe cu acel număr și se construiește prin aplicarea repetată a următoarei reguli: dacă numărul este par, îl împărțim la 2, altfel îl înmulțim cu 3 și adăugăm 1. Lungimea secvenței este dată de numărul de termeni ai secvenței.

Funcția collatz_length primește ca argument un număr n și calculează lungimea secvenței Collatz pentru acel număr. Numărul inițial de termeni este 1 și se crește cu 1 la fiecare iterație a while-ului până când numărul ajunge la 1.

Funcția apoi este apelată în blocul if __name__ == '__main__':, care citește de la tastatură un număr n și verifică dacă acesta se află în intervalul [1, 1000000]. Dacă nu, se afișează un mesaj de eroare. Dacă este, se calculează și se afișează lungimea secvenței Collatz pentru acel număr.