Nombres qui serpentent⚓︎
On dira d'un entier qu'il serpente si ses chiffres alternent entre croissants et décroissants quand on les lit. Par exemple :
- \(8\), \(90\), \(243\,516\) et \(31\,524\) sont des nombres serpent ;
- \(44\), \(123\) et \(4235\) ne sont pas des nombres serpent.
Objectif : Compter les nombres serpent qui ont \(n\) chiffres, pour \(n\) inférieur à 100. Les zéros de tête sont interdits (sauf pour zéro lui-même) pour les nombres, ainsi \(08\) ne compte pas comme un nombre serpent. Calculer un tableau d'entiers serpent de longueur au moins 100 tel que serpent[n] donne l'effectif des nombres serpent à n chiffres.
Exemples
- Les nombres serpent à 0 chiffre n'existent pas. Il n'y en a aucun ; 0.
- Les nombres serpent à 1 chiffre sont \(0\), \(1\), \(2\), \(\cdots\), \(8\), et \(9\). Il y en a 10.
- Parmi les nombres serpent à 2 chiffres, il y a \(10\), \(12\), \(13\), ..., \(20\), \(21\), \(23\), ..., \(98\). Il y en a 81 : de \(10\) inclus à \(100\) exclu, il y en a 90, auquel on enlève les 9 nombres \(11\), \(22\), ..., \(99\) qui ne sont pas serpent.
- Parmi les nombres serpent à 3 chiffres, il y a \(101\), \(121\), \(120\), ..., \(205\), \(218\), \(230\), ..., \(989\). Il y en a 525.
>>> serpent[0]
0
>>> serpent[1]
10
>>> serpent[2]
81
>>> serpent[3]
525
>>> len(serpent) >= 100
True
serpent = [0, 10]bksl-nl# À compléter avec ou sans fonction...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert serpent[0] == 0bksl-nlassert serpent[1] == 10bksl-nlassert serpent[2] == 81bksl-nlassert serpent[3] == 525bksl-nlassert len(serpent) >= 100bksl-nlbksl-nlserpent = [0, 10]bksl-nlserpentpy-undcroissant = [0] + [1] py-str 9bksl-nlserpentpy-unddecroissant = [0] + [1] py-str 9bksl-nlbksl-nlfor py-und in range(2, 100):bksl-nl newpy-undcroissant = [0] py-str 10bksl-nl newpy-unddecroissant = [0] py-str 10bksl-nl for i in range(10):bksl-nl newpy-undcroissant[i] = sum(serpentpy-unddecroissant[j] for j in range(0, i))bksl-nl newpy-unddecroissant[i] = sum(serpentpy-undcroissant[j] for j in range(i + 1, 10))bksl-nl serpentpy-undcroissant = newpy-undcroissantbksl-nl serpentpy-unddecroissant = newpy-unddecroissantbksl-nl serpent.append(sum(serpentpy-undcroissant) + sum(serpentpy-unddecroissant))bksl-nlbksl-nl
A
On peut remplacer les lignes 6 à 10 par des listes en compréhension.
new_croissant = [sum(serpent_decroissant[j] for j in range(0, i)) for i in range(10)]
new_decroissant = [sum(serpent_croissant[j] for j in range(i+1, 10)) for i in range(10)]
À la suite de quoi, il est possible de se passer des tableaux new_* de manières explicites. Ils seront toutefois toujours créés par Python !!! Le code de la boucle devient alors
for _ in range(2, 100):
serpent_croissant, serpent_decroissant = (
[sum(serpent_decroissant[j] for j in range(0, i)) for i in range(10)],
[sum(serpent_croissant[j] for j in range(i+1, 10)) for i in range(10)],
)
serpent.append(sum(serpent_croissant) + sum(serpent_decroissant))
On a ici un style plutôt fonctionnel très dense.
Pour aller plus loin⚓︎
Ici, on calcule les termes de serpent de proche en proche.
En utilisant du calcul matriciel, ou mieux polynomial, on pourra calculer des termes éloignés de serpent. Il faudra maitriser l'exponentiation rapide et le calcul modulaire.
Z
Indice 1
Si on sait que :
- Il y a \(A\) nombres serpent de taille 20 qui finissent par
0en décroissant. - Il y a \(B\) nombres serpent de taille 20 qui finissent par
1en décroissant. - Il y a \(C\) nombres serpent de taille 20 qui finissent par
2en décroissant. - Il y a \(D\) nombres serpent de taille 20 qui finissent par
3en décroissant. - Il y a \(a\) nombres serpent de taille 20 qui finissent par
0en croissant. - Il y a \(b\) nombres serpent de taille 20 qui finissent par
1en croissant. - Il y a \(c\) nombres serpent de taille 20 qui finissent par
2en croissant. - Il y a \(d\) nombres serpent de taille 20 qui finissent par
3en croissant.
Pouvez-vous déduire la quantité de nombres serpent à 21 chiffres qui finissent par 3 en croissant ?
Solution
Il s'agit de \(A+B+C+D\). En effet, s'il finit par 3 en croissant, c'est qu'avant, c'était 0, 1, 2 ou 3, qu'il était de taille 20 et qu'il finissait en décroissant.
Indice 2
Généraliser une formule qui donne :
- l'effectif des nombres serpent de taille \(n+1\) qui finissent par
ien décroissant ; - l'effectif des nombres serpent de taille \(n+1\) qui finissent par
ien croissant.
Tout cela en fonction des effectifs pour ceux de taille \(n\).
Indice 3
On utilisera deux tableaux :
serpent_croissantde longueur 10, qui indique pour chaque chiffreide 0 à 9, combien de nombres serpent à \(n\) chiffres se finissent parien croissant.serpent_decroissantde longueur 10, qui indique pour chaque chiffreide 0 à 9, combien de nombres serpent à \(n\) chiffres se finissent parien decroissant.
Écrire les instructions qui permettent :
- de construire deux nouveaux tableaux
serpent_croissant_suivantetserpent_decroissant_suivantqui contiennent les effectifs suivants en fonction des précédents. - de remplacer des deux anciens tableaux par les nouveaux.
Indice 4
Écrire l'instruction simple qui calcule et stocke la bonne valeur de serpent[n] en fonction de serpent_croissant et serpent_decroissant.
Indice 5
Initialiser correctement toutes vos variables et mettre en place la boucle qui fait progresser votre problème ; on parle de programmation dynamique.