Aller au contenu

Nombre serpent

Le cadre

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.

⚠ 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 autre nombre serpent.

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.

Exercice

Coder une fonction serpent qui prend un entier positif en argument et qui renvoie l'effectif des nombres serpent à n chiffres.

On pourra utiliser de la mémoïsation pour stoker des résultats intermédiaires.

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 \(e\) nombres serpent de taille 20 qui finissent par 0 en croissant.
  • Il y a \(f\) nombres serpent de taille 20 qui finissent par 1 en croissant.
  • Il y a \(g\) nombres serpent de taille 20 qui finissent par 2 en croissant.
  • Il y a \(h\) 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\). En effet, s'il finit par 3 en croissant, c'est qu'avant, c'était 0, 1 ou 2, qu'il était de taille 20 et qu'il finissait en décroissant.

Indice 2

Généraliser une formule qui donne, pour \(n>1\) :

  • l'effectif des nombres serpent de taille \(n\) qui finissent par i en décroissant ;
  • l'effectif des nombres serpent de taille \(n\) qui finissent par i en croissant.

Tout cela en fonction des effectifs pour ceux de taille \(n - 1\).

Indice 3

On utilisera deux tableaux pour progresser en dynamique :

  • 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.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.128013x/.r;nbOylaeu)*d63m(Pô+02è-],59fq!78 _o=Àpcwgv41kRIéhtsSàL[ji:E050q0m0$0l0-0k0%0L0R0k0l0%0%0O010$0-0Q010406050%0n0t0t0l0e0j040(0N0k0n130N0g0L020l0t0Q0f0L0Y0m1d0e0H0n0m0%050c1a1c1e1g180Q04051L1E1O0c1L180q0-0U0{0}0 110#0-0T0#0k1$0#0$16050?0h0k0m1X0~10011#1%1)1%0$1/1;1-0$0e1M0$0#1?1Z010G0^0m0g1r0m010{1j0%0Q0l0g110z1-2j2l271^2a1;2d0t2f040a0L0v0e0N0Q0N0%0-1m1o0;2h0e0e0m0R2J1E2q0g1M0c252V2224231.0q2s111)0g2c2G1-1U1W0|1@2)0-2+0g0N2/1-0Q2O1M2T2V30192k1o2;282_0e1d0k160L0W2S3417332r361^383a3c0z3f2l3h2T2(013m0l3b040L0s3q2U183t3k113w3y0L0V3C3s343u3I3c0E3M3E3O3G3v0N393x3c0r3T3i351Y3l3Y3n3z0J3%3F3*3H3,3!3z0K3:3V3=3X3Z3J0F3{3j3}3Q040W0y423)2=3~3-0W3e1F3g3U434b450W3p4g3r4i4a373@3y0W3B4o2U1P2~1E2/2Y0q242%3W0R2`2y0:1V1M2}0m2 3g3M054I0;4Q4j37160%0m0e0Q2c0$3M0L3(3u0N160O4*4,3W15040+4S3;4b0t0-16484x4W4r1^4@0D4;4{284}16474`3|4b4@0C493P4Z4#4%0g0$0M0R2D0-0 2l4)514+581^4.044:5w4=3}4@4_515E4|4~0450325y115g575e285A0x5S4X54165H5O5T1^5a465d5Y5Q165h5D5P015A0p5X53115)41514q5j044!4$4(0M0;5q0N5s0%5u5^4-4/6b4?5!5+5_015)5N4R5;5R5:5%115V6e5F6g5I5;5)4f5$5,016o305x6q5=165@6p6B5{3T5~3W0X160G3Y6t4k160M6U5U0S162@6Y3l0h160e2l0T0m6h3u4@0u6/3W5)4n6A6i556%5`5L476l3r5J284@0o0.3T0L796F6B0g162+0S5p5r5t5n6}6H5B7l5G6?3}6k7q5f5.7l5?7l6y713D7a7b6i7d047f642P7i697k6K6i5A5C6E735Z4^7t595L7A526:7v7N6c046J7R6x6 7Y067C7S116Q046S0e7l7F0-7w6!046$7$3W0g6)046+0g6-7V7T6=6w6G7z885-0476787C7a7:3v7e0m7g66686a8b6B7p8t7E6#8e6C7#7*6G7P7_831G8z6;8z7F615m5o657K8s6`7!7U8w5 0,8I8B3g7D3u7=7@7_168X803}0N7}7 8C7c8385878V6f048a8S6@7X8Y04568,6V7~900o0o8i8j8#818n7g8P677j5v8}6u8U9j947{8_9k5/8;7O6d93378G1b908|6m6G8L5l638q9h905#9B7c8*909r8!8l8%6T9v3l9M9T6r8/0g8F6*6,6.9p7u8{8K8y9W7m5W9-6y90929s3u8d9(741697999b445k625n7h9g7L9i9P5;8E9-7F7H9Ga69~8l9Da28O7Ja58Ra88D9u9@9c7G8o7Iaean4p7/5;ai8N8z5A0d9+040l0Q5m0q9z8K9x0taM9`9U609Ea3aw7M9m9{8g7w169/ar44aOaQaYaS8M639f8raX9K6{9|985}1E4U4P4za}0c4C1E0$4Eb22#2W0l1:a 4C1K7Z3W2O0t0M0G0l0X0m0M0#0s161w1y1A1C0L775I1R3h1L0i1o4%1l0Lbf0Q0}0R4#0L1;0`1|2+0`0r0L0)3d0y0L2k0e0L0;bM5s0$bt2c2h1s0e0!0#2c2H1naFbx1T1V3u1`1(1*1,bd3}2u2c2e162A0(5q140$2B0j251n4S4O52314Ra|b}94ad8Qa=3r9 4baaa(9)9J72aAa*aR8f9Acu9Ca18Navcla7cA8u6va,3H9VcK8A049Ocn9Q6R9Scr4Y048+cV5z9Y9!849$a+a?9^8 cxcO9?ao9L95c-75a_cZ7;cT7^ab9,c_5=c#ab8?c(c?16cz4y7+5b7Y8l75cQ3Dah9dcEamcm2Uco5Uaqc:a@9lc*81cwcN8Jc-aB9FcF9IaGcYds9q7l9Rc|c 7FdDcRa9d1dJd3869%dvd6aG9ocN6sc-9;d5917y7,96c^dp8$c{8)c=c 8.6#9Zd29#dRc)cH6i9_dT8gde3h0ccha~2Vbb1N040PbK0l0L1a2I1=2L1A670D0L0^0L1Cc72F0 0-b9bY1=4!bV1@bJbZ0L1 0m0l0n0b4+ch7H6Jchet0L1d0g0-0A2O0`0m0bbG0-0Ree0%0d0L0Z0_ec4#1nc70$0N1l0m6S5seAe-0,e-0e0`5q0!0!0`bWc8ca1o0If30L0*1=a|eL0}0L0he-0|ef0m0U0-4(0L3x3Y1Db=4L2:3}b_1|1+2p6Gb 2w2yc3c50Qc70vc90#cb5Icd3(cf72e35;dHd.6X9-d;7~d?dPd^8^d~d7ci7W166_dE9)c/dM8c7,db6n9|bv307.8kaAcCdzdjcGd86G6|c}aTajdia;f}3z8lcqd+8`f!f@9adccJf)9w4Z9yd#f!dgg2cDa:9Hd#ctf~c;dLgudqe0dm1^fPg1gwg7dNd=c$8@dSgh898z7sd#f+dlgndWgL8f9}9-gCdJc~ga8-dOg#4kdQfYgUcOgmd946f/f 9|0CgQ179a79gfdrd{3Pdug,dwcNdyaVdAgsdC9NdGd-gD7|gHd@c%d_gldVaDa$gN6 9=d%dad)ha7?cUg(cWgTf,6BfT8:hv6(fXgKg~gbhmhqd#0og@agf:a!5}azcBgo4(hk04b;h316aIaKd`gxg gjaPhidxf`h5f|96a#04a%hC3Hh0hG9kg.hSa.a3gqafhKd*4pa{4J2VfJb04MbcbAfkekeX0L0n1o0%0$0j1;bV1k0$0wc76S0g2Q0-1n2+0keA0e0A0`0;0g4!b;1S050#0Wek0q5Qe^0B3x1;0e0BbG0n0%0B0k677F0ve^fk0kiRiniVbKiZ1EiJby040ZeXej1n0{3x0R0nimbLeA4#2xiC1=4Ti6h~5veK2L2}0N0Rb-embB2Djc0miGi:0/1o1l0^5s5ubY0ni_0ki{iy1d22eWfi0ki@js4}0meEbV1j0j2_4}3xi@bBe^6+jtjveybtb$39bt0!iY1$0ge}eLj44Vj6i54Ve!e$0Lbi0n0qjQ1d2I0e5sbJ0k00eT2F2^130l2JbEaI0-2L0=bKf7i`i|eM2`i|0@2Ojj18b00=0@0_04.