Editing 3672 - Calculeaza pe n

== Cerinta ==

Se citește de la tastatură număr natural '''n'''. Pornind de la valoarea '''1''', asupra valorii curente '''x''' se pot aplica următoarele trei operații: înmulțire cu '''2''', înmulțire cu '''3''' sau adunare cu '''1'''. De exemplu, dacă '''x=1''' atunci se poate obține '''2''' (prin înmulțirea cu 2 sau prin adunarea cu 1) sau '''3''' (prin înmulțirea cu 3).

Calculați numărul minim de operații necesare pentru a obține numărul '''n''' începând de la numărul '''1'''.

== Date de intrare ==

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

== Date de iesire ==

Programul va afișa pe ecran numărul '''k''', reprezentând numărul minim de operații pentru obținerea numărului '''n''' pornind de la '''1''' sau valoarea '''0''' dacă nu se poate obține '''n'''.

== Restrictii si precizari ==

*1 &les; n &les; 1.000.000

== Exemplul 1 ==
;Intrare
:1
;Iesire
:Datele introduse corespund restrictiilor impuse
:0

== Exemplul 2 ==
;Intrare
:0
;Iesire
:Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def numar_minim_operatii(n):
    dp = [float('inf')] * (n + 1)
    dp[1] = 0

    for i in range(1, n + 1):
        if i * 2 <= n:
            dp[i * 2] = min(dp[i * 2], dp[i] + 1)
        if i * 3 <= n:
            dp[i * 3] = min(dp[i * 3], dp[i] + 1)
        if i + 1 <= n:
            dp[i + 1] = min(dp[i + 1], dp[i] + 1)

    return dp[n] if dp[n] != float('inf') else 0

def verificare_date_intrare(n):
    return 1 <= n <= 1000000

# Citire număr de la tastatură
n = int(input("Introduceți numărul n: "))

# Verificare date de intrare
if not verificare_date_intrare(n):
    print("Datele introduse nu corespund restricțiilor impuse")
else:
    # Calcul și afișare rezultat
    rezultat = numar_minim_operatii(n)
    print(f"Numărul minim de operații pentru a obține {n} este: {rezultat}")

</syntaxhighlight>