Nombre de coups de la tour de Hanoï

La tour de Hanoï est un jeu inventé par le mathématicien français Édouard Lucas.

Les règles sont simples :

le jeu est organisé autour de trois bâtons de bois que l'on nommera $a$, $b$ et $c$ ;
sur ces bâtons on glisse des pièces circulaires de diamètres différents. Le nombre de pièces est appelé $n$ ;
les pièces doivent toujours être empilées dans un ordre décroissant : il est interdit de poser une grande pièce sur une petite ;
à chaque étape on déplace une pièce d'un bâton à l'autre ;
initialement, les pièces sont sur le bâton $a$. Le but du jeu est de les amener sur le bâton $c$.

Un stratégie de résolution optimale, qui résout le problème en un nombre minimal de déplacements, repose sur l'observation suivante. Transporter $n$ pièces du bâton $a$ vers le $c$ nécessite de :

transporter les $n - 1$ pièces du dessus du bâton $a$ vers le $b$ ;
déplacer la plus grande pièce du bâton $a$ vers le $c$ ;
transporter les $n - 1$ pièces du bâton $b$ vers le $c$.

L'illustration ci-dessous¹ illustre la résolution du problème dans le cas $n = 4$ :

On cherche dans cet exercice à calculer le nombre de coups minimal permettant de résoudre le problème à $n$ pièces. On note appelle $(u_n)$ la suite définie pour $n > 0$ et donnant le nombre de coups nécessaires à l'exécution de la stratégie proposée dans le cas de $n$ pièces.

On a donc :

\[ \begin{align*} u_1 &= 1&\\ \\ u_2 &= 1 + 1 + 1 \\ &= 3\\ \\ u_3 &= 3 + 1 + 3 \\ &= 7\\ \\ u_4 &= 7 + 1 + 7 \\ &= 15 \end{align*} \]

assert ?

Le mot clé assert est utilisé en Python afin de vérifier que des propositions sont vraies.

Ainsi, l'instruction assert 3 + 5*7 == 38 permet de vérifier que l'expression 3 + 5*7 est bien évaluée à 38.

Si c'est le cas, le programme continue de se dérouler normalement. Dans le cas contraire, le programme est interrompu et une erreur est signalée.

Suite définie par récurrence

De façon générale, on montre que :

\[ \begin{align*} & u_1=1\\ \text{Pour tout }n>0,\qquad & u_{n+1} = 2u_n+1 \end{align*} \]

Écrire la fonction nb_coups qui prend en paramètre l'entier n représentant le nombre de pièces à déplacer (n > 0) et renvoie le nombre de coups permettant de résoudre le problème en appliquant la stratégie décrite.

Exemples

>>> nb_coups(1)
1
>>> nb_coups(2)
3
>>> nb_coups(3)
7
>>> nb_coups(10)
1023

Version videVersion à trous

Évaluations restantes : 10/10

.128013urkm cpiy/2tP)=lhsebwS*_53(av,1:n4dg+of050J0t0m0C0i0q0s0f0g0q0C0s0s0p010m0i0h010406050s0b0e0e0C0c0j040w0M0q0b0(0M0H050k0/0;0?0^0-0h041118051b0k1b1d180-0J0i0D0W0Y0!0$0r0i0K0r0q1r0r0m0+050R0u0q0t1m0Z0#011q1s1u1s0m1A1C1y0m0u0M0J0^1z0c190m0r0W0{0s0h0C0H0$0l011E1o010N0T0t0H0C0e0t1y1$1(1-1G1:1C1?1^0+0a0f0n0c0M0h0M0s0i0~0H0f0P1!0c0c0t0g2d111{0H190k1Y2q0m1W1V1X0J1}0$1u0H1=2a1y1j1l0X1F2A0i2C0H1S1k1y0h2j192o2q2U0.1%2e2I1.2N0c0=0q0+0F2n2Y0,2X1|2!1G2$2(0+0l2,1(2.2o2z012?0C2)040A2`2p0-2}2;0$30320I352|2Y2~3b0+0z3e1a2S112G2t0J2x2~0g1S1_193p1c3n2W122-053u0P2T3g39010d0+0P0N3l381n1G0v0+0f3P3I3R3a0N0+0H0u0y3u0b0h0s3W2:3Y010*040B3-2Z3/0H3#3@2~3;0o0G3e060f433V3Q2J2 0+0b3e453X470M0+0p4b2/3^470e0i2*41444c3.473L040N0M0c4i462#0+0i4z4d1.0M3T042L4E4s2#0u0+0c1(0K0t3|3J3;3?3C2{4j2~4m4o4Y2p4!4V0+0E4L4k4B04104(3H4M1G3~404?424q444*3_494.2~4f044h4?4r4/1G4$042_58504e0+0x533J3`044a5f4A1G550L5k3/5c2+4|4q5g1.4u2j0m0b0c4=2U593h524|113F0t2q2R5P3o1k3q2t2v2r1R1T2t0C1B5S0k3p0-5)0Q0S0U04.

Évaluations restantes : 10/10

.128013urkm cpiy/2tP)=lhsebwS*_53(av,1:n4dg+of050J0t0m0C0i0q0s0f0g0q0C0s0s0p010m0i0h010406050s0b0e0e0C0c0j040w0M0q0b0(0M0H050k0/0;0?0^0-0h041118051b0k1b1d180-0J0i0D0W0Y0!0$0r0i0K0r0q1r0r0m0+050R0u0q0t1m0Z0#011q1s1u1s0m1A1C1y0m0u0M0J0^1z0c190m0r0W0{0s0h0C0H0$0l011E1o010N0T0t0H0C0e0t1y1$1(1-1G1:1C1?1^0+0a0f0n0c0M0h0M0s0i0~0H0f0P1!0c0c0t0g2d111{0H190k1Y2q0m1W1V1X0J1}0$1u0H1=2a1y1j1l0X1F2A0i2C0H1S1k1y0h2j192o2q2U0.1%2e2I1.2N0c0=0q0+0F2n2Y0,2X1|2!1G2$2(0+0l2,1(2.2o2z012?0C2)040A2`2p0-2}2;0$30320I352|2Y2~3b0+0z3e1a2S112G2t0J2x2~0g1S1_193p1c3n2W122-053u0P2T3g39010d0+0P0N3l381n1G0v0+0f3P3I3R3a0N0+0H0u0y3u0b0h0s3W2:3Y010*040B3-2Z3/0H3#3@2~3;0o0G3e060f433V3Q2J2 0+0b3e453X470M0+0p4b2/3^470e0i2*41444c3.473L040N0M0c4i462#0+0i4z4d1.0M3T042L4E4s2#0u0+0c1(0K0t3|3J3;3?3C2{4j2~4m4o4Y2p4!4V0+0E4L4k4B04104(3H4M1G3~404?424q444*3_494.2~4f044h4?4r4/1G4$042_58504e0+0x533J3`044a5f4A1G550L5k3/5c2+4|4q5g1.4u2j0m0b0c4=2U593h524|113F0t2q2R5P3o1k3q2t2v2r1R1T2t0C1B5S0k3p0-5)0Q0S0U04.

Suite définie explicitement

On donne ci-dessous les premières valeurs de $u_n$ :

\[u_1 = 1 \qquad u_2 = 3 \qquad u_3 = 7 \qquad u_4 = 15 \qquad...\qquad u_{10} = 1\,023 \qquad...\qquad u_{20} = 1\,048\,575 \qquad\]

On peut montrer qu'il existe une formule permettant de calculer directement $u_n$ à l'aide de la seule valeur de $n$ et ce, sans utiliser la formule de récurrence de la question précédente.

On ne fournit pas cette formule explicite, il est demandé de la conjecturer.

Écrire la fonction nb_coups qui prend en paramètre l'entier n représentant le nombre de pièces à déplacer (n > 0) et renvoie le nombre de coups permettant de résoudre le problème en appliquant la stratégie décrite.

Grandes valeurs de $n$

La fonction demandée doit calculer explicitement la valeur cherchée sans utiliser de boucle ni de formule de récurrence.

Les tests secrets portent sur de très grandes valeurs de $n$. Ainsi, un algorithme structuré autour d'une boucle aura pour conséquence de bloquer le navigateur.

Exemples

>>> nb_coups(1)
1
>>> nb_coups(2)
3
>>> nb_coups(3)
7
>>> nb_coups(10)
1023

Évaluations restantes : 10/10

.128013.urkm c;piy/xA2ORtP)=lh0q{seb^wS*}_-(3éav,1:[ndgU+]of050V0C0s0O0k0w0B0g0h0w0O0B0B0v010s0k0j010406050B0c0f0f0O0d0l040G0!0w0c0_0!0U0g020O0f0j0i0g0r0C130d0z0c0C0B050m101214160~0j041u1B051E0m1E1G1B0~0V0k0P0.0:0=0@0x0k0W0x0w1U0x0s0|050)0D0w0C1P0;0?011T1V1X1V0s1%1)1#0s0D0!0V161$0d1C0s0x0.190B0j0O0U0@0p011+1R010#0+0C0U1h0C1#26282d1-2g1)2j0f2l040a0g0t0d0!0j0!0B0k1c1e0%240d0d0C0h2G1u2n0U1C0m222S0s201 210V2p0@1X0U2i2D1#1M1O0/1,2$0k2(0U1|1N1#0j2L1C2Q2S2}0 271e2.2e2?0d130w0|0R2P310}302o331-35370|0p3b282S2`0C2S2,2V0V2Z2#010h1|2v0$1N1C3p2|3c3m2R053y0%3F3f1Q1-0e0|0%0#3H3M323O0@0F0|0g3U3e3W2/010U0#0|0U0D0J3y0c0j1t1v3G2Q3w0{040L3$3`3g0@0U3-3 313{0|0u0S3U060g4d3#403X013Q042L0s0c0d0U3U4f4641010f0k3k453N3)0!0|0H0H4y3(34443^3n4r4z2e4B040K4q3%3w4v394b1u3K3q1D2{1u3s1u0s3u4(2X2T1{1}2V0O1(4Z0m3s1A3V3w2L0f0J0#0O0e0C0J0x0M0|1m1o1q1s0g4a4J3I1H3d1B0q1e0O0g2i5l0#0#0(0Q0g2C4n0g0s0!1b4L4G1-142F0x130s0C0n0|090L1e020W0s1k0y090u4q5c1K3B2-4h5C225F5H5J0T0c0J290p0E0U0K0R090Z4$3C4_0o1?2i2G5v5x5G0#0!0k0B5r0c2(0g0P0N0d0k2g0h0O5}0V280-0 2W1d0W040h0C0d0)2;0-6e0-276r0k0h0c1X6q3@0B6l0U6n0g670j6q2u0s5s0;0g2I2`5x0P6q0g590.0(5G0g61366B1*1s6O0P0d0*1*5t0d4f6G6n5w1b5a1)0-0P0O1)4n0-2I4S4t5!5E6f5%045K0U5S4q6F6b2N1n5|5s2D2F1N1s2P6@040b1D5g040X6K2L0c6V6R1*6p0g0d0N100w0)6O4 2F0g2;5G0d6V0U0k6=0:0g102F1*282(0n1*745Z6b5#785I7a0L0L0P5+0u7d5d046R0N2g7S6:5x6=6_6O5|0k6W7(3)765$7-7b5N5P5R5T7^6P6=5V3d2,3w887,5(7;1e0v0g5*1e0Y0g5;5?4@5^1F045i5s0C5y0f1d2W6W6Y6p5{7W0c7Y0g7!5H6*6F0g0W0N0!0f0N2W0k6Y6S4|84806M7%4g877*775G8a7:0J0R0v0p7@2}5l6O2I6.631d5z8m8=895J0L0z8|8~3c7s5f4_8E5m0V0N0V8Q6O595r6;5~5y862e8n8@9a5M5O5Q9e4K8j1L1N975D997a0T8q0g8s5-7c8z4^8C0(6R1d0h5b7t9G5Y8;9J8o9L06090D0C0W2;0A6 1U0U0H0I068u1f1h1j8s8q5:0909061g1i0i8|5.5:9+2i0V9;1;9@9_5=5@0P3d4@0(0*0,04.

Les illustrations de cette page proviennent d'ici et là. ↩