Noeuds d'un Tas
Résolu/Fermé
A voir également:
- Noeuds d'un Tas
- Google tas - Accueil - Applications & Logiciels
3 réponses
KX
Messages postés
16755
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 février 2025
3 020
26 oct. 2016 à 22:57
26 oct. 2016 à 22:57
Bonjour,
Un tas est forcément complet sur chaque ligne (sauf la dernière)
Donc au maximum sur la première ligne tu as 1=2^0 noeud, la deuxième 2=2^1, troisième 4=2^2, ... ligne h : 2^h noeuds.
Si on fait la somme ça donne 2^(h+1)-1
Quant au minimum, ça se déduit du maximum. Si ton tas de hauteur h est complet avec 2^(h+1)-1 noeuds, alors tu rajoutes 1 noeud, et ça te donne le plus petit tas possible de hauteur h+1 avec 2^(h+1) noeuds
Un tas est forcément complet sur chaque ligne (sauf la dernière)
Donc au maximum sur la première ligne tu as 1=2^0 noeud, la deuxième 2=2^1, troisième 4=2^2, ... ligne h : 2^h noeuds.
Si on fait la somme ça donne 2^(h+1)-1
Quant au minimum, ça se déduit du maximum. Si ton tas de hauteur h est complet avec 2^(h+1)-1 noeuds, alors tu rajoutes 1 noeud, et ça te donne le plus petit tas possible de hauteur h+1 avec 2^(h+1) noeuds
Utilisateur anonyme
26 oct. 2016 à 23:06
26 oct. 2016 à 23:06
Hello,
putain, c'est loin celà !
Un peu de révisions :
https://rmdiscala.developpez.com/cours/LesChapitres.html/Cours4/Chap4.7.htm
A+
putain, c'est loin celà !
Un peu de révisions :
https://rmdiscala.developpez.com/cours/LesChapitres.html/Cours4/Chap4.7.htm
A+