MP* Feuille d’exercices d’informatique – Révisions d’algorithmique et de programmation 2019-2020

Pour chacun des programmes suivants, on prouvera la validité de la réponse Arrivez-vous à une complexité en O(N 2 ) ? (Le calcul de la somme des divi-
et on évaluera la complexité dans le pire cas. seurs propres de N a un coût en O(N ).)
Exercice 10 – Multiplication du paysan russe : En s’inspirant de l’algorithme
Exercice 1 : Donner des exemples d’algorithme (de préférence classique) d’exponentiation rapide, écrire un programme russe(a ,b ) qui prend en argu-
dont la complexité est logarithmique (resp. linéaire, en O(n 2 ), O(n 3 ), expo- ment deux entiers naturels a, b et qui renvoie le produit ab en n’utilisant que
nentiel). des additions, des multiplications par 2 et des divisions par 2. Le programme
doit être linéaire en log2 b.
Exercice 2 : Écrire une fonction binom(n,k) qui calcule n
¡ ¢
k pour 0 É k É n.
On cherchera la meilleure complexité possible. Exercice 11 : Que fait le programme suivant ?

Exercice 3 : Écrire un programme somchiffre(n) qui renvoie la somme des 1 def mystere(n):
chiffres décimaux de l’entier n. 2 L=[]
3 d=2
Exercice 4 : Écrire un programme nbchiffre(n) qui renvoie le nombre de 4 a=n
chiffres décimaux de l’entier n. Écrire une variante nbchiffre(n,b) qui renvoie 5 while a>1:
le nombre de chiffre de n dans la base b Ê 2. 6 while a%d != 0 :
7 d= d+1
Exercice 5 : Écrire un programme decomp(n) d’argument un entier stricte- 8 v=0
ment positif n et qui renvoie l’unique couple d’entiers (s, t ) avec t impair tel 9 while a%d == 0:
que n = 2s t . 10 v= v+1
11 a= a//d
Exercice 6 : La suite de Fibonacci est la suite définie par récurrence par
12 L+=[[d,v]]
F 0 = 0, F 1 = 1 et F n+2 = F n+1 + F n pour n Ê 0. Écrire un programme fibo qui
13 return(L)
renvoie le n e nombre de Fibonacci.

Exercice 7 : Écrire un programme nombre_palindrome qui renvoie True si Exercice 12 : Que fait le programme suivant ? Majorer le plus finement pos-
un nombre entier est un palindrome en base 10 et False sinon. (Exemple : sible sa complexité.
1534351 est un palindrome car son écriture est symétrique.) 1 def protocole(n:int):
Écrire un programme palindrome qui renvoie True si une chaîne de caractère 2 L = [ True for k in range(n+1)]
est un palindrome et False sinon. 3 L[0], L[1] = False, False
4 for k in range(2, n+1):
Exercice 8 : Écrire un programme somdivpropre qui calcule la somme des
5 L[k] = True
diviseurs propres (i.e. différents de n) de l’entier n Ê 1. Écrire ensuite un pro-
6 for k in range(2, n+1):
gramme parfait qui renvoie True si n est parfait (i.e. égal à la moitié de la
7 if L[k] == True:
somme de ses diviseurs) et False sinon.
8 j = 2*k
Exercice 9 : Un diviseur d’un entier naturel a est propre s’il est différent 9 while j <= n:
de a. Un couple d’entiers (a, b) est amiable si a est égal à la somme des 10 L[j ] = False
diviseurs propres de b et b la somme des diviseurs propres de a avec a et 11 j += k
b distincts. Écrire un programme amiable d’argument un entier N qui ren- 12 k += 1
voie l’ensemble des couples amiables (a, b) avec a < b É N où N est donné. 13 return L

1
MP* Feuille d’exercices d’informatique – Révisions d’algorithmique et de programmation 2019-2020

Exercice 13 – Golomb : La suite de Golomb est l’unique suite d’entiers crois-

sante (u k )kÊ1 telle que u 1 = 1 et auto-descriptive au sens suivant : u n est le
nombre de fois où l’entier n apparaît dans la suite (u k ).
1. Déterminer les 10 premiers termes de la suite de Golomb.
2. Écrire un programme Golomb(n) qui renvoie la liste des n premiers
termes de la suite de Golomb. (Le slicing est autorisé.)

Exercice 14 – Le problème de Flavius Josephus :

On dispose les n entiers 0, 1, 2, . . . , n − 1 en cercle. On en raye un sur deux
en commençant par le 1. On note J (n) le dernier rayé. Par exemple, J (4) = 0
et J (5) = 2. Écrire un programme Joseph qui renvoie J (n). (Indication : on
pourra utiliser del qui efface un terme d’une liste.)

Exercice 15 : (Difficile) On se donne une liste L d’entiers naturel de longueur

n. Un élément de L est dit prévalent s’il apparait au moins bn/2c + 1 fois dans
L. Écrire un programme prevalent(L) d’argument la liste L et qui renvoie un
élément prévalent s’il existe et None sinon, en O(N ) temporel et O(1) spatial.

2
MP* Feuille d’exercices d’informatique – Révisions d’algorithmique et de programmation 2019-2020

Solutions 6 c += 1
7 return c
Exercice 1. — Pour une complexité logarithmique : la recherche dichoto-
mique dans un tableau trié. Et en base b :
— Linéaire : L’évaluation de P (x) par la méthode de Horner. Ou la re- 1 def nbchiffre(n,b):
cherche du maximum d’un tableau non trié. 2 a=n
— Quadratique : le calcul du produit de deux polynômes par la méthode 3 c=1
standard. 4 while a>b:
5 a = a//b
— Cubique : l’algorithme du pivot de Gauss pour résoudre un système li-
6 c += 1
néaire.
7 return c
— Exponentiel : le test de primalité standard qui consiste à tester les divi-
seurs potentiels. Ou le problème du sac à dos. La terminaison de la boucle while ne pose aucun problème : l’entier k est au
moins divisé par b à chaque étape, jusqu’à tomber sur un nombre de [[0, b −
Exercice 3. Pour les chiffres décimaux : 1]], qui fait sortir de la boucle. Pour la correction, le nombre de chiffre en base
1 def somchiffre(n): b de b c−1 a est un invariant de boucle. Sur l’argument α, il vaut le nombre de
2 a=n chiffre de α à l’entrée dans la boucle, donc aussi en sortie.
3 S=0
Exercice 5. On commence par déterminer s :
4 while a>0:
5 S += a%10 1 def decomp(n):
6 a = a//10 2 k=n
7 return S 3 s=0
4 while k%2==0:
La terminaison vient du fait que dans la seule boucle while, la variable a est 5 s+=1
décroît strictement au cours des appels, sauf quand a = 0 et alors on sort. 6 k//=2
Pour la correction, on dispose de l’invariant de boucle S(a) + S où S(a) est 7 return([s,k])
la somme des chiffres de a. C’est bien un invariant, car entre deux appels
consécutifs de la boucle while, S(a) devient S(a) + r où r est le chiffre des La terminaison de la boucle while ne pose aucun problème : l’entier k est au
unités de a, tandis que a perd son chiffre des unités. La complexité est loga- moins divisé par 2 à chaque étape, jusqu’à tomber sur un nombre impair, qui
rithmique, vu qu’on appelle la boucle while O(ln10 n) fois, et qu’on effectue fait sortir de la boucle. Pour la correction, on dispose de l’invariant de boucle
un nombre fini fixé d’opérations à chaque passage. 2s × k, qui vaut n à l’entrée.

Exercice 4. Pour les chiffres décimaux : Exercice 6. Pour calculer le n e nombre de Fibonacci avec une solution naïve :

1 def nbchiffre(n): 1 def fibo(n):

2 a=n 2 if n== 0:
3 c=0 3 return(0)
4 while a>0: 4 elif n==1:
5 a = a//10 5 return(1)

3
MP* Feuille d’exercices d’informatique – Révisions d’algorithmique et de programmation 2019-2020

6 else: 3 for k in range(l//2):

7 a=0 4 if w[k]!=w[l−k−1]:
8 b=1 5 return(False)
9 for k in range(n−1): 6 return(True)
10 a,b=b,a+b
11 return(b) On prend comme invariant le booléen “w est un palindrome et w[p] = w[l −
1 − p] pour tout p É k” où l est la longueur de w.
Il y a un invariant simple : a = F k et b = F k+1 , qui prouve la correction. La
terminaison d’une boucle for est automatique. Exercice 8. On s’arrête bien entendu
X à n/2 pour trouver les diviseurs
µ ¶ µ ¶ propres. Un invariant est s + k. La correction vient du fait que
u n+2 u n+1 k|n, d +1ÉkÉE (n/2)
On peut faire beaucoup mieux en remarquant que = A où
u n+1 u d augmente strictement et donc dépasse E (n/2) en un nombre fini détapes.
µ ¶ µ ¶ µ ¶ n µ ¶
0 1 u n+1 u1 1
A= . On a donc (récurrence immédiate) que = An =A . 1 def somdivpropre(n):
1 1 un u0 0
2 d=1
Il suffit de calculer A n par exponentiation rapide. Chaque multiplication ma-
3 s=0
tricielle a un coût constant, et on a un nombre d’étape logarithmique en n.
4 while d<=n//2:
D’où une complexité logarithmique en n.
5 if n%d==0:
Exercice 7. L’idée du programme suivant est de retourner l’écriture décimale 6 s+=d
et de comparer ensuite avec l’argument. En notant ret(k) l’entier obtenu en 7 d+=1
inversant les chiffres décimaux de k, on a l’invariant p · ret(k) où · est l’opé- 8 return(s)
rateur de concaténation.
1 def parfait(n):
1 def nombre_palindrome(n):
2 return(n==somdivpropre(n))
2 k=n
3 p=0
4 while k!=0: Exercice 9. On utilise la fonction somdivpropres précédente.
5 r=k%10
1 def amiable(n):
6 p=p*10+r
2 L=[]
7 k=k//10
3 for a in range(1,n+1):
8 if n==p:
4 b=somdivpropre(a)
9 return True
5 if a==somdivpropre(b) and a<b:
10 else:
6 [Link]([a,b])
11 return False
7 return L
On adapte l’algorithme précédent pour une chaîne de caractères. Mais atten-
tion : les chaînes de caractères sont des objets non-mutables (i.e. non modi- L’idée est que si (a, b) est un couple amiable, b est uniquement déterminé
fiable). par a. La solution proposée ne fait intervenir qu’une seule boucle for et à
chaque itération, on appelle deux fois la fonction somdivpropre.
1 def string_palindrome(m):
2 l =len(w) Exercice 10. Le programme suivant convient.

4
MP* Feuille d’exercices d’informatique – Révisions d’algorithmique et de programmation 2019-2020

Vu que n + k − 1 É bn/kc É n/k, on a

1 def russe(a,b):
2 r =0 n
X n
X n
X
3 while b > 0: (n/k − 1) É bn/kc É n/k.
k=2 k=2 k=2
4 if b%2 == 1:
5 r =r +a On e ndéduit que
6 a=a* 2
n
7 b = b // 2 X
4nHn + O(n) É bn/kc É 4nHn + O(n).
8 return r k=2

Terminaison : tant que b est strictement positif, la variable b décroît stricte- En ajoutant les termes O(n) trouvés au début, la complexité du crible d’Éra-
ment. Elle prend donc la valeur 0. On sort alors de la boucle et on effectue le thostène est majorée par un O(n ln n).
return.
Complexité : chaque étape de la boucle while comporte 2 tests et au plus Exercice 13. On se convainc facilement que le deuxième terme de la suite de
3 calculs avec affectations, soit un nombre borné. Or b étant divisé par 2 Golomb ne peut être que 2. En effet, ce n’est pas 1, et si le terme suivant était
à chaque étape, il atteint 0 en log2 b étapes. On a O(ln b) opérations, soit p > 2, il y aurait p fois le terme 2, qui ne peuvent être situés qu’après le 1 par
une compléxité linéaire en la taille de b. (Remarque : on peut optimiser en croissance.
O(min(ln a, ln b)) en utilisant la commutativité.) On met à part les deux cas particulier n = 1 et n = 2. Donc L commence par
Correction : la quantité I = I (r, a, b) = r + ab est un invariant de boucle. En 1, 2, 2. On lit donc sur le début de la liste le nombre de 3 à ajouter, puis le
effet, si à une étape b > 0 est pair, alors la nouvelle valeur de I est r + 2a ∗ nombre de 4, etc. Après les avoir ajoutés, on risque de dépasser n. On enlève
(b/2) = r + ab. De même si b est impair, I devient (r + a) + 2a ∗ (b − 1)/2 = alors les termes surnuméraires.
r + ab. À l’entrée, r vaut 0 et à la fin b est nul. Donc si on appelle (a 0 , b 0 ) les
1 def Golomb(n):
arguments, qui sont donc les valeurs initiales de a et b, r vaut a 0 b 0 à la fin.
2 if n == 1:
Exercice 11. Ce programme renvoie une liste contenant les couples (= liste 3 return [1]
à deux éléments) des diviseurs premiers et leur multiplicité. 4 if n == 2:
5 return [1,2]
Exercice 12. Il s’agit de l’implantation usuelle du crible d’Érathostène qui 6 L = [1,2,2]
renvoie le tableau de booléens P tel que P [k] = True si et seulement si P [k] 7 c=2
est premier. 8 while len(L) < n:
Étudions sa complexité. La création de L et la première boucle for contri- 9 c = c+1
buent chacune pour n − 1 opérations élémentaires. Notons C (n) le nombre 10 nb = L[c−1]
d’opérations élémentaires effectuées dans la seconde boucle pour l’entrée n. 11 L = L + nb *[c]
Dans le pire cas (si L[k] vaut True), dans la seconde boucle for, la boucle while 12 t = len(L)
sera exécutée (p − 1)-fois où p =cn/kb. Chaque passage dans cette boucle 13 for k in range(t−n):
donne lieu à quatre opérations élémentaires (incrémentation de j et test 14 [Link]()
j É n inclus). On a donc 15 return L
n
X n
X
C (n) É 4 (bn/kc − 1) = bn/kc − 4n + 4.
k=2 k=2
Exercice 14. Une première solution :

5
MP* Feuille d’exercices d’informatique – Révisions d’algorithmique et de programmation 2019-2020

On crée une liste L contenant successivement les entiers 0, 1, . . . , n − 1. À

chaque étape, on supprime un élément de L puis on stocke l’indice pe du 1 def Joseph_ter(n):
prochain éliminé dans la liste actualisée L. La terminaison ne pose pas de 2 r=0
problème : on a exactement n − 1 itération de la boucle for. 3 for k in range(2,n+1):
4 r=(r+2)%k
Pour la correction, on constate qu’à chaque étape on supprime l’entier d’in-
5 return(r)
dice pe puis que le prochain éliminé a pour indice
— pe + 1 si pe < len(L) − 1 ; Les deux programmes précédents sont corrects car basés sur la formule de
— 0 si pe = len(L) − 2 (avant-dernier terme) ; récurrence J (k + 1) = J (k) + 2 mod k + 1... qui reste à prouver.
— 1 si pe = len(L) − 1 (dernier terme)
Exercice 15.
car le successeur de L[len(L) − 1] est L[0].

1 def Joseph(n):
2 L=list(range(n))
3 pe=1
4 while len(L)>1:
5 if pe<len(L)−2:
6 del L[pe]
7 pe+=1
8 elif pe==len(L)−2:
9 del L[pe]
10 pe=0
11 else:
12 del L[pe]
13 pe=1
14 return(L[0])

Une deuxième solution, qui ne fait plus jouer de rôle particulier aux deux
derniers indices de la liste. La congruence est clairement adaptée au carac-
tère circulaire du problème.

1 def Joseph_bis(n):
2 L=list(range(n))
3 k=0
4 for i in range(n−1):
5 k=(k+1)%(n−i)
6 del L[k]
7 return(L[0])

Enfin, une solution sans liste ! Seulement des congruences.