République Tunisienne Niveau : 4ème année Sciences de l’Informatique
Ministère de l’éducation
****** Matière : Algorithmiques et programmation
C.R.E Mahdia - Lycée Secondaire Souassi
Professeur : Abdelkader BARRAJ Date : 27 Janvier 2025 Durée : 1 heure Coefficient : 3
Devoir de Contrôle N° 3
Nom et prénom : ………………………………………………………Note : …...…../20
Exercice 1 (3 points) : Répondre par V (Vrai) ou F (Faux):
1) Un traitement récurrent dépend :
Toujours d’un seul traitement
De zéro traitement précèdent
D’un ou de plusieurs traitement(s) précèdent(s)
U0 = 1
2) Soit la suite U définie par :
Un = 2*Un-1 + n
a. U est une suite récurrente d’ordre : 1 2 3
5 8 9
b. Le 3ème terme de la suite U (U2) est égal à :
c. L’algorithme permettant de calculer Un (avec n >= 1) est :
Fonction terme (n : entier) : entier Fonction terme (n : entier) : entier Fonction terme (n : entier) : entier
Début Début Début
t[0]1 Si n=0 alors Up 1
Pour i de 1 à n-1 faire Retourner 1 Pour i de 2 à n faire
t[i] 2*t[i-1] + n Sinon Up 2*Up + i
Fin pour Retourner 2*terme(n-1) + n Fin pour
Retourner t[n] Fin si Retourner Up
Fin Fin Fin
Exercice 2 (8.5 points) :
Soit la suite ROBINSON définie comme suit :
U0=X (X étant un entier positif donnée)
Un+1= nombre d’apparition de chaque chiffre dans Un
Exemple : Si U0 = 1 alors
U1 = 11 (1 Se répète 1 fois dans U0)
U2 = 21 (1 Se répète 2 fois dans U1)
U3 = 1211 (2 Se répète 1 fois et 1 se répète 1 fois dans U2)
U4 = 3112 (1 Se répète 3 fois et 2 se répète 1 fois dans U3)
U5 = 132112
La1" Iigne dji remplie
(Etc…)
1. Quel est l'ordre de récurrence de cette suite ?
2. Écrire un algorithme d'un module qui,à partir d'un entier positif x , permet de calculer et
afficher les n premières termes de cette suite.
N.B : n et x sont déja saisis dans le programme
----4
appelant.
Page 1 sur 2
Exercice 3 (8.5 points) :
La matrice M suivante représentant les 6 premières lignes du triangle de Leibniz.
0 1 2 3 4 5
0 1/1
1 1/2 1/2
2 1/3 1/6 1/3
3 1/4 1/12 1/12 1/4
4 1/5 1/20 1/30 1/20 1/5
5 1/6 1/30 1/60 1/60 1/30 1/6
Les éléments de la matrice M sont des enregistrements de type FRACTION remplis en suivant le principe ci-après :
Chaque élément de la première colonne et de la diagonale principale est égal à :
1 / L+1 (avec L est le numéro de la ligne).
Chaque autre case de la matrice est égale à la différence entre l’élément du dessus à gauche
(M[L-1,C-1]) et celui à sa gauche sur la même ligne (M[L,C-1])
M[L,C]=M[L-1,C-1]-M[L,C-1]
a c a∗d −(c∗b)
On rappelle que : − =
b d b∗d
x
Pour simplifier une FRACTION c'est-à-dire la rendre irréductible on divise x et y par leur
y
PGCD : PGCD(x,y)
Exemple :M[4,2]=M[3,1]-M[4,1]=
1 1 20 ∗ 1 − (12 ∗ 1) 8 1
− = = =
12 20 12 ∗ 20 240 3O
PGCD (8, 240) = 8 8 Div 8 = 1 et 240 Div 8 = 30
Travail demandé :
Écrire l’algorithme d’un module qui permet de remplir le triangle de Leibniz en utilisant le principe décrit
précédemment .
Page 2 sur 2
C.R.E Mahdia - Lycée Souassi ---- Correction du devoir de contrôle N° 3 ---- 4ème S.I (Algo&prog)
Exercice 1 (3 points) :
1) Un traitement récurrent dépend :
Toujours d’un seul traitement
De zéro traitement précèdent
D’un ou de plusieurs traitement(s) précèdent(s)
U0 = 1
2) Soit la suite U définie par :
Un = 2*Un-1 + n
a. U est une suite récurrente d’ordre : 1 2 3
5 8 9
b. Le 3ème terme de la suite U (U2) est égal à :
c. L’algorithme permettant de calculer Un (avec n >= 1) est :
Fonction terme (n : entier) : entier Fonction terme (n : entier) : entier Fonction terme (n : entier) : entier
Début Début Début
t[0]1 Si n=0 alors Up 1
Pour i de 1 à n-1 faire Retourner 1 Pour i de 2 à n faire
t[i] 2*t[i-1] + n Sinon Up 2*Up + i
Fin pour Retourner 2*terme(n-1) + n Fin pour
Retourner t[n] Fin si Retourner Up
Fin Fin Fin
Exercice 2 (8.5 points) :
Procedure affiche(n:en er,x:en er)
Début
U0convch(x) Objet Type/Nature
Ecrire_nl(U0)
U0,ch,dist Chaine
Pour i de 1 à n-1 faire
i,nb En er
distdis nct(u0),ch’’ ‘’
Occurrences,dist Fonc on
Pour j de 0 à long(dist)-1 faire
nboccurrences(dist[j],U0)
chch+convch(nb)+dist[j]
Fin Pour
U0ch
Ecrire_nl(U0)
Fin Pour
Fin
--------------------------------------------------------------------------------------------------------------------------------
Fonc on dis nct(ch:chaine):chaine
Début
chdist’’ ‘’
Pour i de 0 à long(ch)-1 faire
Si pos(ch[i],chdist)=-1 alors
chdistchdist+ch[i]
Fin Si
Fin Pour
Retourner chdist
--------------------------------------------------------------------------------------------------------------------------------
Fonc on occurrences(c:caractère,ch:chaine) : en er
Début
Nbocc 0
Pour i de 0 à long(ch)-1 faire
Si ch[i]=c alors Objet Type/Nature
NboccNbocc+1 Nbocc,i En er
Fi Si
Fin Pour
Retourner nbocc
Fin
Exercice 3 (8.5 points) :
Procédure remplir(M:mat,n:en er) T.D.N.T
Début Type
Pour L de 0 à n-1 faire
frac on = enregistrement
Pour C de 0 à n-1 faire
num,den :en er
Si C=0 ou L=C alors
fin frac on
M [L, C].num1
mat=tableau de 1000*1000 frac on
M [L, C].denL+1
Sinon Objet Type/Nature
aM[L-1,C-1].num L,C,a,b,c,d En er
bM[L-1,C-1].den frac frac on
cM[L,C-1].num pgcd fonc on
dM[L,C-1].den
frac.num(a*d-c*b)
frac.den(b*d)
frac.numfrac.num div pgcd(frac.num,frac.den)
frac.denfrac.den div pgcd(frac.num,frac.den)
M[L,C].numfrac.num
M[L,C].denfrac.den
Fin Si
Fin Pour
Fin Pour
Fin
--------------------------------------------------------------------------------------------------------------------------------
Fonc on pgcd(a,b) :en er
Début
Si a=b alors
Retourner a
SinonSi a>b alors
Retourner pgcd(a-b,b)
Sinon
Retourner pgcd(a,b-a)
Fin Si
Fin
