Exercice Algorithme : Les structures répétitives - Actions Paramétrées - Les chaines

Participez au vote ☆☆☆☆☆★★★★★

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é.

  1. donner les spécifications
  2. donner la solution en langage naturel
  3. indiquer les structures de données
  4. 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

  1. Ecrire une action permettant de remplacer toutes les occurrences de x par y dans un tableau de taille n.
  2. Ecrire un algorithme qui échange les valeurs des cases i et j dans un tableau.
  3. 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 :

  1. saisie d’un point
  2. affichage d’un point
  3. calcul de la distance entre deux points
  4. 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

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