View
213
Download
0
Category
Preview:
Citation preview
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)
2) Pour i de 2 à n faire
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
3) Pour i de 1 à n faire
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
Algorithme de la procédure Remplir
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)
4) Si ( i ≤ n ) alors
Si ( j ≤ n ) alors
Ecrire(m[i,j])
Proc Affich (n,i,j+1,m)
Sinon
Proc Affich (n,i+1,1,m)
Fin si
M. Yassine ELGHARBI 4 SI
Algorithmique et Programmation en Pascal 2
{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)
1) Si ( i ≤ n ) alors
Si ( j ≤ n ) alors
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
Algorithme de la procédure Afficher
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
Solution itérative :
Solution récursive :
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.
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 module utilisé.
Algorithme
Solution itérative :
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
Solution récursive :
Algorithme de la procédure Remplir
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
M. Yassine ELGHARBI 4 SI
Algorithmique et Programmation en Pascal 4
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
Algorithme de la Fonction 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
Algorithme de la Fonction Convb2_b10
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
Algorithme de la Fonction 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
M. Yassine ELGHARBI 4 SI
Algorithmique et Programmation en Pascal 5
0) DEF Proc Convertir( Var TE :tab ;n :octet)
1) Pour i de 1 à n faire
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
M. Yassine ELGHARBI 4 SI
Algorithmique et Programmation en Pascal 6
Algorithme de la procédure Importer
0) DEF Proc Importer(TE : tab ; n :octet ;var F16 :
text)
1) ReCreer( F16 )
2) Pour i de 1 à n faire
Ecrire( F16, TE[i].h )
Fin pour
3) Fermer( f16)
4) Fin Importer
Algorithme de la procédure Afficher
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 :
M. Yassine ELGHARBI 4 SI
Algorithmique et Programmation en Pascal 7
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
Recommended