Remerciez-le!

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

Informatique UV21 Exercices corrigés sur les boucles Exercice 1 Proposer un alg

Informatique UV21 Exercices corrigés sur les boucles Exercice 1 Proposer un algorithme permettant de tester si une chaîne de caractères (contenue dans une variable s) est un palindrome. Le résultat (vrai/faux) sera stocké dans une variable booléenne b. Un palindrome est une chaîne de caractères qui se lit de la même manière de gauche à droite et de droite à gauche. Par exemple, "kayak" est un palindrome mais "baobab" n’en est pas un. Correction : Analyse : on est donc amené à comparer les lettres d’un mot. Pour "baobab" par exemple, nous comparons la première et la 6eme (et dernière), puis la 2eme et la 5eme, puis la 3eme et la 4eme. Le mot est un palindrome si pour toutes les comparaisons on a la même lettre, ce qui n’est pas le cas pour "baobab". Plus généralement, notons n la longueur (le nombre de lettres) du mot. Il s’agit donc de comparer les lettres de position 1 et n, puis 2 et n-1, puis 3 et n-2, etc. Autrement dit, il s’agit de comparer les lettres de position i et n+1-i pour i=1,2,3,… Question : où faut-il s’arrêter ? Il suffit de s’arrêter « au milieu » du mot. Pour "baobab", qui contient 6 lettres, on s’arrête pour i=3 (comparaison des lettres 3 et 6+1-3=4). Pour "kayak" (de longueur impaire), on s’arrête pour i=2 (comparaison des lettres 2 et 4). Il est donc inutile de comparer quand i dépasse (strictement) n/2. Solution 1 : boucle pour Première variante (la plus naturelle) : on initialise b à vrai, et on le met à faux si l’on trouve une position où le test ne marche pas (le mot n’est pas un palindrome). Deuxième variante (ça marche aussi…) : on compte le nombre de tests qui sont justes. Si tous les tests sont justes on met b à vrai, sinon b vaut faux. Il y a       2 n tests (iquo(n,2) en Maple) – attention à ne pas se tromper avec les cas n pair et n impair... Variante 1 Variante 2 b:=true: n:=length(s): for i from 1 to n/2 do if s[i]<>s[n+1-i] then b:=false: fi: od: print("La réponse est",b); c:=0: n:=length(s): for i from 1 to n/2 do if s[i]=s[n+1-i] then c:=c+1: fi: od: if c=iquo(n,2) then b:=true else b:=false: fi : print("La réponse est",b); Remarques : - on peut faire une boucle de 1 à n (au lieu de n/2), cela marcherait tout aussi bien (en changeant le test en conséquence dans la variante 2). Simplement, on ferait des tests inutiles car on ferait chaque test 2 fois. - Dès que l’on a trouvé un test faux, il est inutile de continuer (le mot n’est pas un palindrome). On pourrait rajouter une instruction break: après b:=false: (version 1). Cette instruction fait « sortir » de la boucle. Là encore, cela économise des tests inutiles. Erreur classique à éviter : Le programme suivant ne fonctionne pas. b:=true: n:=length(s): for i from 1 to n/2 do if s[i]<>s[n+1-i] then b:=false: else b:=true: fi: od: print("La réponse est",b); En effet, si le test est vrai, il ne faut pas remettre b à vrai ! Si b était déjà vrai, ça ne change rien, mais si b était faux, cela signifie qu’un test avait montré que le mot n’est pas un palindrome, b doit rester faux ! Exemple d’exécution avec "rosser". Avant la boucle, b vaut vrai. Quand i=1, on compare les lettres de position 1 et 6, le test est faux et b vaut vrai. Quand i=2, on compare "o" et "e" donc b devient faux. Quand i=3, on compare "s" et "s" donc b redevient vrai ! Solution 2 : boucle tant que Il est également possible d’utiliser non pas une boucle pour mais une boucle tant que. Voici les deux variantes transformées en boucle tant que. Variante 1 Variante 2 b:=true: n:=length(s): i:=1: while i<=n/2 do if s[i]<>s[n+1-i] then b:=false: fi: i:=i+1: od: print("La réponse est",b); c:=0: n:=length(s): i:=1: while i<=n/2 do if s[i]=s[n+1-i] then c:=c+1: fi: i:=i+1: od: if c=iquo(n,2) then b:=true else b:=false: fi : print("La réponse est",b); Remarques : - Ne pas oublier d’initialiser i (i:=1:) et de le mettre à jour à chaque passage dans la boucle (i:=i+1:). - Ne pas mettre la mise à jour (i:=i+1:) dans le test (entre b:=false: et fi:). Il faut mettre à jour à chaque passage. - On pourrait remplacer le test i<=n/2 par (i<=n/2 and b). Cela permettrait de sortir de la boucle quand b est faux et, comme précédemment, d’éviter des tests inutiles. Autre solution : On peut aussi réécrire le mot à l’envers, puis comparer le mot obtenu avec le mot initial. Par exemple, si le mot est "baobab", l’écriture inversée est "baboab". On va alors tester les lettres des mots "baobab" et "baboab" une par une, et répondre faux si une lettre au moins diffère, vrai si toutes les lettres sont les mêmes. s2:="": for i from 1 to length(s) do s2:=cat(s[i],s2): od: b:=true: n:=length(s): for i from 1 to n do if s[i]<>s2[i] then b:=false: fi: od: print("La réponse est",b); La première boucle consiste à créer l’image inversée du mot s (variable s2). Comme précédemment, on pourrait faire en réalité faire une boucle uniquement de 1 à n/2, cela éviterait des tests inutiles. Exercice 2 On considère des dépenses effectuées dans différents postes budgétaires. A chaque dépense est associée le nom du fournisseur, sous forme de liste de deux éléments (nom du fournisseur et montant de la dépense), par exemple [``Dupont'', 877]. Nous considérons alors la liste de ces dépenses, donc une liste de listes LL. Un même fournisseur pourra apparaître plusieurs fois. Par exemple: [["Dupont", 87],["Ets Moulin", 233],["Martin", 877],["Durand", 82],["Dupont", 4269],["Dupont", 321],["Martin", 921]] Donner un algorithme permettant de construire la liste récapitulative contenant les dépenses totales faites auprès de chaque fournisseur, et de l'afficher. Dans l'exemple, cela doit donner:[["Dupont", 4677],["Ets Moulin", 233],["Martin", 1798],["Durand", 82]] Correction : Dans la liste des dépenses, on ne connaît pas ni l’ordre des fournisseurs, ni le nombre de fois ou chacun d’eux apparaît. L’objectif étant de « résumer » la liste (sommer les dépenses pour chaque fournisseur), il faudra prendre en compte chaque sous-liste donc la structure algorithmique à utiliser est une boucle. Il existe plusieurs structures pour faire des boucles. La question à se poser pour choisir concerne la connaissance ou non du nombre de cycles de la boucle. Soit ce nombre est connu et il faudra mettre en œuvre une boucle pour ou ce nombre n’est pas connu et il faudra mettre en œuvre une boucle répéter ou tant que. Dans notre cas, puisqu’on doit prendre en compte chaque sous liste, on connaît le nombre d’itérations, il s’agira d’une boucle pour. On peut donc pour le moment résumer la solution à : > for i from 1 to nops(LL) do # partie relative au traitement du ieme fournisseur de la # liste LL end do; Remarque : 1) le premier élément d’une liste est à la position 1 et le dernier à la position nops(liste). 2) La variable i utilisée dans la boucle ne doit pas être modifiée dans la partie relative au traitement d’un fournisseur. La valeur de cette variable est gérée par la boucle et vous assure d’accéder à tous les fournisseurs. La boucle étant définie, le second problème concerne le traitement de la iéme dépense. Le problème est qu’il faut pour la ième dépense prendre en compte le résultat du traitement des i-1 premières dépenses (pour savoir notamment s’il y a déjà eu des dépenses relatives au fournisseur de la ième dépense). Pour pouvoir le faire, il faut avoir enregistré le résultat des traitements précédents. La seule solution est d’enregistrer les résultats précédents dans une nouvelle liste que nous appellerons resultat. Sur l’exemple, la liste résultat vaudra successivement : - i=1 : [["Dupont", 87]] - i=2 : [["Dupont", 87],["Ets Moulin", 233]] - i=3 : [["Dupont", 87],["Ets Moulin", 233],["Martin", 877]] - i=4 : [["Dupont", 87],["Ets Moulin", 233],["Martin", 877],["Durand", 82]] - i=5 : [["Dupont", 4356],["Ets Moulin", 233],["Martin", 877], ["Durand", 82]] - i=6 : [["Dupont", 4356],["Ets Moulin", 233],["Martin", 1798], ["Durand", 82]] - i=7 : [["Dupont", 4677],["Ets Moulin", 233],["Martin", 1798],["Durand", 82]] Erreur classique : La liste résultat doit être initialisée. La difficulté est de savoir quand cette initialisation doit être faîte. Le code ci-dessous est faux : > for i from 1 to nops(LL) do resultat = [] ; # partie relative au traitement du ieme fournisseur de la # liste LL prenant en compte les résultats des i-1 # fournisseurs enregistrés dans resultat. end do; Quel que soit le traitement dans la partie non encore décrite, cette solution ne peut être que fausse. A toutes les itérations, la variable résultat est initialisée à NULL effaçant le résultat enregistré au cycle précédent. Pour vous en convaincre, il suffit d’afficher la valeur de résultat juste avant end do. > for i from 1 to nops(LL) do resultat = [] ; # Traitement illustratif : resultat := op(resultat), LL[i] ; print(resultat); end do: Dans cet exemple, les uploads/Ingenierie_Lourd/ exercice-s-corrige-s-boucle-s.pdf