0639 – Înălțime: Diferență între versiuni
(Pagină nouă: == Enunț == Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc. Numărul de nivele distincte din arbore determină înălțimea arborelui. = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați înălțimea arborelui. = Date de intrare = Fișierul de intrare <code>inaltimeIN.txt</code> con...) |
|||
Linia 9: | Linia 9: | ||
= Date de ieșire = | = Date de ieșire = | ||
Fișierul de ieșire <code>inaltimeOUT.txt</code> va conține pe prima linie numărul <code>H</code> , reprezentând înălțimea arborelui. | Fișierul de ieșire <code>inaltimeOUT.txt</code> va conține pe prima linie numărul <code>H</code> , reprezentând înălțimea arborelui.Î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 curentă din 27 decembrie 2023 14:54
Enunț
Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul 1
, fiii rădăcinii pe nivelul 2
, fiii fiilor rădăcinii pe nivelul 3
, etc. Numărul de nivele distincte din arbore determină înălțimea arborelui.
Cerința
Se dă vectorul de tați al unui arbore cu rădăcină cu n
noduri. Determinați înălțimea arborelui.
Date de intrare
Fișierul de intrare inaltimeIN.txt
conține pe prima linie numărul de noduri n
. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații.
Date de ieșire
Fișierul de ieșire inaltimeOUT.txt
va conține pe prima linie numărul H
, reprezentând înălțimea arborelui.Î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
- în vectorul de tați rădăcina este marcată cu
0
Exemplu 1:
inaltimeIN.txt
7 4 1 7 0 7 7 1
inaltimeOUT.txt
4
Exemplu 2:
inaltimeIN.txt
101 4 1 7 0 7 7 1
inaltimeOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
def verifica_restrictii(n):
if 1 <= n <= 100:
return True
else:
with open("inaltimeOUT.txt", "w") as file:
file.write("Datele nu corespund restrictiilor impuse")
return False
def calculeaza_inaltimea(n, tati):
if not verifica_restrictii(n):
return
inaltime = 0
nivele = [0] * n
for i in range(n):
nivel = 0
j = i
while tati[j] != 0:
nivel += 1
j = tati[j] - 1
if nivele[j] != 0:
nivel += nivele[j]
break
nivele[i] = nivel
inaltime = max(inaltime, nivel + 1)
with open("inaltimeOUT.txt", "w") as file:
file.write(str(inaltime))
def main():
# Citirea datelor de intrare
with open("inaltimeIN.txt", "r") as file:
n = int(file.readline())
if not verifica_restrictii(n):
return
tati = list(map(int, file.readline().split()))
# Calcularea inaltimii arborelui
calculeaza_inaltimea(n, tati)
if __name__ == "__main__":
main()