3672 - Calculeaza pe n - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T12:31:39Z

Rezolvare

← Older revision		Revision as of 12:31, 29 December 2023
Line 46:		Line 46:

	return dp[n] if dp[n] != float('inf') else 0		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ă		# Citire număr de la tastatură
	n = int(input("~~Introduceti numarul~~ n: "))		n = int(input("Introduceți numărul n: "))

	~~# Calcul și afișare rezultat~~
	~~rezultat = numar_minim_operatii(n)~~
	~~print(f"Numarul minim de operatii pentru a obtine {n} este: {rezultat}"~~)

			# 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>		</syntaxhighlight>

Mesarosdenisa: /* Rezolvare */

2023-12-27T09:33:46Z

Rezolvare

← Older revision		Revision as of 09:33, 27 December 2023
Line 33:		Line 33:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<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>		</syntaxhighlight>

Mesarosdenisa at 09:32, 27 December 2023

2023-12-27T09:32:30Z

← Older revision		Revision as of 09:32, 27 December 2023
Line 21:		Line 21:
	:1		:1
	;Iesire		;Iesire
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:0		:0

Line 28:		Line 28:
	:0		:0
	;Iesire		;Iesire
	;Datele introduse nu corespund restrictiilor impuse		:Datele introduse nu corespund restrictiilor impuse

Mesarosdenisa at 09:32, 27 December 2023

2023-12-27T09:32:02Z

← Older revision		Revision as of 09:32, 27 December 2023
Line 1:		Line 1:
	== Cerinta ==		== 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 ==		== Date de intrare ==

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

	== Date de iesire ==		== 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 ==		== Restrictii si precizari ==

	*1 ≤ n ≤ 1.000.000		*1 &les; n &les; 1.000.000

	== Exemplul 1 ==		== Exemplul 1 ==

Mesarosdenisa: Pagină nouă: == 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 cit...

2023-12-12T11:33:36Z

Pagină nouă: == 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 cit...

New page

== 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">
from collections import deque

def min_operatii(n):
visited = set()
queue = deque([(1, 0)]) # Coada va conține tupluri (valoare_curenta, numar_operatii)

while queue:
x, k = queue.popleft()

if x == n:
return k

if x * 2 not in visited and x * 2 <= n:
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
rezultat = min_operatii(n)
print(f"Numărul minim de operații pentru a obține {n} este {rezultat}.")

</syntaxhighlight>