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, 10]bksl-nl# À compléter avec ou sans fonction...bksl-nlbksl-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-nlNone
A
Z
Indice 1
Si on sait que :
Il y a \(A\) nombres serpent de taille 20 qui finissent par 0 en décroissant.
Il y a \(B\) nombres serpent de taille 20 qui finissent par 1 en décroissant.
Il y a \(C\) nombres serpent de taille 20 qui finissent par 2 en décroissant.
Il y a \(D\) nombres serpent de taille 20 qui finissent par 3 en décroissant.
Il y a \(a\) nombres serpent de taille 20 qui finissent par 0 en croissant.
Il y a \(b\) nombres serpent de taille 20 qui finissent par 1 en croissant.
Il y a \(c\) nombres serpent de taille 20 qui finissent par 2 en croissant.
Il y a \(d\) nombres serpent de taille 20 qui finissent par 3 en 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 i en décroissant ;
l'effectif des nombres serpent de taille \(n+1\) qui finissent par i en croissant.
Tout cela en fonction des effectifs pour ceux de taille \(n\).
Indice 3
On utilisera deux tableaux :
serpent_croissant de longueur 10, qui indique pour chaque chiffre i de 0 à 9, combien de nombres serpent à \(n\) chiffres se finissent par i en croissant.
serpent_decroissant de longueur 10, qui indique pour chaque chiffre i de 0 à 9, combien de nombres serpent à \(n\) chiffres se finissent par i en decroissant.
Écrire les instructions qui permettent :
de construire deux nouveaux tableaux serpent_croissant_suivant et serpent_decroissant_suivant qui 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.