M. Yassine ELGHARBI 4 SI · M. Yassine ELGHARBI 4 SI Algorithmique et Programmation en Pascal 3 3°) Donner une analyse et l’algorithme du programme principal ainsi que pour chaque

M. Yassine ELGHARBI 4 SI

Algorithmique et Programmation en Pascal 1

Exercice 1 : On vous demande dans cet exercice de proposer une solution récursive sur la manipulation de

matrice

Ecrire un programme qui permet de réaliser les tâches suivantes :

- Saisir la taille de la matrice n. avec 2 ≤ n ≤ 10.

- Initialiser la première ligne et la première colonne de la matrice à la valeur 1.

- Remplir le reste de la matrice par la formule suivante : M ← i*M + j*M

- Calculer et afficher la somme des valeurs de la matrice M.

Questions : 1°) Montrer que le remplissage de la matrice est un traitement récurrent, déterminer son ordre ? 2°) Proposer une décomposition adéquate de ce problème. 3°) Donner les algorithmes du programme principal ainsi que chaque module utilisé.

Algorithme

Solution itérative :

Programme principal

0) Debut Exercice1

1) Procedure saisie(n)

2) Procedure remplir(n,m)

3) Procedure Afficher(n,m)

4) Fin exercice1

Algorithme de la procédure saisie

0) DEF Proc saisie (var n :octet)

1) Repeter

Ecrire(‘’saisir la taille de la matrice’’)

Lire(n)

Jusqu’à (n Dans [2..10])

2) Fin saisie

Algorithme de la procédure initialiser

0) DEF Proc initialiser (n:octet ; var m:matrice)

1) Pour i de 1 à n faire

M[i,1]� 1

M[1,i]� 1

Fin pour

2) Fin initialiser

Algorithme de la procédure Remplir

0) DEF Proc Remplir (n :octet ; var m :matrice)

1) Proc initialiser(n,m)


Pour j de 2 à n faire

M[i,j]� i*M[i-1,j]+j*M[i,j-1]

Fin pour

Fin pour

3) Fin Remplir

Algorithme de la procédure Afficher

0) DEF Proc Afficher (n :octet ; m :matrice)

1) Ecrire(‘’Pour la matrice : ‘’)

2) S�0


Pour j de 1 à n faire

Ecrire(M[i,j])

S�s+M[i,j]

Fin pour

Solution récursive :

Programme principal

0) Debut Exercice1

1) Procedure saisie(n)

2) Procedure remplir(n,m)

3) Procedure Afficher(n,m)

4) Fin exercice1

Algorithme de la procédure saisie

0) DEF Proc saisie (Var n :octet)

1) Ecrire(‘’saisir la taille de la matrice’’)

2) Lire(n)

3) Si ( Non (n Dans [2..10]) ) alors

Proc saisie(n )

Fin si

4) Fin saisie


0) DEF Proc Remplir (n,i,j :octet ; var m :matrice)

1) Si ( i ≤ n ) alors

Si ( j ≤ n ) alors

Si ( i=1 ) ou ( j=1 ) alors

M[i,j] �1

Sinon

M[i,j]� i*M[i-1,j]+j*M[i,j-1]

Fin si

Proc remplir(n,i,j+1,m)

Sinon

Proc remplir(n,i+1,1,m)

Fin si

Fin si

2) Fin Remplir

Algorithme de la procédure Affich

3) DEF Proc Affich (n,i,j :octet ; m :matrice)



Ecrire(m[i,j])

Proc Affich (n,i,j+1,m)

Sinon

Proc Affich (n,i+1,1,m)

Fin si



{retour à la ligne}

Fin pour

4) Ecrire (‘’La somme est égale à ‘’, s)

5) Fin Afficher

Fin si

5) Fin Affich

Algorithme de la fonction S_Mat

0) DEF Fn S_Mat (n,i,j :octet ; m :matrice)



S_mat�M[i,j]+Fn S_Mat(n,i,j+1,m)

Sinon

S_mat�s_mat+Fn S_Mat(n,i+1,1,m)

Fin si

Sinon

S_mat�0

2) Fin S_Mat


0) DEF Proc Afficher (n,i,j :octet ; m :matrice)

1) Ecrire(‘’Pour la matrice : ‘’)

2) Proc Affich (n,i,j,m)

3) Ecrire (‘’La somme est égale à ‘’, Fn

S_Mat(n,i,j,m) )

4) Fin Afficher

Exercice 2 : Soient les deux suites « Un » et « Vn » définis par :

U0 = 1

Un+1 =2*Un + 1

V0 = 2

Vn+1 =3*Un*Vn

Questions :

1°) Montrer que les deux suites sont récurrentes. Quel est l’ordre de récurrence ?

2°) Afficher les « n » premiers nombres de deux suites U et V ; n : entier positif donnée.

3°) Ecrire un module qui permet de vérifier l’assertion suivante : Un < Vn

Algorithme



Exercice 3 : Ecrire une analyse et un algorithme d'un programme intitulé "Conversion" qui permet de créer un

fichier texte intitulé "FB.txt" le remplir par des chaînes binaires. L’entrée d’une chaîne vide arrête la

saisie. Une chaîne binaire est une chaîne non vide qui contient seulement "0" et "1".

Réaliser la conversion du contenu du fichier texte "FB.txt" de la base binaire vars la base

hexadécimale dans un deuxième fichier texte intitulé "FH.txt". (R)

On veut réaliser un tri sur le fichier texte "FH.txt" en suivant la méthode suivante :

- Charger le contenu du fichier "FH.txt" dans un tableau d’enregistrements "TE" à deux champs (le

contenu de chaque ligne du fichier est stocké dans le premier champ de chaque case du tableau) (R)

- Remplir le deuxième champ du "TE" par la conversion, du premier champ, de la base hexadécimale

vers la base décimale.

- Réaliser un tri suivant le deuxième champ du "TE" par la méthode de tri Shell.

- Transférer le contenu du premier champ du "TE" dans le fichier "FH.txt". (R)

- Afficher finalement le fichier texte "FH.txt". (R)

Questions :

1°) Définir les structures de données à utiliser pour résoudre ce problème.

2°) Donner une décomposition adéquate du problème.



3°) Donner une analyse et l’algorithme du programme principal ainsi que pour chaque module utilisé.

Algorithme


Programme principal

0) DEF Exercice3

1) Procedure Creation ( F2, F16 )

2) Procedure Remplir(F2)

3) Procedure transfert(F2,F16)

4) Procedure Exporter(F16,TE,n)

5) Procedure Convertir( TE, n )

6) Procedure Trier(TE,n)

7) Procedure Importer(TE,n,F16)

8) Procedure Afficher(F16)

9) Fin exercice3



0) DEF Proc Remplir (var F2 :text)

1) ReCreer( F2 )

2) Repeter

Ecrire("saisir une chaine binaire")

Lire(ch)

Test� FN Verifier(ch)

Si (Test) alors

Ecrire_nl( F2, Ch )

Fin si

Jusqu’à ( non(test) ou ch="" )

3) Fermer (F2)

4) Fin Remplir

Algorithme de la Fonction Verifier

0) DEF FN Verifier (ch :chaine) :booleen

1) i�1

2) Tant que ( ch[i] dans ["0","1"] ET i≤long(ch) )

FAIRE

i�i+1

fin tant que

Si ( i=long(ch)+1 ) Alors

Verifier� Vrai

Sinon

Verifier� Faux

Fin si

3) Fin Verifier

Algorithme de la Fonction Verifier

0) DEF FN Verifier (ch:chaine; i:octet):booleen

1) Si ( i ≤ long(ch) ) Alors

Si ( ch[i] dans ["0","1"] ) Alors

Verifier� Vrai * Fn Verifier ( ch,i+1 )

Sinon

Verifier� Faux

Fin si

Fin si

2) Fin Verifier

Algorithme de la procédure Transfert

0) DEF Proc transfert( VAR F2,F16 :text )

1) ReCréer( F16 )

2) Ouvrir( F2 )

3) Tant que (Non (Fin_fichier(F2) ) ) Faire

Lire_nl( F2,ch )

Ch� FN Convb2_b16( ch )

Ecrire_nl( F16.H,ch )

Fin Tantque

4) Fermer(F2)

5) Femer(F16)

6) Fin transfert



Algorithme de la Fonction Convb2_b16

0) DEF FN Convb2_b16 (ch :chaine) :chaine

1) Tant que ( Long(ch) MOD 4 ≠ 0 )Faire

Ch�"0"+Ch

Fin tant que

2) Rch�""

3) Tant que (ch ≠ "" ) Faire

s-ch�sous-chaine( ch, 1, 4 )

nb� Convb2_b10( s-ch)

Si ( nb < 10 ) Alors

Convch�Convch( nb, chnb)

Sinon

Chnb�chr( ord("A")+ nb )

Fin si

Efface( ch, 1, 4 )

Rch�Rch + Chnb

Fin Tant que

4) Convb2_b16 � Rch

5) Fin Convb2_b16


0) DEF FN Convb2_b16 (ch :chaine) :chaine

1) Si ( Long(ch) MOD 4 ≠ 0 ) Alors

Ch�"0"+Ch

Fin Si

2) Si (ch ≠ "" ) Alors

s-ch�sous-chaine( ch, 1, 4 )

nb� Convb2_b10( s-ch)

Si ( nb < 10 ) Alors

Convch�Convch( nb, chnb)

Sinon

Chnb�chr( ord("A")+ nb )

Fin si

Efface( ch, 1, 4 )

Convb2_b16�Chnb+Fn Convb2_b16(ch)

Sinon

Convb2_b16� ""

Fin Si

3) Fin Convb2_b16


0) DEF FN Convb2_b10 (ch :chaine) :entier

1) Tant que (ch ≠ "" ) Faire

Val( ch[1], n2, e )

n� n + n2 * Fn Puiss( 2, long(ch) -1 )

Efface( ch, 1, 1 )

Fin Tant que

2) Convb2_b10 � n

3) Fin Convb2_b10


0) DEF FN Convb2_b10 (ch :chaine) :entier

1) Si (ch ≠ "" ) Alors

Val( ch[1], n2, e )

Efface( ch, 1, 1 )

Convb2_b10 � Convb2_b10( Ch ) + n2 *

Fn Puiss( 2, long(ch) )

Sinon

Convb2_b10 �0

Fin Si

2) Fin Convb2_b10

Algorithme de la Fonction Puiss

0) DEF FN puiss (b :octet ;a :entier) :entier

1) R�1

2) Tant que (a ≠ 0 ) Faire

R� r * b

A�a - 1

Fin Tant que

3) puiss � r

4) Fin puiss

Algorithme de la Fonction Puiss

0) DEF FN puiss (b :octet ;a :entier) :entier

1) Si (a ≠ 0 ) Alors

Puiss � b * Fn Puiss( b, a-1 )

Sinon

Puiss � 1

Fin Si

2) Fin puiss

Algorithme de la procédure Exporter

0) DEF Proc Exporter(Var F16 :text ;Var

TE :tab ;n :octet)

1) Ouvrir( F16 )

2) i�0

3) Tant que (Non (Fin_fichier(F16) ) ) Faire

Lire_nl( F16, Ch )

i� i + 1

TE[i].H� Ch

Fin Tantque

4) Fermer( f16)

5) Fin Exporter

Algorithme de la procédure Convertir Algorithme de la procédure Convertir



0) DEF Proc Convertir( Var TE :tab ;n :octet)


Avec TE[i] Faire

D� Fn Convb16_b10 ( H )

Fin Avec

Fin pour

2) Fin Convertir

0) DEF Proc Convertir( Var TE :tab ;n :octet)

1) Si ( n≥1 ) alors

Avec TE[n] Faire

D� Fn Convb16_b10 ( H,1 )

Proc Convertir( TE,n-1 )

Fin Avec

2) Fin Convertir

Algorithme de la fonction Convb16_b10

0) DEF Fn Convb16_b10 (Ch:chaine) : entier

1) N10 � 0

2) Pour i de 1 à Long (ch) Faire

Si Ch[ i ] dans [ ''0''..''9'' ] Alors

Val( ch[ i ], a, e )

Sinon

a <-- Ord( ch[ i ] ) - Ord(''A'') + 10

Fin si

N10<--n10 + a * Fn Puiss( 16, long(ch) – i )

Fin pour

3) Convb16_b10 <-- n10

4) Fin Convb16_b10

Algorithme de la fonction Convb16_b10

0) DEF Fn Convb16_b10 (Ch:chaine,i :entier) :

entier

1) si ( i ≤ long(ch) )alors

Si ( ch[ i ] dans [''0''..''9''] ) alors

Val( ch[ i ], a, e )

Sinon

a<--Ord( ch[ i ] ) - Ord(''A'') + 10

Fin si

Convb16_b10 <-- Fn Convb16_b10 ( ch,

i+1 ) + c * Fn Puiss ( 16, long(ch) – i )

Fin si

2) Fin Convb16_b10

Algorithme de la procédure Trier

0) DEF Proc Trier(Var TE : tab ; n :octet )

1) pas � FN Calcul_pas (N)

2) Répéter

Pour i de pas+1 à N faire

tmp � TE[i]

j�i

Tant que (j-pas >0) et (TE[j-pas].D >tmp.D )

faire

TE[j] � TE[j-pas]

j � j-pas

Fin tant que

TE[j] � tmp

Fin Pour

Pas � pas div 3

Jusqu’à (pas<1)

3) Fin Trier

Algorithme de la procédure Trier

0) DEF Proc Trier( Var TE:tab; n:octet )

1) P� Fn Calcul( n )

2) Proc Tri_Shell( TE, n, 1, p )

3) Fin Trier

Algorithme de la procédure Tri_Shell

0) DEF Proc Tri_Shell ( var TE:tab; n,i,p:octet )

1) Si(p>=1) alors

si(i<=n) alors

tmp<--TE[i]

j<--i

tant que( (j>p) et (tmp.D<TE[j-p].D)) faire

TE[j] <--TE[j-p]

j<--j-p

tant que

TE[j]<--tmp

Tri_Shell (TE,n,i+1,p)

Sinon

p<--p DIV 3

i<--p+1

Tri_Shell (TE,n,i,p)

Fin si

fin si

2) Fin Trier

Algorithme de la fonction calcul_pas

0) DEF Fn Calcul_pas (N:entier) : entier

1) pas � 1

2) Tant que ( 3*pas+1 < N ) faire

pas � pas * 3 + 1

Fin tant que

3) calcul_pas � pas

4) Fin calcul_pas

Algorithme de la fonction calcul_pas

0) DEF Fn Calcul_pas (N:entier) : entier

1) pas � 1

2) Tant que ( pas < n ) Faire

Pas�3*pas +1

Tant que

3) Calcul_pas� pas

4) Fin calcul_pas



Algorithme de la procédure Importer

0) DEF Proc Importer(TE : tab ; n :octet ;var F16 :

text)

1) ReCreer( F16 )


Ecrire( F16, TE[i].h )

Fin pour

3) Fermer( f16)

4) Fin Importer


0) DEF Proc Afficher(Var F16 :text)

1) Ouvrir( F16 )

2) Tant que (Non (Fin_fichier (F16) ) ) Faire

Lire_nl( F16,Enr) {Enr :enregistrement}

Ecrire( E.H )

Fin tant que

3) Fermer( f16)

4) Fin Afficher

Exercice 4 : 1) Proposez un algorithme qui lit un nombre binaire positif N et le convertit dans la base 10.

2) A partir de cette question, le nombre N est exprimé dans la base 10. On cherche à déterminer si

un entier N saisi (N>9) est divisible par 9 ou non en appliquant la méthode suivante :

(i) On fait la somme du premier et du second chiffre de N.

(ii) Si la somme obtenue est supérieure ou égale à 9, on lui soustrait 9.

(iii) On ajoute ensuite à cette somme le chiffre suivant et on lui applique la règle (ii) et ainsi de suite

jusqu’au dernier chiffre de N.

(iv) Si le résultat final est nul alors le nombre est divisible par 9.

Exemple : pour N = 65493, l’algorithme effectuera les opérations suivantes :

6 + 5 = 11 (11 > 9, on lui soustrait 9, on obtient 2)

2 + 4 = 6 (6 < 9)

6 + 9 = 15 (15 > 9, on lui soustrait 9, on obtient 6)

6 + 3 = 9 (9 = 9, on lui soustrait 9, on obtient 0)

Le résultat est nul et tous les chiffres de N ont été traités ; donc le nombre 65493 est divisible par 9.

Algorithme

… …

Algorithme de la procédure Dev9

0) DEF FN Dev9 ( N : entierlong ) :booleen

1) S�0

2) Convch( N, chn )

3) Pour i de 1 à long( chn ) faire

Val( chn[i], c, e )

S� s + c

Si ( s ≥ 9 ) alors

S� s – 9

Fin si

Fin pour

4) Dev9� S = 0

5) Fin Dev9

Algorithme de la procédure Dev9

0) DEF FN Dev9 ( N : entierlong ) :booleen

Exercice 5 :



un nombre est dit super premier et si, en supprimant des chiffres à partir de sa droite ,le

nombre restant est aussi premier.

EXEMPLE: le nombre 59399 est super premier car les nombre 59399,5939,593,59 et 5 sont

tous premier.

Ecrire un programme pascale qui permet de :

*saisir un entier tel que 40000<n>100000.

*cherche tous les nombres premiers inférieur ou égaux à n, les afficher à raison d'un nombre

par ligne en mentionnant devant chaque nombre super premier la note "super premier" et

de faire la même chose dans un fichier texte super_p.txt.

Algorithme

… …

Algorithme de la fonction Premier

0) DEF FN Premier ( N : entierlong ) :booleen

1) S�0

2) Pour i de 1 à N DIV 2 faire

Si ( N MOD i = 0 ) alors

S� s + i

Fin si

Fin pour

3) Premier � S = 1

4) Fin Premier

Algorithme de la fonction Sup_Premier

0) DEF FN Sup_Premier( N : entierlong) :booleen

1) exit� faux

2) repeter

Si ( FN Premier(N) ) alors

N� N DIV 10

Sinon

Exit� vrai

Fin si

Jusqu’à ( exit ) OU ( N=0 )

3) Sup_Premier � N = 0

4) Fin Sup_Premier

Algorithme de la procédure recherche

0) DEF Proc recherche ( N : entierlong ; Var

Sup :text )

1) ReCreer( sup)

2) Pour i de 1 à N faire

Si (Sup_Premier(i) ) alors

Convch( i, ch )

Ch� ch+" super premier"

Ecrire(ch) {retour à la ligne}

Ecrire_nl(sup,ch)

Fin si

Fin pour

3) Fermer (Sup)

4) Fin recherche

Documents

M. Yassine ELGHARBI 4 SI · M. Yassine ELGHARBI 4 SI Algorithmique et Programmation en Pascal 3 3°) Donner une analyse et l’algorithme du programme principal ainsi que pour chaque