Aller au contenu

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.
🐍 Console Python
>>> serpent[0]
0
>>> serpent[1]
10
>>> serpent[2]
81
>>> serpent[3]
525
>>> len(serpent) >= 100
True
###
# testsbksl-nlbksl-nlassert serpent[0] == 0bksl-nlassert serpent[1] == 10bksl-nlassert serpent[2] == 81bksl-nlassert serpent[3] == 525bksl-nlassert len(serpent) >= 100bksl-nlbksl-nl# autres testsbksl-nlbksl-nlSERPENT = [0, 10, 81, 525, 3105, 18939, 114381, 693129, 4195557, 25405586, 153820395, 931359050, 5639156409, 34143908573, 206733865761, 1251728824798, 7578945799704, 45888871327435, 277847147039527, 1682304127857000, 10185986079451152, 61673933253012813, 373422269794761171, 2260990733622821388, 13689807788336374413, 82888812632681299575, 501873756436963255725, 3038736584593404112888, 18398889984004648394684, 111401282480312690455535, 674510568248786542723384, 4084014982140900066996999, 24727823639079446292398973, 149721601071325722314771768, 906531773865227322540527599, 5488852985453577921599786404, 33233812608096915187160862646, 201223516716003090938495558273, 1218364686502763138912251531858, 7376933539095247157524690209596, 44665730255556705813455277892969, 270441294975640547699726057576357, 1637463299259559727190050998356877, 9914484608068134973197170061461591, 60030050803623279460905640700537146, 363468918651916171818101177606787775, 2200725354342352358032848391711429287, 13324914006975819086503546268399064826, 80679460043917672551257824285696701631, 488496606399894533135228090580518726849, 2957740846732444497653596441045121744779, 17908478384122192100208036703515396114945, 108431946763990227509406490644619239949670, 656531885447794265344437789229847771602593, 3975157962881656804262109523464275982054206, 24068718032001765864399208734778590812059100, 145730859783006115692556683131127947572716351, 882368702182510621630923925514359365784813975, 5342550834809792396806303497681900898790602948, 32347984863840919439702872508060799643996329921, 195860022132767463457194622209195721131511619393, 1185889891791338408154534460189644031233260498090, 7180305710879381718473109708289839840279416225259, 43475191464705279658821205861906473192979193394551, 263232841190727052129577046753774486800584662952576, 1593817677320544472069315699698021405961289198127352, 9650219847374200686866980990825185077113651584259915, 58429985077851243131664519519650782811471472008138262, 353780868228289794214717741134865565936022487352042972, 2142066313342370732999494929764219945531265582381574084, 12969746254891643527206138735713153473581856857600095022, 78528996450069182818170035206950924986262776615228842359, 475476016435488792922724897174988743962786201248439181821, 2878904002664891282213725487897616787658753354127999437145, 17431138417229580981375607929954799920484191208458836849334, 105541756946171068442094408895636846737397539224743995138242, 639032413871166799425569675259991298503891964738270377571646, 3869202463497791194390022403538813795184824191022263105120261, 23427180497538227918384894216032536344822982120913486859005897, 141846489358451945872383596558786903972944914449980284295419669, 858849682975367577620868729238136646340508021279438150851189203, 5200148282012719554761322719583518251776093190150646249093143114, 31485768337525729063232789086930259474485679688747287900236134643, 190639488345634999172037991756500352751157724547714851328253128848, 1154280693648192732866441010454314021643048294494184927145989749181, 6988918881870570231769912232187671511248169744379692168541703509970, 42316385785669385595814350388619174876388240296223393673888607531882, 256216524505193716144733781060865175999482846906506651739660845744675, 1551335403784699437467403137673555159940026653854455786424502055338943, 9392998908573720332591434332116379298964835183480715231431284456457957, 56872568163674679661793660628819558901413442844685202596077017341738809, 344351047095241664581365027406377518948639259453576986455463834228076289, 2084970794607558707929544265766774574113298602455891036247922071247187506, 12624045290514652253974190059423751220374380450784779710821698749343369568, 76435852199532490537114357525478173578997382169325263461986888368804125371, 462802482644657363293397846264195190536976947251737947227949204965780224431, 2802168508345203224585165008456703166541527129222571530462213246984687687723, 16966521666631831399368304014981269907585511181598421802474676023379660074148, 102728603439442098192781482549970023263233791039643568211308707933725742061091, 621999380425342872846895049949523920352287482295049627234230430671848280308249]bksl-nlbksl-nlfor n, attendu in enumerate(SERPENT):bksl-nl assert serpent[n] == attendu, f"Erreur pour n = {n}"bksl-nlbksl-nl ∞/∞

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.

Retour en haut de la page