Au premier coup d'œil, cela parait facile...
Mais, il n'en est rien…
J'ai trouvé pour vous un algorithme simple à expliquer… un algorithme qui ne manipule que des nombres entiers … mais qui va mettre à rude épreuve vos capacités à programmer et maitriser vos Calculettes ou Pockets préférés.
Surtout quand il va s'agir d'optimiser et minimiser tout cela.
L'Algorithme de Kaprekar est en réalité très simple, c'est plus un jeu qu'une transformation mathématiques (quoique ?), il réalise une transformation très simple d'un nombre en un autre et peut ainsi se répéter indéfiniment tout en ne manipulant toujours que des nombres entiers et n'utilisant qu'une opération mathématique simple (une sous traction) et un nombre très limité d'étapes dans son déroulement.
Peu d'étapes, des nombres (entier de surcroît), se répétant comme une suite à partir d'un unique argument, …
voilà quelque chose qui convient parfaitement à nos Calculettes, Pockets, ordinosaures ou programmables préférés, …
même aux plus vénérables ...
Il est tellement simple que l'Algorithme de Kaprekar peut être réalisé sur des nombres entiers en base décimale (base naturelle), mais aussi et sans complication ou amendement dans n'importe quelle autre base (binaire,octal, hexadécimal, quelconque b, …)
Pour ne pas nous embrouiller, nous nous contenteront d'appliquer cet excellant algorithme uniquement sur des nombres en base 10. Cela est bien suffisant. Cela évitera de nous fâcher. De plus, cela est compatible avec la très grande majorité des systèmes en nos possessions.
Bon, si certains d'entre vous, dont je connais l'esprit pervers et facessieux, auront besoin, pour implémenter cet algorithme, d'utiliser des ruses, des gruges, ou des chemins scabreux et détournés en exploitant transitoirement d'autres bases… Je les laisse libres de leurs choix, si cela permet de mieux faire… Mais les nombres initiaux utilisés en entrée ou produits en sorties finales ne devrons être qu'en base 10.
Mais je me fais du souci pour rien; l'Algorithme de Kaprekar est si simple que personne, oui vraiment personne, ne songera à empreinter de tels sentiers...
En effet, le but de ce M.P.O. est de produire le code le plus adapté, petit et optimiser pour votre (ou vos) calculatrice(s) ou pocket(s) préféré((e)s) qui permet d'appliquer l'Algorithme de Kaprekar décrit ci-dessous à un nombre donné et d'en afficher (ou imprimer) le résultat de la transformation. Puis, de facilement répéter ce processus en appliquant à nouveau l'Algorithme de Kaprekar sur ce nouveau nombre et ainsi de suite sous l'impulsion de l'utilisateur.
Evidemment, le choix du mode de saisie du nombre et du lancement de l'algorithme de transformation devra être indiqué et adapté à chaque système. L'idéal étant de ne pas avoir à re-saisir les nombres à chaque itération ou re-charger tout le programme à chaque itération.
Enfin, vous comprenez, j'espère, l'itération devra être relancée par un truc simple et efficace, une pression sur R/S, CONT, ENTER ou autre Lbl ou DEF, … ou je ne sais quel bouton ou partie de l'interface homme-machine... Le tout est de bien nous indiquer le procédé qui pourra être spécifique à chaque système mais devra être optimisé et bien pensé.
Vous allez vite voir que nous allons nous chamailler sur d'autres sujets. Car au sein de l'Algorithme de Kaprekar se cache un alien, un vice profond, une source d'ennuis, un Râhu indou, un monstre énorme et tordu, une mission impossible ?
Mais, j'en suis sûr, vous allez me démontrer que je me trompe, et qu'avant septembre, un code MPOïsé existera dans ce fils pour toutes les CASIO, SHARP, HP ou TI et autres Silicium ...
L’Algorithme de Kaprekar transforme un nombre entier en un autre. Il fut découvert en 1949 par le mathématicien indien Dattatreya Ramachandra Kaprekar pour les nombres de quatre chiffres, mais il peut être généralisé à tous les nombres.
Votre code devra donc être particulièrement efficace pour les nombres de quatre chiffres, mais devra être fonctionnel sur des nombres plus petits ou plus grands sans dépasser 10 chiffres cependant.
Il y aura donc deux catégories de codes :
Les codes de Catégorie A qui fonctionnent très bien avec des nombres de 1 à 10 chiffres
Les codes de Catégorie 4 qui fonctionnent exclusivement avec des nombres entiers de 4 chiffres
Tous les codes qui ne pourront être rattachés à l'une ou l'autre de ces deux catégories seront dit 'Hors-Catégorie' ou 'OFF' comme aux festivales.
Votre mission: implémenter de façon optimisée et efficace l'Algorithme de Kaprekar qui se définit comme suit :
L’algorithme de Kaprekar consiste à associer à un nombre quelconque n un autre nombre K(n) généré de la façon suivante :
- on considère un nombre entier n, écrit en base 10 ;
- on forme le nombre c en arrangeant les chiffres du nombre n dans l’ordre croissant
et le nombre d en les arrangeant dans l’ordre décroissant ; - on calcule K(n) = d – c et on affiche ou imprime ce résultat (en base 10);
- on itère ensuite le processus avec K(n) sous l'impulsion déclenchée par l'utilisateur.
Exemples:
Code : Tout sélectionner
En partant du nombre 5294 , on obtient successivement:
K(5294) = 9542 - 2459 = 7083.
K(7083) = 8730 - 378 = 8352.
K(8352) = 8532 - 2358 = 6174.
K(6174) = 7641 - 1467 = 6174 et ainsi de suite.
Code : Tout sélectionner
Si on commence avec 634, on obtient successivement 297, 693, 594, 495, 495, etc.
On obtient là aussi un nombre qui ne varie plus.
EDIT:
Avec 52, la séquence est la suivante : 52, 27, 45, 09, 81, 63, 27…
L'exemple ci-dessus est un mauvais exemple et ne correspond pas à l'algorithme demandé. En effet, 09 n'est pas un nombre à deux chiffres, c'est au mieux un vecteur à deux éléments ou une chaine de caractères. La séquence convenable devient :
Code : Tout sélectionner
Avec 52, la séquence est la suivante : 52, 27, 45, 9, 0, 0, 0…
Préparez vite vos codes, nous allons débusquer tous les Râhu et faire d'étranges découvertes…