3672 - Calculeaza pe n

From Bitnami MediaWiki
Revision as of 12:31, 29 December 2023 by Mesarosdenisa (talk | contribs) (→‎Rezolvare)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 ⩽ n ⩽ 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
  1. Citire număr de la tastatură

n = int(input("Introduceți numărul n: "))

  1. 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>