1651 - Graf - Revision history

Simina at 13:07, 7 January 2024

2024-01-07T13:07:58Z

← Older revision		Revision as of 13:07, 7 January 2024
Line 45:		Line 45:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	def ~~verifica_restricții~~(n, m, ~~muchii~~):		from typing import List, Tuple
	~~# Verificăm restricțiile~~
	if not (1 <= n <= 100~~) or any(not (1 <= vf1 <= n and 1 <= vf2 <= n) for vf1, vf2, _ in muchii) or any(not (1 <= p < 1000) for _, _, p in muchii~~):		def check_constraints(n, m, edges):
			if not (1 <= n <= 100):
	return False		return False
			for edge in edges:
			i, j, p = edge
			if not (1 <= i <= n) or not (1 <= j <= n) or not (1 <= p < 1000):
			return False
	return True		return True

	def ~~gaseste_varf_minim_media_ponderilor~~(~~n, m, muchii~~):		def main():
	~~# Initializăm un dicționar pentru a stoca ponderile muchiilor incidente pentru fiecare vârf~~		nMAX = 100
	~~ponderi_vf~~ = ~~{i:~~ [] for i in range(1, n + 1)}		mat = [[] for _ in range(nMAX + 1)] # mat[i][0] = (j, p) (edge between i and j with weight p)

			n, m = map(int, input().split())

			if not (1 <= n <= 100):
			print("Detele nu respecta restrictiile impuse")
			return

	~~# Citim și memorăm ponderile muchiilor în dicționar~~		edges = [tuple(map(int, input().split())) for _ in range(m)]
	for i in range(m):
	~~vf1, vf2, pondera = muchii[i]~~
	~~ponderi_vf[vf1].append(pondera)~~
	~~ponderi_vf[vf2~~]~~.append(pondera)~~

	~~# Calculăm media aritmetică a ponderilor pentru fiecare vârf~~		if not check_constraints(n, m, edges):
	~~medii_ponderi = {vf: sum~~(~~ponderi~~) ~~/ len~~(~~ponderi~~) ~~for vf, ponderi in ponderi_vf.items()}~~		print("Detele nu respecta restrictiile impuse")
			return

	~~# Găsim vârful cu media minimă~~		for i, j, p in edges:
	~~vf_min_media = min~~(~~medii_ponderi~~, ~~key=medii_ponderi~~.~~get~~)		mat[i].append((j, p))
			mat[j].append((i, p))

	~~return vf_min_media~~		vfmin = 0
			medmin = float('inf')

	~~# Citirea numărului de vârfuri~~		for i in range(1, n + 1):
	n = ~~int~~(~~input("Introduceți numărul de vârfuri ")~~)		_sum = sum(weight for _, weight in mat[i])
	if ~~not~~ (1 <~~= n <= 100)~~:		if _sum / len(mat[i]) < medmin:
	~~print~~(~~"Datele nu corespund restrictiilor impuse"~~)		medmin = _sum / len(mat[i])
	~~else:~~		vfmin = i
	~~# Citirea numărului de muchii~~
	m = ~~int(input("Introduceți numărul de muchii: "))~~

	~~# Citirea muchiilor și ponderilor~~		print(vfmin)
	print(~~"Introduceți extremitățile și ponderea fiecărei muchii:"~~)
	~~muchii = [tuple(map(int, input().split())) for _ in range(m)]~~

	~~# Apelarea funcției și afișarea rezultatului~~		if __name__ == "__main__":
	~~rezultat~~ = ~~gaseste_varf_minim_media_ponderilor(n, m, muchii)~~		main()
	~~if rezultat is not None:~~
	~~print~~(~~rezultat~~)

	</syntaxhighlight>		</syntaxhighlight>

Simina at 14:56, 27 December 2023

2023-12-27T14:56:52Z

← Older revision		Revision as of 14:56, 27 December 2023
Line 6:		Line 6:

	= Date de ieșire =		= Date de ieșire =
	Programul va afișa pe ecran numărul <code>vf</code>, reprezentând vârful determinat.		Programul va afișa pe ecran numărul <code>vf</code>, reprezentând vârful determinat.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

	= Restricții și precizări =		= Restricții și precizări =

Simina: Pagină nouă: = Cerința = Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică. = Date de intrare = Programul citește de la tastatură numerele `n m`, reprezentând numărul de vârfuri și numărul de muchii din graf, apoi `m` triplete i j p 2023-12-27T07:28:38Z Pagină nouă: = Cerința = Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică. = Date de intrare = Programul citește de la tastatură numerele <code>n m</code>, reprezentând numărul de vârfuri și numărul de muchii din graf, apoi <code>m</code> triplete <code>i j p</co... New page = Cerința = Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică. = Date de intrare = Programul citește de la tastatură numerele <code>n m</code>, reprezentând numărul de vârfuri și numărul de muchii din graf, apoi <code>m</code> triplete <code>i j p</code>, reprezentând muchiile, date prin extremități și pondere. = Date de ieșire = Programul va afișa pe ecran numărul <code>vf</code>, reprezentând vârful determinat. = Restricții și precizări = * <code>1 ≤ n ≤ 100</code> * ponderile muchiilor sunt numere naturale nenule mai mici decât <code>1000</code> * graful dat nu conține noduri izolate = Exemplul 1: = Intrare 5 6 1 2 10 2 3 2 2 5 2 3 5 12 3 4 1 4 5 5 Ieșire 4 === Explicație === Mediile ponderilor muchiilor incidente cu vârfurile grafului sunt: * pentru vârful <code>1</code> media este <code>10</code> * pentru vârful <code>2</code> media este <code>4.66667</code> * pentru vârful <code>3</code> media este <code>5</code> * pentru vârful <code>4</code> media este <code>3</code> * pentru vârful <code>5</code> media este <code>6.33333</code> Astfel media minimă este <code>3</code>, pentru vârful <code>4</code> == Exemplul 2: == <code>Intrare</code> <code>101</code> <code>consola</code> Datele nu corespund restrictiilor impuse == Rezolvare == <syntaxhighlight lang="python3" line="1"> def verifica_restricții(n, m, muchii): # Verificăm restricțiile if not (1 <= n <= 100) or any(not (1 <= vf1 <= n and 1 <= vf2 <= n) for vf1, vf2, _ in muchii) or any(not (1 <= p < 1000) for _, _, p in muchii): return False return True def gaseste_varf_minim_media_ponderilor(n, m, muchii): # Initializăm un dicționar pentru a stoca ponderile muchiilor incidente pentru fiecare vârf ponderi_vf = {i: [] for i in range(1, n + 1)} # Citim și memorăm ponderile muchiilor în dicționar for i in range(m): vf1, vf2, pondera = muchii[i] ponderi_vf[vf1].append(pondera) ponderi_vf[vf2].append(pondera) # Calculăm media aritmetică a ponderilor pentru fiecare vârf medii_ponderi = {vf: sum(ponderi) / len(ponderi) for vf, ponderi in ponderi_vf.items()} # Găsim vârful cu media minimă vf_min_media = min(medii_ponderi, key=medii_ponderi.get) return vf_min_media # Citirea numărului de vârfuri n = int(input("Introduceți numărul de vârfuri ")) if not (1 <= n <= 100): print("Datele nu corespund restrictiilor impuse") else: # Citirea numărului de muchii m = int(input("Introduceți numărul de muchii: ")) # Citirea muchiilor și ponderilor print("Introduceți extremitățile și ponderea fiecărei muchii:") muchii = [tuple(map(int, input().split())) for _ in range(m)] # Apelarea funcției și afișarea rezultatului rezultat = gaseste_varf_minim_media_ponderilor(n, m, muchii) if rezultat is not None: print(rezultat) </syntaxhighlight>