Année académique 2025 - 2026

Algorithmique-programmation 1
Classes Préparatoires aux Ecoles d’Ingénieur (CPEI)

MPSI : Semestre 1

Volume horaire 10 H
Cours Théorique: - H, TD / TP: 10 H

Cours de:
Cheick Amed Diloma Gabriel T RAOR É
[Link]@[Link]
 Sommaire

1 Chapitre premier 1

2 Problèmes de synthèse 2

Bibliographie 10

i
 Chapitre premier
1
Introduksjon
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Ut purus elit, vestibulum ut,
placerat ac, adipiscing vitae, felis. Curabitur dictum gravida mauris. Nam arcu libero,
nonummy eget, consectetuer id, vulputate a, magna. Donec vehicula augue eu neque.
Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis
egestas. Mauris ut leo. Cras viverra metus rhoncus sem. Nulla et lectus vestibulum
urna fringilla ultrices. Phasellus eu tellus sit amet tortor gravida placerat. Integer sapien
est, iaculis in, pretium quis, viverra ac, nunc. Praesent eget sem vel leo ultrices biben-
dum. Aenean faucibus. Morbi dolor nulla, malesuada eu, pulvinar at, mollis ac, nulla.
Curabitur auctor semper nulla. Donec varius orci eget risus. Duis nibh mi, congue eu,
accumsan eleifend, sagittis quis, diam. Duis eget orci sit amet orci dignissim rutrum.

Nam dui ligula, fringilla a, euismod sodales, sollicitudin vel, wisi. Morbi auctor lorem non
justo. Nam lacus libero, pretium at, lobortis vitae, ultricies et, tellus. Donec aliquet, tortor
sed accumsan bibendum, erat ligula aliquet magna, vitae ornare odio metus a mi. Morbi
ac orci et nisl hendrerit mollis. Suspendisse ut massa. Cras nec ante. Pellentesque a
nulla. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus
mus. Aliquam tincidunt urna. Nulla ullamcorper vestibulum turpis. Pellentesque cursus
luctus mauris.

Section a
Publikasjonen har benyttet data fra Norsk pasientregister (NPR). Forfatterne er eneans-
varlig for tolkning og presentasjon av de utleverte data. NPR har ikke ansvar for analyser
eller tolkninger basert på de utleverte data.

Section b

1
 Problèmes de synthèse
2
Exercice 1. La suite de Fibonacci est une suite d’entiers naturels dans laquelle chaque
terme est la somme des deux termes qui le précèdent. On définit cette suite de la
manière suivante : 
F (1) = 1



F (2) = 1


F (n) = F (n − 1) + F (n − 2), ∀n ≥ 3.


Cette suite doit son nom à Leonardo Fibonacci qui exposa le problème de la croissance
d’une population de lapins. Ce problème s’énonce ainsi :
≪ On place un couple de lapins sur une ı̂le ne comportant aucun prédateur.
Combien de couples obtient-on au bout d’un an si chaque couple engendre
tous les mois un nouveau couple à compter du troisième mois de son exis-
tence ? ≫
Si on note F (12) le nombre de couples de lapins au bout d’un an (12 mois) :

F (3) = 1 + 1 = 2,
F (4) = 2 + 1 = 3,
F (5) = 3 + 2 = 5,
F (5) = 3 + 2 = 5,
F (6) = 5 + 3 = 8,
F (7) = 8 + 5 = 13,
F (8) = 13 + 8 = 21,
F (9) = 21 + 13 = 34,
F (10) = 34 + 21 = 55,
F (11) = 55 + 34 = 89,
F (12) = 89 + 55 = 144

Il y aura 144 couples de lapins sur cette ı̂le au bout d’une année.

2
On définit également une deuxième suite telle que :
√
F (n) 1+ 5
R(n) = = ϕ , n ≥ 2 où ϕ = est le nombre d’or.
F (n − 1) 2

Travail demandé
1. De la version itérative et récursive de l’algorithme de Fibonacci qu’elle est la plus
efficiente à programmer? Justifier votre réponse en terme de complexités tempo-
relle et spatiale. (Ecrivez votre réponse en commentaire à la fin du programme
principal.)
2. Écrire une fonction permettant de déterminer les valeurs numériques de F (n) pour
une valeur de n saisie par l’utilisateur.
3. Écrire l’algorithme principal correspondant. Celui-ci:
(a) demandera à l’utilisation de saisir la valeur de n.
(b) Calculera R(n) en appelant F (n).
(c) Affichera les valeurs de F (n) ainsi que de R(n).
4. Programmez vos algorithmes en Python.
5. Quelle conjecture peut-on faire sur la limite de R(n) lorsque n tend vers l’infini ?
Que peut-on en déduire ?
(Ecrivez votre réponse en commentaire à la fin du programme principal.)
Astuce pour la dernière question: tester l’algorithme principal avec plusieurs valeurs de
n et observer les résultats.

Fonctions à utiliser: print(), input() , int(), def(), range()

Exercice 2 (Développement limité de la fonction exponentielle). En mathématiques, la

factorielle d’un entier naturel n, notée n!, est le produit des nombres entiers strictement
positifs inférieurs ou égaux à n.

L’écriture mathématique est la suivante :

n! = n × (n − 1) × (n − 2) × · · · × 2 × 1

Par convention, 0! = 1.

Exemple 5! = 5×4×3×2×1 = 120. La factorielle de 5 exprime, par exemple, le nombre

de combinaisons possibles de placement de 5 convives autour d’une table.

On définit la série numérique suivante :

n
1
un = ∑ k!
k =0

3
Il s’agit de calculer différentes valeurs de cette série un et de conjecturer sa limite
lorsque n tend vers l’infini.

Travail demandé

1. De la version itérative et récursive de l’algorithme de la factorielle, qu’elle est la

plus efficiente à programmer? Justifier votre réponse en terme de complexités
temporelle et spatiale. (Ecrivez votre réponse en commentaire à la fin du pro-
gramme principal.)
2. Écrire une fonction permettant de déterminer la valeur numérique de la factorielle
d’une valeur n saisie par l’utilisateur.
3. Écrire l’algorithme principal correspondant. Celui-ci
(a) demandera à l’utilisation de saisir la valeur de n.
(b) Calculera un en appelant la fonction factorielle. Une programmation naı̈ve du
calcul de un vous conduira à une complexité de O(n2 ) Alors qu’une utilisation
de liste vous donnera une complexité de O(n).
(c) Affichera les valeurs de n et de un en une instruction.
4. Programmez vos algorithmes en Python.
5. Quelle conjecture peut-on faire sur la limite de un lorsque n tend vers l’infini ?

Astuce pour la dernière question: tester l’algorithme principal avec plusieurs valeurs de
n et observer les résultats.

Fonctions à utiliser: print(), input() , int(), def(), range()

Exercice 3 (Étude de nombres rationnels). Un nombre rationnel est un nombre qui

peut s’exprimer comme le quotient de deux entiers relatifs :

p
r= ; p ∈ Z et q ∈ Z
q

Lorsque p et q n’ont pas de diviseurs communs autre que 1, on dit que la fraction est
irréductible. On dit également que ces nombres sont premiers entre eux car ils vérifient
l’égalité :
PGCD( p; q) = 1

où PGCD désigne le Plus Grand Commun Diviseur des entiers p et q.

Le développement décimal d’un nombre rationnel est toujours périodique au bout d’une
certaine décimale. Réciproquement, si un nombre possède un développement décimal
périodique, alors c’est un nombre rationnel.

Exemple r = 1, 12345123451234512345 . . .

4
On écrit les égalités suivantes :

(r − 1) × 105 − 12345 = r − 1
12345
(r − 1) = 5
10 − 1
12345
r = 1+ 5
10 − 1
5
10 − 1 + 12345
r=
105 − 1
112344
r=
99999

Cette fraction n’est pas irréductible car PGCD(112344; 99999) = 3. En divisant le numérateur
et le dénominateur par 3, on obtient :

37448
r=
33333

Travail demandé

1. Soit r un nombre rationnel positif donné, écrire une fonction permettant de déterminer
les deux entiers p et q tels que :

r = p

q
PGCD( p; q) = 1


Il s’agit de créer un programme renvoyant un couple de nombres premiers entre

eux dont le quotient est égal à r. L’utilisateur doit indiquer les deux paramètres
suivants :
— la troncature à l’unité de r ;
— la séquence périodique des décimales.
Exemple : r = 1, 12345123451234512345 . . .
Les paramètres sont dans ce cas : 1 et 12345.
2. Écrire l’algorithme principal correspondant.
3. Programmez vos algorithmes en Python.
4. À l’aide de ce programme, déterminer les entiers p et q dans les cas suivants :
(a) r = 1, 12345123451234512345 . . .
(b) r = 1, 2589258925892589 . . .
(c) r = 0, 369369369 . . .

Fonctions à utiliser : print(), input(), length(), modulus(), range(), eval(), len(),

def().

5
Exercice 4 (Nombres premiers : test de primalité). Un nombre premier est un entier
naturel qui admet exactement deux diviseurs distincts entiers et positifs (lui-même et 1).
Cette définition exclut 1, qui n’est qu’un seul diviseur entier positif. Un nombre non
premier est dit composé. Par exemple 15 = 3 × 5 est composé. L’objectif de ce travail
pratique est de déterminer si un entier naturel n donné est premier.

Théorème (Critère de Primalité): Soit n un entier naturel supérieur ou égal à 2. Si n

√
n’est pas premier, alors il existe un diviseur premier p de n tel que p ≤ n.

Démonstration : Si n n’est pas premier, alors il admet un diviseur premier p tel que
1 < p < n. Dans ce cas p divise n, donc il existe un entier naturel d tel que n = p × d. Si
√ √ √ √
p > n et d > n alors p × d > n, ce qui est impossible, donc p ≤ n ou d ≤ n.
√
Si p ≤ n, le théorème est démontré.
√
Si d ≤ n : on distingue deux cas:
— Soit d est premier et dans ce cas le théorème est démontré;
— Soit d n’est pas premier et dans ce cas il admet un diviseur premier p′ qui est
inférieur à d et le théorème est démontré avec p′ .
On en déduit le corollaire suivant : soit n un entier naturel supérieur ou égal à 2. Si n
√
n’est divisible par aucun nombre premier p inférieur à n, alors n est premier.

Travail demandé
1. Écrire une fonction permettant de déterminer si un nombre n donné est premier.
Il s’agit de créer une fonction estpremier(n) qui renvoie 0 ou True (Vrai) si le
nombre n est premier et 1 ou False (Faux) sinon.
2. Écrire l’algorithme principal correspondant.
3. Programmez vos algorithmes en Python.
4. Application numérique : utiliser la fonction estpremier() pour déterminer si les
nombres suivants sont premiers : 8191, 23245681, 131071 et 8388607.
Fonctions à utiliser: print(); def() ; a%b ; range() ; break ; sqrt() ; int()

Exercice 5 (Ensemble des diviseurs positifs d’un entier naturel). Un diviseur positif d’un
entier naturel n est un entier naturel d tel que la division euclidienne de n par d donne
un reste nul.

Exemple 7 est un diviseur de 42 parce que 42 = 7 × 6 + 0. On dit que 7 divise 42 ou que

42 est divisible par 7. On dit également que 42 est un multiple de 7.
Les diviseurs peuvent être positifs ou négatifs.
Les diviseurs positifs de 42 sont : {1, 2, 3, 6, 7, 14, 21, 42}.

Travail demandé
1. Écrire une fonction permettant de déterminer l’ensemble des diviseurs d’un entier
naturel n donné.

6
 2. Écrire l’algorithme principal correspondant. Celui-ci:
(a) demandera à l’utilisateur de saisir la valeur de l’entier naturel n.
(b) affichera l’ensemble des diviseurs de n.
(c) déterminera si n est premier ou non.
3. Programmez vos algorithmes en Python.
4. Déterminer la liste des diviseurs des entiers suivants 287527 et 29312156.
Fonctions à utiliser print() ; input() ; a%b ; range() ; int() ; def()

Exercice 6 (Identité de Bézout). Soient a et b deux entiers naturels donnés, il s’agit de

déterminer un couple d’entiers relatifs u et v solution de l’équation suivante:

au + bv = PGCD(a; b)

Si PGCD(a; b) = 1 alors on dit que les entiers a et b sont premiers entre eux. Dans ce
cas, les entiers u et v sont également premiers entre eux.

Exemple

On souhaite résoudre l’équation suivante : 875u + 8v = 1.

On écrit les divisions euclidiennes de l’algorithme d’Euclide:

875 = 8 × 109 + 3
8 = 3×2+2
3 = 2×1+1

Il s’agit maintenant d’écrire les égalités en allant de la dernière ligne jusqu’à la première
tout en laissant les nombres 875 et 8 en facteur. On obtient:

1 = 3−2×1
1 = 3 − (8 − 3 × 2) × 1 = 3 × 3 − 8
1 = 3 × (875 − 8 × 109) − 8
1 = 875 × 3 − 3 × 8 × 109 − 8
1 = 875 × 3 − 8 × (3 × 109 + 1)
1 = 875 × 3 − 8 × 328

On obtient ainsi : u = 3 et v = −328.

Les différentes suites utilisées

On se place dans le cas où a et b sont des entiers naturels tels que a > b et on donne
les relations suivantes :
— Suite des restes (rn ), des divisions euclidiennes : r0 = a, r1 = b et rn+1 est le reste
de la division euclidienne de rn−1 par rn pour n ≥ 1.

7
 — Suite des quotients (qn ), des divisions euclidiennes : qn+1 est le quotient de la
division euclidienne de rn−1 par rn pour n ≥ 1.
— Suites des coefficients (un ) et (vn ) : u0 = 1, v0 = 0, u1 = 0, v1 = 1 et pour n ≥ 1:

n+1 = un−1 − qn+1 × un
u
v
n+1 = v −q ×v
n−1 n+1 n

On effectue les calculs des différentes valeurs tant que le reste rn est strictement
supérieur à zéro.

Travail demandé
1. Écrire une fonction permettant de déterminer le couple (u, v) et PGCD(a, b) à
partir de a et b.
2. Écrire l’algorithme principal correspondant. Celui-ci:
(a) demandera à l’utilisateur de saisir les valeurs de a et b.
(b) affichera le PGCD(a, b) et le couple (u, v) solution de l’identité de Bézout.
3. Programmez vos algorithmes en Python.
4. Déterminer un couple d’entiers relatifs u et v dans les cas suivants :
(a) a = 1071 et b = 1029
(b) a = 99 et b = 56
(c) a = 8303 et b = 2717
Fonctions à utiliser: print() ; input() ; def() ; a%b ; int()

Exercice 7 (Algorithme d’Euclide : détermination du PGCD de deux entiers naturels).

Le plus grand commun diviseur, noté en général PGCD, de deux entiers naturels est
le plus grand entier naturel qui divise simultanément ces deux entiers. Par exemple on
écrit : PGCD(42; 56) = 14.

Algorithme d’Euclide

Cet algorithme consiste à effectuer des divisions euclidiennes successives en prenant

comme diviseur, à chaque étape, le reste de la division précédente. Le PGCD est le
dernier reste non nul.

Exemple

Détermination du PGCD de 1071 et de 1029 à l’aide de cet algorithme:

Étape 1 :1071 = 1029 × 1 + 42 (d’où r = 42)

Étape 2 :1029 = 42 × 24 + 21 (d’où r = 21)
Étape 3 :42 = 21 × 2 + 0 (d’où r = 0)

Le dernier reste non nul est 21, donc PGCD(1071; 1029) = 21.

8
Travail demandé
1. Écrire une fonction permettant de calculer le plus grand commun diviseur de deux
entiers naturels a et b donnés.
2. Écrire le l’algorithme principal correspondant. Celui-ci:
(a) demandera à l’utilisateur de saisir les valeurs des deux entiers a et b.
(b) affichera la valeur du PGCD(a, b) en appelant la fonction.
3. Programmez vos algorithmes en Python.
4. Calculer les valeurs suivantes :
(a) PGCD(1071; 1029)
(b) PGCD(150; 75)
(c) PGCD(25411; 11)
Fonctions à utiliser: print() ; input() ; a%b ; int() ; def()

9
 Bibliographie

10