solEmdS12022-2023

SOLUTION

Exercice No 1: (6 Pts)

Solution 1: en utilisant un Tant Que

Algorithme SommeChiffres;

Var

S, Nbr, chiffre: Entier; // 0.5 pt

chiffre0: Booleen;

Debut

S <--- 0; // 0.5 Pt

chiffre0 <--- Faux;

Tant Que (NON(chiffre0)) Faire // 1 Pt

Repeter

Ecrire("Donner un entier > 0");

Lire(Nbr);

Jusqu'a (Nbr > 0); // 0.5 Pt

// 3 Pt

Tant Que (Nbr > 0) Faire

chiffre <--- Nbr Mod 10;

Si (chiffre = 0) alors

chiffre0 <--- Vrai;

Sinon

S <--- S + chiffre;

Fsi

Nbr <--- Nbr Div 10;

Fait

Ecrire("Somme S = ", S); // 0.5 Pt

Fin.

Solution 2: en utilisant un Repeter

Algorithme SommeChiffres;

Var

S, Nbr, chiffre: Entier; // 0.5 pt

chiffre0: Booleen;

Debut

S <--- 0; // 0.5 Pt

chiffre0 <--- Faux;

Repeter

Ecrire("Donner un entier > 0");

Lire(Nbr);

Jusqu'a (Nbr > 0); // 0.5 Pt

// 3 Pt

Repeter

chiffre <--- Nbr Mod 10;

Si (chiffre = 0) alors

chiffre0 <--- Vrai;

Sinon

S <--- S + chiffre;

Fsi

Nbr <--- Nbr Div 10;

Jusqu'a (Nbr = 0);

Jusqu'a (chiffre0 = Vrai); // 1 Pt

Ecrire("Somme S = ", S); // 0.5 Pt

Fin.

Exercice No 2: (7 Pts)

Algorithme VecteursSMax;

Var

V1: Tableau[100] de Entier; // 0.5 pt

// Attention; Taille de V2 peut presque doubler (V2:Tableau[198] est correct aussi)

V2: Tableau[200] de Entier;

i, J, iDeb, iFin, nb, N, M, SMax: Entier;

Debut

Repeter

Ecrire("Donner N entier avec 2<= N <= 100");

Lire(N);

Jusqu'a ((N >= 2) et (N <= 100)); // 0.25 pt

//1- Remplir Vecteur V1 : 0.5 pt

Pour i <--- 1 a N Faire

Repeter

Lire(V1[i]);

Jusqu'a ((V1[i]>=0) et (V1[i]<=9));

Fait

// 2. Déterminer et afficher la plus grande somme Smax de 2 éléments consécutifs

// de V1 : 1 Pt

// Autre solution: initialiser SMax à (V1[1] + V1[2]) et boucler à partir de 2 dans la boucle Pour

SMax <--- 0;

Pour i <--- 1 a (N - 1) Faire

Si (V1[i] + V1[i+1] > SMax) alors

SMax <--- V1[i] + V1[i+1];

Fsi

Fait

Ecrire("La plus grande Somme de 2 elements consecutifs de V1 est:", SMax);

// 3. Construire un vecteur V2 contenant tous les éléments de V1 qui se suivent et

// dont la somme est égale à Smax: 2 Pts

/* Solution: Parcourir les elements de V1 avec une boucle Pour et si V1[i] + V1[i+1]

est egale à SMax, recopier V1[i] et V1[i+1] dans V2.

J <--- 1;

Pour i <--- 1 a (N - 1) Faire

Si (V1[i] + V1[i+1] = SMax) alors

V2[J] <--- V1[i];

J <--- J + 1;

V2[J] <--- V1[i+1];

J <--- J + 1;

Fsi

Fait

M <--- J - 1;

// ecriture de V2: optionnel

Ecrire("Tableau V2:\n");

Pour i <--- 1 a M Faire

Ecrire(V2[i]);

Fait

// 4. Supprimer de V2 toutes les séquences répétitives consécutives sans utiliser

// un vecteur autre intermédiaire: 3 Pts

// Solution 1: Non Optimisee: Parcourir vecteur V2 avec un Tant Que et si

// V2[i]=V2[i+1] alors supprimer V2[i+1] en decalant les elements se trouvant

// apres la position (i+1) d'une position vers la gauche

i <-- 1;

Tant Que (i < M) Faire

Si (V2[i] = V2[i+1]) alors

// supprimer V2[i+1] en decalant d'une position vers la gauche tous les elements

// de V2 se trouvant apres la position (i+1)

M <--- M - 1;

Pour J <--- i+1 a M Faire

V2[J] <--- V2[J+1];

Fait

// ATTENTION ICI: NE PAS INCREMENTER LE i

Sinon

i <--- i + 1;

Fsi

// Solution 2: Solution Optimisee

// Detecter debut et fin des sequences repetitives et ensuite faire la suppression

i <--- 1;

Tant Que (i < M) Faire

// chercher debut d'une sequence de valeurs successives repetitives

Tant Que ((i < M) et (V2[i] <> V2[i+1])) Faire

i <--- i + 1;

Fait

Si (i < M) alors // on a trouve une sequence de valeurs successives repetitives

J <--- i;

iDeb <--- i;

// chercher fin de la sequence de valeurs successives repetitives

Tant Que ((J < M) et (V2[J] = V2[J+1])) Faire

J <--- J + 1;

Fait

iFin <--- J;

// supprimer tous les elements se trouvant entre iDen et iFin sauf le

// premier (celui se trouvant a la position iDeb)

// supprimer valeurs de (iDeb+1) à iFin en decalant les elements

// de V2 se trouvant de la position (iFin + 1) à la position M de nb elements à la fois

nb <--- iFin - iDeb;

iDeb <--- iDeb + 1;

Pour J <--- iFin+1 a M Faire

V2[iDeb] <--- V2[J];

iDeb <--- iDeb + 1;

fait

M <--- M - nb;

Fsi

Fait

// Solution 3: Solution la plus optimisee

// Une autre solution optimisee encore meilleur est de rechercher les

// sequences de valeurs consecutives repetitives a partir de la fin du tableau et de

// supprimer les sequences au fur et a mesure qu'on les trouve.

i <--- M;

Tant Que (i > 1) Faire

// sauter sequence de valeurs non repetitives

Tant Que ((i > 1) et (V2[i] <> V2[i-1]))

i <--- i - 1;

Fait

Si (i > 1) alors

J <--- i;

iFin <--- i;

Tant Que ((J > 1) et (V2[J] = V2[J - 1])) Faire

J <--- J - 1;

Fait

iDeb <--- j;

// supprimer valeurs de (iDeb + 1) à iFin

nb <--- iFin - iDeb;

iDeb <--- iDeb + 1;

Pour k <--- iFin+1 a M Faire

V2[iDeb] <--- V2[k];

iDeb <--- iDeb + 1;

Fait

M <--- M - nb;

i <--- J - 1; // continuer rechercher prochaine sequence a partir de (j - 1)

Fsi

Fait

// Optionnel: Affichage vecteur V2

Ecrire("Vecteur V2 apres suppression:\n");

Pour i <--- 1 a M Faire

Ecrire(V2[i]);

Fait

Fin.

Exercice No 3: (7 Pts)

Algorithme ChiffresRestantMatrice;

Var

A, AC: Tableau[100,100] de Entier; // 0.25 Pt

V, VC: Tableau[50] de Entier;

N, M, i, J, k, k1, svJ, nb, nbC: Entier;

Debut

// Lecture de N compris entre 2 et 100: 0.25 Pt

Repeter

Ecrire("Donner N entier 2<=N<=100");

Lire(N);

Jusqu'a ((N>=2) et (N <= 100));

// Lecture de M compris entre 2 et 50: 0.25 Pt

Repeter

Ecrire("Donner M entier 2<=M<=50");

Lire(M);

Jusqu'a ((M>=2) et (M <= 50));

// Remplir matrice d'entiers compris entre 1 et 9: 1 Pt

Pour i <--- 1 a N Faire

Pour J <--- 1 a N Faire

Repeter

Ecrire("Donner element A[", i, ",", J, "] compris entre 1 et 9");

Lire(A[i,J]);

Jusqu'a ((A[i,J] >= 1) et (A[i,J] <= 9));

Fait

// initialiser matrice AC a 0: 0.25 Pt

Pour i <--- 1 a N Faire

Pour J <--- 1 a N Faire

AC[i, J] <--- 0;

Fait

// Remplir vecteur V avec nombre de N chiffres Max: 1 Pt

Pour i <--- 1 a M Faire

Repeter

Ecrire("Donner V[", i, "] > 0 et contenant au max ", N, "chiffres");

Lire(V[i]);

Si (V[i] > 0) alors

nbC <--- 0;

nb <--- V[i];

Tant Que(nb > 0) Faire

nbC <--- nbC + 1;

nb <--- nb Div 10;

Fait

Fsi

Jusqu'a ((V[i] > 0) et (nbC <= N));

VC[i] <--- nbC; // sauvegarder nbr de chiffres de V[i] dans VC[i]

Fait

Pour i <--- 1 a M // Parcourir vecteur V : 1 Pt

Faire

nbC <--- VC[i]; // nbr de chiffres de V[i]

// rechercher V[i] dans toutes les lignes de la matrice A: 1 Pt

Pour k <--- 1 a N // Parcourir les lignes de la matrice A

Faire

// ligne k de la matrice A

J <--- N; // j: indice derniere colonne

Tant Que (J >= nbC)

Faire

// chercher le dernier chiffre de V[i] en commencant

// par la derniere colonne J de la ligne k

nb <--- V[i];

c1 <--- nb Mod 10; // c1 dernier chiffre

Tant Que ((J >= 1) et (A[k, J] <> c1)) Faire

J <--- J - 1;

Fait

Si ((J >= 1) et (J >= nbC) ) // on a trouve le dernier chiffre

alors

svJ <--- j; // sauvegarder position ou on a trouve le dernier chiffre

// comparer les autres chiffres

Tant Que ((J >= 1) et (nb <> 0) et (A[k,J] = c1))

Faire

J <--- J - 1;

nb <--- nb Div 10;

c1 <--- nb Mode 10;

Fait

Si (nb = 0) // nbr V[i] se trouve dans la ligne k

alors

// marquer les positions dans matrice AC

Pour k1 <--- svJ-nbC+1 a svJ Faire

AC[k, k1] <--- -1;

Fait

Sinon

J <--- svJ - 1; // recommencer recherche a partir de svJ - 1

Fsi

Fait

// rechercher nb dans toutes les colonnes de la matrice A: 1 Pt

Pour k <--- 1 a N

Faire

// colonne k de la matrice A

J <--- N; // j indice de la derniere ligne de la colonne k

Tant Que(J >= nbC)

Faire

// chercher le derniere chiffre de V[i] a partir de la fin de la colonne k

nb <--- V[i];

c1 <--- nb Mod 10; // dernier chiffre

Tant Que ((J >= 1) et (A[J, k] <> c1)) Faire

J <--- J - 1;

Fait

Si ((J >= 1) et (J >= nbC))

alors

svJ <--- J;

// comparer les autres chiffres

Tant Que((j >= 1) et (nb <> 0) et (A[j, k] = c1))

Faire

J <--- J - 1;

nb <--- nb Div 10;

c1 <--- nb Mod 10;

Fait

Si (nb = 0) // On a trouve V[i] dans la colonne k

alors

// Marquer les chiffres correspondant dams matrice AC

Pour k1 <--- svJ-nbC+1 a svJ Faire

AC[k1, k] <--- -1;

Fait

Sinon

J <--- svJ - 1; // reprendre recherche a partir de svJ - 1

Fsi

Fait

// calculer Nb nombre des chiffres restant: 1 Pt

nb <--- 0;

Pour i <--- 1 a N

Faire

Pour J <--- 1 a N

Faire

Si (AC[i, J] = 0) alors

nb <--- (nb * 10) + A[i, J];

Fsi

Fait

Si (nb = 0) alors

Ecrire("Tous les chiffres de la matrice sont marques");

Sinon

Ecrire("Nombre des chiffres restant = ", nb);

Fsi

Fin.