Exercice Algorithme : Les Tableaux - Le Tri - Les Fichiers

Exercice (1) : Les Tbleaux

1/

Ecrivez un algorithme qui permette la saisie d’un nombre quelconque de valeurs, sur le principe de l’ex 8 (dans la série Les Tableau (Partie 2)). Toutes les valeurs doivent être ensuite augmentées de 1, et le nouveau tableau sera affiché à l’écran:

2/

Ecrivez un algorithme permettant, toujours sur le même principe, à l’utilisateur de saisir un nombre déterminé de valeurs. Le programme, une fois la saisie terminée, renvoie la plus grande valeur en précisant quelle position elle occupe dans le tableau. On prendra soin d’effectuer la saisie dans un premier temps, et la recherche de la plus grande valeur du tableau dans un second temps.

3/

Toujours et encore sur le même principe, écrivez un algorithme permettant, à l’utilisateur de saisir les notes d'une classe. Le programme, une fois la saisie terminée, renvoie le nombre de ces notes supérieures à la moyenne 

Solution

1/

Variables i, j, N1, N2, S en Numérique
Tableaux T1(), T2() en Numérique
Debut

… On ne programme pas la saisie des tableaux T1 et T2.
On suppose que T1 possède N1 éléments, et que T2 en possède T2)

…
S ? 0
Pour i ? 0 à N1 – 1
Pour j ? 0 à N2 – 1
S ? S + T1(i) * T2(j)
j Suivant
i Suivant
Ecrire "Le schtroumpf est : ", S
Fin
 

2/

Variables Nb, i en Numérique
Tableau T() en Numérique
Debut
Ecrire "Entrez le nombre de valeurs : "
Lire Nb
Redim T(Nb-1)
Pour i ? 0 à Nb - 1
Ecrire "Entrez le nombre n° ", i + 1
Lire T(i)
i Suivant
Ecrire "Nouveau tableau : "
Pour i ? 0 à Nb – 1
T(i) ? T(i) + 1
Ecrire T(i)
i Suivant
Fin

3/

Variables Nb, Posmaxi en Numérique
Tableau T() en Numérique
Ecrire "Entrez le nombre de valeurs :"
Lire Nb
Redim T(Nb-1)
Pour i ? 0 à Nb - 1
Ecrire "Entrez le nombre n° ", i + 1
Lire T(i)
i Suivant
Posmaxi ? 0
Pour i ? 0 à Nb - 1
Si T(i) > T(Posmaxi) alors
Posmaxi ? i
Finsi
i Suivant
Ecrire "Element le plus grand : ", T(Posmaxi)
Ecrire "Position de cet élément : ", Posmaxi
Fin
 

4/

Variables Nb, i, Som, Moy, Nbsup en Numérique
Tableau T() en Numérique
Debut
Ecrire "Entrez le nombre de notes à saisir : "
Lire Nb
Redim T(Nb-1)
Pour i ? 0 à Nb - 1
Ecrire "Entrez le nombre n° ", i + 1
Lire T(i)
i Suivant
Som ? 0
Pour i ? 0 à Nb - 1
Som ? Som + T(i)
i Suivant
Moy ? Som / Nb
NbSup ? 0
Pour i ? 0 à Nb - 1
Si T(i) > Moy Alors
NbSup ? NbSup + 1
FinSi
i Suivant
Ecrire NbSup, " élèves dépassent la moyenne de la classe"
Fin

Exercice (2) : Les Tableaux (Recherche)

Objectif : Testez vos connaissances dans le domaine d'Algorithmique.

Travail à Faire:

Ecrire les Algorithmes permettant de répondre aux questions suivantes :

1. Recherche du plus grand élément d'un tableau
2. Existence d'un élément dans un tableau
3. Recherche d'une valeur dans un tableau
4. Recherche du nombre d'occurrences dans un tableau

Solution :

1. Recherche du plus grand élément d'un tableau :

Algorithme Maximum (t : tableau d'entiers ; n : entier)

{Recherche l'élément le plus grand d'un tableau de taille n non nulle}

Lexique i, max : entier

Début

Max = t [1]

Pour i = 2 à n faire

Si (t[i] > max)

Alors max = t[i]

Fin si

Fin Pour

Afficher

2. Existence d'un élément dans un tableau :

Algorithme Présent (e : entier ; t : tableau d'entiers ; n : entier)

{Indique si l'élément e est présent ou non dans le tableau t }

Lexique i : entier

Début

i = 1;

Tant que (i

i = i+1

Fin tant que

Si (i>n)

Alors Afficher ("l'élément recherché n'est pas présent")

Sinon Afficher ("l'élément recherché a été découvert")

Fin si

Fin

3. Recherche d'une valeur dans un tableau :

t[N] : Tableau d'Entier

v : Entier

i, indice : Entier

trouve : Booleen;

trouve := FAUX

indice = -1

i = 0

tant que non trouve ET i

si t[i] = v alors

trouve = true

indice = i

sinon

i = i+1

finsi

fin tant que

4. Recherche du nombre d'occurrences dans un Tableau : 

t[N] : Tableau d'Entier

v : Entier

i, nb : Entier

nb = 0

pour i de 1 à N

si t[i] = v alors

nb := nb+1

finsi

fin pour

Exercice (3) : Le PGCD

Enoncé de l'Exercice:

Donner l’algorithme qui calcule le PGDC (plus grand diviseur commun).

Exemple : calcul du PGDC des deux nombres 1000 et 24

Pour plus de Simplicité :

À chaque ligne suivante:

1. A prend la valeur de B,
2. B celle de R.

Et, on recommence la division avec ces nouvelles valeurs de B et R.

On s'arrête lorsque R est nul.

Le PGCD est égal au B final.

Solution :

Première Solution:

Fonction Euclide( u : entier v : entier) : entier

Variables

r : entier (* le reste d'une division entière *)

Début

Tant que v 0 faire

r = u mod v

u = v

v = r

Fin Tant que

retourner u

Fin

Variables

u,v : entier (* les deux entiers donnés par l'utilisateur *)

Début

Écrire("Donner les deux nombres : ")

Lire(u,v)

(* Début question subsidiaire *)

si u=0 et v=0 alors Écrire("Le PGCD n'existe pas")

sinon début

si u

si v

Écrire(euclide(u,v))

fin

Fin

Exercice (4) : Palindrome

Enoncé de l'Exercice:

Un palindrome est un tableau de caractères qui se lit de la même façon dans les deux sens (ex : « elle »,« radar », « laval »).
La fonction doit renvoyer 1 si le tableau est un palindrome et 0 sinon.

1. Écrire une fonction qui dit si un tableau est un palindrome.
2. Écrire la même fonction mais cette fois-ci en ajoutant la possibilité d'avoir des espaces et des apostrophesdans le palindrome (ex : « tu l'as trop ecrase Cesar ce port salut ») 
3. Ecrire une Fonction qui teste si un mot est un palindrome.

Solution :

1. Écrire une fonction qui dit si un tableau est un palindrome.

Entier palindrome (entier T[],entier taille)

{

Entier i, j

i= 0

j= taille-1

Tant que i

Si T[i] =T[j]alors

renvoyer0

Sinon

i = i+1

j = j-1

Fin si

Fin tant que

renvoyer1

}

2. Écrire la même fonction mais cette fois-ci en ajoutant la possibilité d'avoir des espaces et des apostrophesdans le palindrome (ex : « tu l'as trop ecrase Cesar ce port salut ») 

Entier Palindrome(entier T[], entier taille)

{

Entier i, j

I = 0

J = taille-1

Tant que i

Si T[i]=’ ’alors

i = i+1

Sinon

Si T[j] ==’ ’alors

j= j-1

Sinon

Si T[i] =T[j]alors

renvoyer0

Sinon

i =i+1

j =j-1

Fin si

Fin si

Fin si

i = i+1

j = j-1

Fin tant que

renvoyer1

}

3. Ecrire l'Algorithme qui teste si un mot est un palindrome.

Exercice (5) : Les Tableaux (Calcule)

Enoncé de l'Exercice:

Ecrire les Algorithmes permettant de faire :

1. Le calcul du produit scalaire de deux vecteurs réels u et v de dimension

2. Ecrire l’algorithme qui calcule le produit de deux matrices carrées réelles

3. Ecrire un algorithme qui calcule le plus grand écart dans un tableau (l’écart est la valeur absolue de la déférence de deux éléments).

4. Le calcul de la moyenne et du minimum des éléments d’un tableau

Solution :

1. Le calcul du produit scalaire de deux vecteurs réels u et v de dimension

Produit_scalaire (u: Tableau d’entiers, v: Tableau d’entiers  n:entier):entier

VAR i, prod_scalaire : entiers

Début

prod_scalaire

Pour i

prod_scalaire

Fin pour

Retourner prod_scalaire;

Fin

2. Ecrire l’algorithme qui calcule le produit de deux matrices carrées réelles

Produit_matriciel (a: Matrice carrée, b: Matrice carrée, n: entier): Matrice carrée

VAR c: Matrice carrée *n

i: entier

Début

Pour i

Pour j de 1 a n Faire

c[i][j]

Pour k de 1 a n Faire

c[i][j]

Fin pour

Fin pour

Fin pour

Retourner c

Fin

3. Ecrire un algorithme qui calcule le plus grand écart dans un tableau (l’écart est la valeur absolue de la déférence de deux éléments).

VAR : min, max, i: entiers

Début

min = t[1]

max = t[1]

Pour i

   Si t[i] > max

Alors

      Max = t[i]

   Fin si

   Si t[i]

Alors

      Min = t[i]

   Fin si

Fin pour

      Return max - min

Fin

4. Le calcul de la moyenne et du minimum des éléments d’un tableau

VAR somme, i: entiers

Moyenne : réel

Début

Somme

Pour i

Somme

Fin pour

Moyenne

Retourner Moyenne

Minimum(T: Tableau d’entier, N: entier):entier

VAR min, i: entiers

Début

min

Pour i

Si T[i]

Alors min =T[i]

Fin si

Fin pour

Retourner min

Fin

Exercice (6) : Le Tri à Bulles

Enoncé de l'Exercice:

• Réaliser l'Algorithme du Tri à Bulles 

Principe de la méthode : Sélectionner le minimum du tableau en parcourant le tableau de la Fin au début et en échangeant tout couple d'éléments consécutifs non ordonnés.

Exemple: 

Solution : 

Exercice (7) : Le Tri par minimum successif

Enoncé de l'Exercice:

Le Tri par minimum successif

Principe

Le tri par minimum successif est ce que l'on appelle un tri par sélection :

Pour une place donnée, on sélectionne l'élément qui doit y être positionné

De ce fait, si on parcourt la tableau de gauche à droite, on positionne à chaque fois le plus petit élément qui se trouve dans le sous tableau droit

Ou plus généralement : Pour trier le sous-tableau t[i..nbElements] il suffit de positionner au rang i le plus petit élément de ce sous-tableau et de trier le sous-tableau t[i+1..nbElements]

Exemple :

Pour trier101, 115, 30, 63, 47, 20[1], on va avoir les boucles suivantes :

i=1101, 115, 30, 63, 47, 20[1]

i=220, 115, 30, 63, 47, 101[1]

i=320, 30, 115, 63, 47, 101[1]

i=420, 30, 47, 63, 115, 101[1]

i=520,30, 47, 63, 115, 101[1]

Donc en sortie :20, 30, 47, 63, 101, 155[1]

Travail à Faire :

1. Créer une fonction qui pour soit capable de déterminer le plus petit élément (en fait l'indice du plus petit élément) d'un tableau à partir d'un certain rang
2. Créer l’algorithme du Tri par minimum successif

Solution :

 1)

Fonction indiceDuMinimum (t : Tableau[1..MAX] d'Entier ; rang, nbElements : Naturel) : Naturel

Déclaration i, indiceCherche : Naturel

Début

   indiceCherche

   Pour i 

      si t[i]

          indiceCherche

      Fin si

       Retourner indiceCherche

    Fin pour

Fin

 2)

L'algorithme de tri est donc :

procédure effectuerTriParMimimumSuccessif (E/S t : Tableau[1..MAX] d'Entier; E nbElements : Naturel)

Déclaration i,indice : Naturel

Début

Pour i

Indice

si i indice alors

echanger(t[i],t[indice])

Fin si

Fin pour

Fin

Exercice (8) : Le Tri Rapide

Principe de la méthode

Choisir un élément du tableau appelé pivot,

Ordonner les éléments du tableau par rapport au pivot

Appeler récursivement le tri sur les parties du tableau à gauche et à droite du pivot.

Travail à Faire :

• Réaliser l’Algorithme du Tri Rapide

Solution : 

Exercice (9) : calcule la surface d’un rectangle

Exercice  (spécifications).

On veut calculer la surface d’un rectangle. 

Phase 1 : Étape de réflexion (conception abstraite).

A partir de l'énoncé on doit définir les flux entrants (les données du problème), les flux sortants (les résultats du problème), et le moyen de passer des uns aux autres.

On détermine aisément le résultat il fait partie de l’énoncé (la surface d’un rectangle), ce qui n’est pas le cas des données.

On va donc mettre en place un calcul permettant de déterminer le résultat (de façon simple) ce qui fera apparaître par décomposition fonctionnelle les données indispensables.

Phase 2 : L'algorithme associé à son lexique (conception concrète).

Exercice (10) : Les Fichiers

Travail à Faire :

• Faire l’algorithme d’une action qui lit un fichier d’entiers et affiche tous les entiers de ce fichier qui sont pairs.
• Ecrire une action qui lit un fichier d’entiers et met dans un autre fichier d’entiers les valeurs paires.
• Faire une fonction qui recherche un entier x dans un fichier d’entiers et retourne vrai si x est dans le fichier.

Rappel:

Pour ouvrir un fichier :

         OuvrirFichier (IdFic, ModeOuverture)

         Avec ModeOuverture = lecture ou écriture ou rajout.

Pour fermer un fichier

         FermerFichier (IdFic)

Pour lire un fichier

        LireFichier (IdFic, élément) cela correspond à Lire(n) Ù cin>>n

Pour écrire un fichier

        EcrireFichier (IdFic, élément) cela correspond à Ecrire(n) Ù cout

Solution :

Action EntierPairs (E : Fic : fichier d’entiers)

Var n : entier

Début

OuvrirFichier (Fic, lecture)

Si EtatFichier (Fic) = succès alors

LireFichier (Fic, n)

Tant que (EtatFichier (Fic) ? FdF) faire {ou FdF signifie Fin de

Fichier}

Si n%2=0 alors Ecrire(n)

LireFichier(n)

FermerFichier (Fic)

Sinon Ecrire (« Erreur, impossible d’ouvrir le fichier en lecture »)

Fin

Action EntiersPairsFichier (E : f1 : fichier d’entiers, ES : f2 : fichier d’entiers)

Var n : entier

Début

OuvrirFichier (f1, lecture)

Si EtatFichier (f1) = succès alors

OuvrirFichier (f2, écriture)

Si EtatFichier (f2) = succès alors

LireFichier (f1, n)

Tant que EtatFichier(f1)?FdF faire

Si n%2=0 alors EcrireFichier(f2, n)

LireFichier (f1, n)

FermerFichier(f2)

Sinon écrire (« Erreur en écriture »)

FermerFichier (f1)

Sinon écrire (« Erreur en lecture »)

Fin

Fonction Recherche (x : entier, f : fichier d’entiers) : booléen

Var bool repÍ false

Début

OuvrirFichier (f, lecture)

Si EtatFichier(f)=succès alors

LireFichier(f, n)

Tant que (EtatFichier(f) ? FdF ET n?x) faire

LireFichier(f, n)

Si n=x alors repÍ true

FermerFichier (f)

Sinon Ecrire (« Erreur en lecture »)

Fin

Exercice (11) : Les Fichiers (suite .)

Travail à Faire :

Faire une action de fusion de deux fichiers d’entiers. Le fichier de sortie doit être trié.

Rappel:

Pour ouvrir un fichier :

        OuvrirFichier (IdFic, ModeOuverture)

        Avec ModeOuverture = lecture ou écriture ou rajout.

Pour fermer un fichier

        FermerFichier (IdFic)

Pour lire un fichier

        LireFichier (IdFic, élément) cela correspond à Lire(n) Ù cin>>n

Pour écrire un fichier

       EcrireFichier (IdFic, élément) cela correspond à Ecrire(n) Ù cout

Solution :

Exercice (12) : Les Fichiers (2)

Soit le type suivant :

             Type : Tetd = entité ( Nom : chaîne

             Numéro : étudiant

             Notes : tableau [5] d’entiers
             
             Moyenne : entier)

On suppose que la fonction de saisie

Fonction SaisieEtd () : Tetd

Permettant de saisir un tableau de Tetd existe. On pourra donc s’en servir

1. Ecrire une fonction qui permet de saisir un groupe d’étudiant dans un fichier.
2. Ecrire une fonction qui permet de calculer la moyenne générale d’un groupe d’étudiant.

Solution :