3672 - Calculeaza pe n: Difference between revisions

Revision as of 09:33, 27 December 2023

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

Citire număr de la tastatură

n = int(input("Introduceti numarul n: "))

Calcul și afișare rezultat

rezultat = numar_minim_operatii(n) print(f"Numarul minim de operatii pentru a obtine {n} este: {rezultat}")

</syntaxhighlight>

@@ Line 33: / Line 33: @@
 == 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:
+# Citire număr de la tastatură
-            return k
+n = int(input("Introduceti numarul n: "))
-        if x * 2 not in visited and x * 2 <= n:
+# Calcul și afișare rezultat
-            queue.append((x * 2, k + 1))
+rezultat = numar_minim_operatii(n)
-            visited.add(x * 2)
+print(f"Numarul minim de operatii pentru a obtine {n} este: {rezultat}")
-        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
-rezultat = min_operatii(n)
-print(f"Numărul minim de operații pentru a obține {n} este {rezultat}.")
 </syntaxhighlight>