Bonjour,
Un exercice classique de programmation les tours de Hanoï.
1)
Je note a b c les disques sur les aiguilles
0 disque S(0)=0
0 0 0
1 disque S(1)=2*S(0)+1=2*0+1=1
1 0 0
0 1 0 ==> 1 mouvement (déplacement du plus grand disque)
2 disques S(2)=2*S(1)+1=2*1+1=3
2 0 0
1 1 0 On a effectué S(1)
0 1 1 1 mouvement (déplacement du plus grand disque)
0 0 2 on a effectué S(1)
3 disques S(3)=2*S(2)+1=2*3+1=7
3 0 0
2 1 0
1 1 1
1 0 2 ===>On vient d'effectuer S(2)
0 1 2===>1 mouvement (déplacement du plus grand disque)
1 1 1
1 2 0
0 3 0===> On vient d'effectuer S(2)
4 disques S(4)=2*S(3)+1=2*7+1=15
4 0 0 (1234) () ()
1 3 1 0 (234) (1) ()
2 2 1 1 (34) (1) (2)
3 2 0 2 (34) () (12)
4 1 1 2 (4) (3) (12)
5 2 1 1 (14) (3) (2)
6 2 2 0 (14) (23) ()
7 1 3 0 (4) (123) () === S(3)
1 0 3 1 () (123) (4) 1 mouvement (du plus grand disque)
1 0 2 2 () (23) (14)
2 1 1 2 (2) (3) (14)
3 2 1 1 (12) (3) (4)
4 2 0 2 (12) () (34)
5 1 1 2 (2) (1) (34)
6 0 1 3 () (1) (234)
7 0 0 4 () () (1234) on a effectué S(3)
2b) S(n)=S(n-1)+1+S(n-1)=2S(n-1)+1
3)
S(0)=0
S(1)=2*S(0)+1=2*0+1=1=2^1-1=1
On suppose la propriété vraie pour : S(n)=2^n-1
S(n+1)=2*S(n)+1=2*(2^n-1)+1=2^(n+1)-2+1=2^(n+1)-1
4)
S(64)=2^64-1=18446744073709551615
temps=18446744073709551615 s=307445734561825860,25 min =5124095576030431,0041666666666667 h
=213503982334601,29184027777777778 j
=584542046090,62639791999391588714 an
