1651 - Graf: Diferență între versiuni
(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...) |
Fără descriere a modificării |
||
Linia 6: | Linia 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 = |
Versiunea de la data 27 decembrie 2023 14:56
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
, reprezentând muchiile, date prin extremități și pondere.
Date de ieșire
Programul va afișa pe ecran numărul vf
, 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
1 ≤ n ≤ 100
- ponderile muchiilor sunt numere naturale nenule mai mici decât
1000
- 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
1
media este10
- pentru vârful
2
media este4.66667
- pentru vârful
3
media este5
- pentru vârful
4
media este3
- pentru vârful
5
media este6.33333
Astfel media minimă este 3
, pentru vârful 4
Exemplul 2:
Intrare
101
consola
Datele nu corespund restrictiilor impuse
Rezolvare
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)