Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Pilesfiles td corrige pdf TD ?? Piles et ?les Corrigé Piles Exercice N ?? Copie d ? une pile Ecrire une fonction stackcopy s recevant une pile s comme argument et renvoyant une copie s de s Attention la pile s doit bien sûr être conservée Evaluer le coût

TD ?? Piles et ?les Corrigé Piles Exercice N ?? Copie d ? une pile Ecrire une fonction stackcopy s recevant une pile s comme argument et renvoyant une copie s de s Attention la pile s doit bien sûr être conservée Evaluer le coût en mémoire et le nombre d ? opérations de la fonction Puisque dans une pile nous ne pouvons manipuler que le sommet de la pile nous n ? avons pas d ? autre choix pour pouvoir accéder aux éléments successifs de s que de la dépiler dans un premier temps ère boucle for ci-dessous ? def stackcopy s s stackcreate if len s t stackcreate for i in range len s e stackpeek s stackpop s stackpush t e for i in range len t e stackpeek t stackpop t stackpush s e stack push s e return s Notons n la taille de l ? espace mémoire occupé par la pile s A priori la fonction stack pop libère progressivement l ? espace mémoire occupé par s Mais parallèlement on construit la pile t Ainsi l ? espace mémoire total requis par les piles s et t dans la première boucle for est constant et égal à n Dans la deuxième boucle for on vide la pile t mais on construit au fur et à mesure les piles s et s Ainsi l ? occupation mémoire lors de l ? exécution de la deuxième boucle passe de n à Fénelon Sainte-Marie PC PSI - - Marc Lichtenberg CTD ?? Piles et ?les Corrigé n Bien sûr si on ne souhaite pas conserver s cette occupation est à nouveau égale à n on dépile t pour construire s Pour ce qui est des appels à des fonctions on se limite aux fonctions stackpeek stackpop et stackpush Dans la première boucle for on a n appels à chacune des fonction stackpeek stackpop et stackpush Dans la seconde boucle for on a n appels à chacune des fonction stackpeek et stackpop et n appels à la fonction stackpush En dé ?nitive on a ? n appels à la fonction stackpeek ? n appels à la fonction stackpop ? n appels à la fonction stackpush Si on ne souhaite pas conserver s on ne reconstruira pas cette pile dans la deuxième boucle for et on aura seulement ? n appels à la fonction stack push pour un total de n appels au lieu de n Exercice N ?? Inversion d ? une pile Ecrire une fonction stackreverse recevant une pile s comme argument et renvoyant une copie inversée rs de s Attention la pile s doit être conservée Evaluer le coût en mémoire et le nombre d ? opérations de la fonction Dans l ? écriture de la fonction précédente on a vu que la première boucle for permettait d ? obtenir une nouvelle pile inverse de la pile initiale MAIS en lieu et place de celle-ci Pour conserver cette pile initiale il su ?t donc dans un