Devoir pratique n°6 : nombres de Kaprekar et recherche dichotomique dans leur liste

Exercice 1 : les nombres de Kaprekar (8 pts)

Un entier n ≥ 1 de k chiffres est un nombre de Kaprekar si, quand on coupe n² en une partie droite de k chiffres et une partie gauche, la partie droite n'est pas nulle et la somme des deux parties est n. Exemples : 45² = 2025 et 20 + 25 = 45 ; 297² = 88209 et 88 + 209 = 297 ; 9² = 81 et 8 + 1 = 9. 10 n'en est pas un : 10² = 100 donne 1 + 00, la partie droite est nulle.

• 1) Créer un programme Python et l'enregistrer sous le nom Kaprekar.py (1 pt).
• 2) Écrire la fonction Kaprekar(n) qui renvoie Vrai si n est un nombre de Kaprekar, Faux sinon (4 pts).
• 3) Écrire le programme principal en Python qui lit n (1 ≤ n ≤ 99999, saisie contrôlée) puis affiche « n est un nombre de Kaprekar » ou « n n'est pas un nombre de Kaprekar » (3 pts).

Exemple : pour 297, le programme affiche :

297 est un nombre de Kaprekar

Exercice 2 : chercher dans la liste des nombres de Kaprekar (12 pts)

On veut ranger dans un tableau T les n premiers nombres de Kaprekar (2 ≤ n ≤ 10), trouvés avec la fonction Kaprekar de l'exercice 1, puis dire si un entier x est l'un d'eux, et lequel, par recherche dichotomique. T est rangé dans l'ordre strictement croissant : on essaie les entiers 1, 2, 3… dans l'ordre.

On recopie dans ce programme la fonction Kaprekar de l'exercice 1.

• 1) Créer un programme Python et l'enregistrer sous le nom ListeKaprekar.py (1 pt).
• 2) Écrire la procédure Construire(T, n) qui range dans T les n premiers nombres de Kaprekar, en appelant Kaprekar (4 pts).
• 3) Écrire la fonction Dicho(T, n, x) qui renvoie l'indice de x dans T trouvé par recherche dichotomique, ou -1 si x n'est pas dans T (4 pts).
• 4) Écrire le programme principal en Python qui lit n (saisie contrôlée) et x, construit T puis affiche le rang de x parmi les nombres de Kaprekar ou un message, sous la forme des exemples (3 pts).

Les dix premiers nombres de Kaprekar sont 1, 9, 45, 55, 99, 297, 703, 999, 2223 et 2728. Exemples : pour n = 6 et x = 297, le programme affiche « 297 est le nombre de Kaprekar numéro 6 » ; pour n = 6 et x = 703, il affiche :

703 n'est pas parmi les 6 premiers nombres de Kaprekar

Correction détaillée

Sujet original écrit pour Mission Carthage, dans le format d'un devoir pratique d'informatique (3ème Sciences de l'informatique). Ce n'est pas un sujet officiel.

Tout le programme : 3ème année Sciences de l'informatique · Revoir le cours · Tous les devoirs