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 1

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