Exercice Algorithme : Les structures répétitives - Actions Paramétrées - Les chaines
![](/images/thumb/46/default.png)
Exercice (1) : Les structures répétitives
Objectif: Réaliser des Algorithmes en utilisant les structures répétitives
1/
Ecrire un programme mettant en œuvre le jeu suivant :
Le premier utilisateur saisi un entier que le second doit deviner. Pour cela, il a le droit à autant de tentatives qu’il souhaite. A chaque échec, le programme lui indique si l’entier cherché est plus grand ou plus petit que sa proposition.
Un score indiquant le nombre de coups joués est mis à jour et affiché lorsque l’entier est trouvé.
- donner les spécifications
- donner la solution en langage naturel
- indiquer les structures de données
- faites l’algorithme
2/
Ecrire avec la commande POUR un algorithme qui permet de faire la somme d’une suite de nombre entrée par l’utilisateur. Faire la même chose en comptant par pas de –1.
Solution :
1/
Spécifications :
- données : nombre entier
- résultat : nombre de tentatives
Solution en langage naturel : saisir un nombre entier par le premier joueur. Tant que le joueur
2 n saisie, dire si n est > ou < à nombre cherché, incrémenter de 1 et continuer. Quand le résultat est trouvé, afficher le nombre de tentatives.
Structures de données :
- a : nombre saisi par l’utilisateur 1
- n : nombre saisi par l’utilisateur 2
- t : tentatives
Algorithme :
Action : devinette
Var : a, n, t : entiers
Début : Lire (a)
Lire (n)
t=0
Tant que a?n faire
Début
Si n>a alors écrire (« nombre cherché plus petit « )
Sinon écrire (« nombre cherché plus grand »)
t<=t+1
lire (n)
fin
écrire (t+1)
fin
2/
Action :somme_nombre
Var : k, nb, n, somme : entier
Début :
Somme <= 0
Ecrire (« combien voulez-vous entrer de nombres ? »)
Lire (nb)
Pour k de 1 à nb faire
Début
Lire (n)
Somme<=somme + n
Fin
Ecrire (somme)
Fin
Même programme par pas de –1 :
Action : somme_entier
Var : k, nb, n, somme : entiers
Début :
Somme<=0
Ecrire (« combien voulez-vous entrer de nombres ? »
Lire (nb)
Pour k de nb à 1 par pas de –1 faire
Début
Lire (n)
Somme<=somme + n
Fin
Ecrire (somme)
Fin
Exercice (2) : Les structures répétitives
Objectif: Réaliser des Algorithmes en utilisant les structures répétitives
1/
Traduire le POUR de l’algorithme suivant en REPETER JUSQU'A :
Action : bidon
Var : k, nb : entiers
Début
Lire (nb)
Pour k de 1 à nb faire
Ecrire (k)
Fin
2/
Ecrire une fonction qui fait la somme des entiers compris dans un intervalle.
Solution :
1/
Action : Bidon
Var : k, nb : entier
Début
Lire (nb)
K<=1
Si nb>0 alors
Répéter écrire (k)
K<=k+1
Jusqu’à k>nb
Fin
2/
Fonction : intervalle (a, b ; entiers) : entier
Var : k, somme : entier
Début
Somme <= 0
Pour k de a à b faire
Somme<=somme + k
Retourner (somme)
Fin
Exercice (3) : Les Actions Paramétrées
Ex 1
Ecrire une fonction Afficher qui affiche a l’écran le contenu d’un tableau. Ecrire aussi l’action principale qui permettra de comprendre comment fonctionne cette fonction afficher.
{Ne pas oublier d’indiquer les paramètres du tableau !}
Ex 2
Ecrire une fonction qui permet la saisie d’un tableau. Faite aussi l’action principale qui permettra d’accéder a cette fonction saisie mais aussi d’afficher dans un second temps le résultat
Ex 3
Ecrire une fonction qui calcule le nombre d’inversion d’un tableau de taille n (c’est à dire itab[j] pour tout i et j.)
Ex 4
Ecrire une action qui affiche les n premiers éléments de la suite définie par u0=1 et un+1=somme de k=0 jusqu'à n de (uk*un-k)
Aide : stocker les éléments dans un tableau toto avec toto[0]=1. Puis on utilise une boucle
imbriquée pour calculer toto[n+1]=somme k=0 à k=n de toto[k]*toto[n-k].
Solution :
Ex 1
Const : MAX : entier=100
Type : Ttab : Tableau [MAX] d’entier
Fonction Afficher (tab : tableau d’entiers, n entiers)
Var : i entier
Début :
Pour i de 0 à n-1
Ecrire (tab[i], « »)
Fin
Action principale
Var t1 t2 : Ttab
Début
T1[0]<=1
T1[1]<=3
T2[0]<=4
T2[1]<=5
T2[2]<=7
Afficher (T1, 2)
Afficher (T2, 3)
Fin
Résultat à l’écran :
1 3
4 5 7
Ex 2
Fonction : saisie (Stab : tableau d’entiers, N :entier)
Var : i entier
Début :
Pour i de 0 à n-1 faire
Lire (tab[i])
Fin
Action principale
Var : tabl : Ttab
Début
Saisie (toto, 10)
Afficher (toto, 10)
Fin
Ou afficher est la fonction de l’exercice 1.
Ex 3
Fonction inversion (tab : tableau d’entiers, N entier)
Var : j, C, i entiers
Début
C<=0
Pour i de 0 à n-2 faire
Début
Pour j de i+1 à n-1 faire
Si tab[i]>tab[j] alors C<=C+1
Fin
Retourner (C )
Fin
Ex 4
Action Suite (E : d :entier)
Var : toto : Ttab, i, k : entiers
Début :
Toto[0]<=1
Pour I de 1 à d-1 faire
Toto[i]<=0
Pour k de 0 à n-1 faire
Toto[i]<=toto[i]+toto[k]+toto[i-1-k]
Afficher (toto, d)
Fin
Exercice (4) : Les Actions Paramétrées (Suite...)
Voyons maintenant quelques exercices rudimentaires de changements dans un tableau
- Ecrire une action permettant de remplacer toutes les occurrences de x par y dans un tableau de taille n.
- Ecrire un algorithme qui échange les valeurs des cases i et j dans un tableau.
- Ecrire un programme qui inverse un tableau. (Exemple : 1 5 6 7 3 devient 3 7 6 5 1)
Solution :
Var : i :entier
Début
Pour i de 0 à n-1 faire
Si tab[i]=x alors tab[i]<=y
Fin
Action : Echanger (E : i : entier, E : j : entier, ES : tab : tableau d’entier, E : n :entier)
Var : temp
Début
Si i
Temp<=tab[i]
Tab[I]<=tab[j]
Tab[j]<=temp
Fin
Action : inverser (ES : tab : tableau d’entiers, E : n : entier)
Var : i :entier
Début
Pour i de 0 à n/2 – 1 faire
Echanger (i, n-1-in tab, n)
{ou Echanger est la deuxième action de cet exercice}
Fin
Exercice (5) : Les Types Structurés
Ex 1
Ecrire les en-têtes des fonctions/actions suivantes :
- saisie d’un point
- affichage d’un point
- calcul de la distance entre deux points
- projection d’un point sur l’axe des abscisses
Ecrire ensuite les algorithmes de ces fonctions.
Faire une action principale qui demande la saisie de deux points, calcule la distance entre ces deux points et affiche les résultats.
Ex 2
Ecrire un algorithme qui permet de rentrer les données d’un tableau de type TtabVar et dont on connaît la taille.
Ecrire ensuite un algorithme qui permet de rentrer les données d’un tableau de type TtabVar et ou l’on ne connaît pas la taille.
Solution :
Ex 1
Action SaisieTpoint (S : P : Tpoint) {Tpoint a été défini à l’exercice 30}
Début
Lire (P.abs)
Lire (P.ord)
Action AfficherTpoint (E : P : Tpoint)
Début
Ecrire (« ( », P.abs, « ; », P.ord, « ) »)
Fin
Fonction distance (P : Tpoint ; Q : Tpoint) : réel
Var : dist : réel
Début
Dist<=sqrt[(P.abs-Q.abs)² + (P.ord-Q.ord)²]
Retourner (dist)
Fin
Action ProjectionX (ES : P : Tpoint)
Début
P.ord<=0
Fin
Action Principale
Var : P, Q : Tpoint
Dist : réel
Début
SaisieTpoint(P)
SaisieTpoint(Q)
Dist<=distance(P, Q)
Ecrire (« la distance entre »,AfficherTpoint(P), « et », AfficherTpoint(Q), « est », dist)
Fin
Explications 2:
Nous ne rentrerons pas ici le tableau comme nous l’avons fait précédemment :
Nous utiliserons les entités. Ainsi la déclaration se fera de la manière suivante :
Const MAX=100
Type : TtabVar=entité (Tab : tab[MAX] d’entier Taille : entier)
Ainsi, dans une fonction, on aura :
TtabVar : toto
Toto.tab[15]<=1 {pour entrer une valeur de tableau}
Toto.taille++ {On augmente la taille du tableau au fur et a mesure Avantage de cette nouvelle manière d’entrer un tableau : on peu avoir un tableau de taille variable.
Ex 2
Action saisieTtabVar (S : tabvar : TtabVar, E : n : entier)
Var : i : entier
Début
Pour i de 0 à n-1 faire
Lire (tabvar.tab[i])
Tabvar.taille<=n
Fin
Action saisieTtabVar (S tabvar : TtabVar)
Var : réponse : chaîne de caractère
Début
Tabvar.taille<=0
Répéter
Ecrire (« voulez-vous entrer un entier ? »)
Lire (réponse)
Si réponse? « non » alors
Lire (tabvar.tab[tabvar.taille])
Tabvar.taille++
Jusqu’à (réponse= « non » ou tabvar.taille=MAX)
Fin
Exercice (6) : Découpage Fonctionnel
Solution :
![exercice](/images/stories/PHP/exercice.jpg)
On va créer une fonction IndiceEltSup qui cherche la bonne position, une action Insérer qui inclue le nombre entré dans la bonne case du tableau, et une action DécalageDroite qui décale comme dans l’exemple toutes les cases d’un rang vers la droite si nécessaire.
Const MAX=100
Type TtabVar = entité (tab : tableau[MAX] d’entiers, taille : entier)
Fonction IndiceEltSup (tvt : TtabVar, entier, n : entier) : entier
Var : i : entier
Début
Tant que (i?tvt.taille ET tvt.tab[i]<n)
i<=i+1
retourner (i)
Fin
Action DécalageDroite (ES : tvt : TtabVar, E : i : entier)
Var : j : entier
Début
Pour j de tvt.taille – 1 à i par pas de –1 faire
Tvt.tab[j+1]<=tvt.tab[j]
Tvt.taille++
Fin
Action Insérer (ES : tvt : TtabVar, E : i : entier, E : i : entier)
Début
DécalageDroite (tvt, i)
Tvt.tab[i]<=i
Fin
Action SaisieTrié (S : tvt : TtabVar)
Var : rep : chaîne, nb : entier, i : entier
Début
Tvt.taille<=0
Répéter
Ecrire (Rentrer encore un entier ?)
Lire (rep)
Si rep ? « non » alors
Lire (nb)
I<=IndiceEltSup(tvt, nb)
Si non(i
Insérer (tvt, i, nb)
Jusqu’à rep= « non » ou tvt.taille=MAX
Fin
Exercice (7) : Les Chaînes
Ex 1 :
Faire un algorithme qui détermine la longueur d’une chaîne de caractères.
Faire ensuite de deux manières différentes, une fonction qui permet de copier la chaîne d’une source dans une chaîne destination.
Ex 2 :
Faire une fonction de concaténation (ajoute à la fin de la première chaîne de caractères le contenu de la deuxième chaîne de caractères.)
Faire une fonction de Comparaison qui compare deux chaînes de caractères suivant l’ordre lexicographique.
Faire une fonction qui efface une partie de la chaîne en spécifiant une longueur d’effacement et un indice à partir duquel il faut effacer.
Solution :
Ex 1 :
Fonction Longueur (chaine : Tchaine) : entier
Var i : entier
Début
iÍ0
Tant que chaine[ i ] != END faire iÍ i+1
Retourner (i)
Fin
Fonction de copie : première méthode :
Fonction Copier (E : src : Tchaine, S : dest : Tchaine)
Var i, Lsrc : entier
Début
LsrcÍLongueur(src)
Pour i de 0 à Lsrc faire dest[ i ]Ísrc [ i ]
Fin
Fonction de copie : deuxième méthode : plus optimisée :
Fonction CopieOptimisée (E : src : Tchaine, S : dest : Tchaine)
Var i : entier
Début
iÍ0
tant que src[ i ] != END faire
dest [ i ] Í src [ i ]
i Í i+1
dest [ i ] Í src [ i] {pour copier en fin de fichier la sentinelle}
Fin
Ex 2 :
Début
iÍ0
LsrcÍLongueur (src1)
Tant que src2 [ i ] != END
Src1[ Lsrc1+i]Í src2[ i ]
iÍi+1
src1[Lsrc1+i]Ísrc2[ i ]
Fin
Pour faire la fonction comparer, il faut d’abord créer une fonction qui compare les
caractères :
Fonction ComparerChar (char a, char b)
Début
Si a
Si a=b retourner (0)
Si a>b retourner (1)
Fin
On peut maintenant faire la fonction de comparaison de chaînes de caractères qui utilisera la
fonction ComparerChar :
Fonction Comparer (E : src1 : Tchaine, E : src2 : Tchaine)
Var i, L1, L2, cmp : entiers
Début
L1ÍLongueur (src1)
L2ÍLongueur (src2)
IÍ0
Tant que (i
Si i=L1 ou i=L2 alors
Si i
Sinon
Si i
Sinon cmpÍ0
Sinon cmpÍComparerChar(src1[ i ], src2 [ i ])
Retourner (cmp)
Fin
Fonction Effacer (ES : src : Tchaine, E : indice : entier, E : lg : entier)
Var i, Lsrc : entiers
Début
LsrcÍLongueur (src)
Pour i de indice+lg à Lsrc faire
Src[i-lg]Ísrc[ i ]
Fin
Exercice (8) : Les Chaînes (Suite...)
Ecrire l’en-tête d’une action multi décalage à droite qui décale à droite les éléments d’une chaîne à partir d’un certain indice et insère des cases vides à la place. (des actions de multi décalage ont déjà été vue avec les tableaux, on ne demande pas d’en refaire une ici, ce référer aux exercices sur les tableaux)
Faire une action d’insertion. On pourra pour cela utiliser au paravent la fonction multi décalage à droite précédente.
Faire une action de remplacement d’une partie d’une chaîne de caractères par une autre chaîne de caractères dont la longueur n’est pas forcément la même. On pourra utiliser des fonctions des exercices 39 et 40.
Faire une fonction Extraire qui prend une partie de chaîne de caractères à partir d’un certain indice et la met dans une chaîne destination.
Faire une fonction de recherche qui recherche une chaîne dans une chaîne de caractère et retourne un indice si à partir de cette case on a la chaîne cherchée. Sinon, elle retourne –1.
Faire une action qui changent toutes les occurrences d’une chaîne dans une chaîne de caractères par une autre chaîne tampon.
Solution :
Action MultidécalageDroite (ES : src : Tchaine, E : indice : entier, E : lg : entier)
Action Insérer (ES : src : Tchaine, E : indice : entier, E : motif : Tchaine)
Var i, Lsrc, Lmotif : entier
Début
LmotifÍLongueur(motif)
MultidécalageDroite (src, indice, Lmotif)
Pour i de 0 à Lmotif-1 faire
src[indice+i]Ímotif[ i ]
Fin
Action Remplacer (ES : src : Tchaine, E indice : entier, E lg : entier, E : motif : Tchaine)
Début
Effacer (src, indice, lg)
Insérer (src, indice, motif)
Fin
Fonction Recherche (src : Tchaine, motif : Tchaine, Binf : entier)
Var : i, Lsrc, Lmotif : entiers
Tampon : Tchaine
Début
LsrcÍLongueur (src)
LmotifÍLongueur(motif)
iÍBinf
Extraire (src, i, Lmotif, tampon)
Tant que (i
iÍi+1
Extraire (src, i, Lmotif, tampon)
Si non(i=Lsrc – Lmotif) alors retourner (i)
Sinon retourner (–1)
Fin
Action RemplacarToutesChaines (ES : src : Tchaine, E : ancien : Tchaine, E : nouveau :
Tchaine)
Var i , Lancien, Lnouveau, indice :entiers
Début
iÍ0
LancienÍLongueur (ancien)
LnouveauÍLongueur (nouveau)
IndiceÍ Recherche(src, ancien, i)
Tant que indice? -1 faire
Remplacer (src, indice, Lancien, nouveau)
iÍindice+Lnouveau
indiceÍRecherche(src, ancien, i)
Fin