3672 - Calculeaza pe n: Difference between revisions

Latest revision as of 12:31, 29 December 2023

Cerinta[edit]

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[edit]

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

Date de iesire[edit]

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[edit]

1 ⩽ n ⩽ 1.000.000

Exemplul 1[edit]

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

Exemplul 2[edit]

Intrare: 0
Iesire: Datele introduse nu corespund restrictiilor impuse

Rezolvare[edit]

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

@@ Line 1: / Line 1: @@
 == 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).
+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.
+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.
+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.
+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
+*1 &les; n &les; 1.000.000
 == Exemplul 1 ==
@@ Line 21: / Line 21: @@
 :1
 ;Iesire
-;Datele introduse corespund restrictiilor impuse
+:Datele introduse corespund restrictiilor impuse
 :0
@@ Line 28: / Line 28: @@
 :0
 ;Iesire
-;Datele introduse nu corespund restrictiilor impuse
+:Datele introduse nu corespund restrictiilor impuse
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-from collections import deque
+def numar_minim_operatii(n):
+    dp = [float('inf')] * (n + 1)
+    dp[1] = 0
-def min_operatii(n):
+    for i in range(1, n + 1):
-    visited = set()
+        if i * 2 <= n:
-    queue = deque([(1, 0)])  # Coada va conține tupluri (valoare_curenta, numar_operatii)
+            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)
-     while queue:
+     return dp[n] if dp[n] != float('inf') else 0
-        x, k = queue.popleft()
-        if x == n:
+def verificare_date_intrare(n):
-            return k
+    return 1 <= n <= 1000000
-        if x * 2 not in visited and x * 2 <= n:
+# Citire număr de la tastatură
-            queue.append((x * 2, k + 1))
-            visited.add(x * 2)
-        if x * 3 not in visited and x * 3 <= n:
-            queue.append((x * 3, k + 1))
-            visited.add(x * 3)
-        if x + 1 not in visited and x + 1 <= n:
-            queue.append((x + 1, k + 1))
-            visited.add(x + 1)
-    return 0  # Nu s-a putut ajunge la n
-# Citirea datelor de intrare
 n = int(input("Introduceți numărul n: "))
-# Calculul și afișarea rezultatului
+# Verificare date de intrare
-rezultat = min_operatii(n)
+if not verificare_date_intrare(n):
-print(f"Numărul minim de operații pentru a obține {n} este {rezultat}.")
+    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>