Problème 1068
Dans ce pays, tous les nombres sont des entiers positifs dont les chiffres (en numération décimale) sont différents de 0.À chaque nombre de n chiffres, on associe ses (n – 1) « descendants » :
- son fils, formé de tous les chiffres de son père sauf le premier (à gauche)
- son petit-fils, formé de tous les chiffres de son grand-père sauf les deux premiers
- et ainsi de suite...
Un nombre est dit « raffiné » quand il est multiple de son fils.
- 1. Quel est le plus grand nombre raffiné dont tous les descendants d’au moins deux chiffres sont raffinés ? (6 points)
Un nombre est dit « élégant » quand il est multiple de son petit-fils.
- 2. Quel est le plus grand nombre élégant dont tous les descendants d’au moins trois chiffres sont élégants ? (6 points)
Pour ce problème, python est plus pratique à cause des conversions nécessaires entre chaines de caractères et entiers. L'idée est la même pour les deux questions : si on enlève des chiffres à gauche à un nombre vérifiant la condition de la question, il vérifie aussi la question ; donc on peut construire les nombres de cette manière (itérative). Il s'agit donc de maintenir une liste des nombres à examiner, et à tester si la concaténation d'un chiffre à gauche vérifie toujours la condition, auquel cas on ajoute le nombre à la liste des éléments à explorer (deux listes sont utilisées en pratique). Lorsqu'il n'y a plus de nombre dans la liste, cela veut dire que l'on a effectivement explorés tous les nombres vérifiant la contrainte.
Le code est disponible ici.
Le code est disponible ici.
- 1. 95 625
- 2. 81 421 875