汉诺塔问题的ppt详解课件.ppt

《汉诺塔问题的ppt详解课件.ppt》由会员分享，可在线阅读，更多相关《汉诺塔问题的ppt详解课件.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、/ 汉诺塔汉诺塔 ABCABC/ 汉诺塔汉诺塔 ABC/ 汉诺塔汉诺塔 ABC/ 汉诺塔汉诺塔 ABC/ 汉诺塔汉诺塔 ABC/ 汉诺塔汉诺塔 ABC/ 汉诺塔汉诺塔 ABC/ 汉诺塔汉诺塔 ABC/ 汉诺塔汉诺塔 ABC/ 汉诺塔汉诺塔 ABC/ 汉诺塔汉诺塔 ABC/ 汉诺塔汉诺塔 / 汉诺塔汉诺塔 # include void hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b ) ; printf(“%c - %cn”, a , c) ; hanoi ( n-1, b, a, c ) ; v

2、oid main () int n ; printf( Input the number of diskes:n “) ; scanf(“%d”,&n) ; hanoi ( n, A , B , C ) ; StackOutput/ 汉诺塔汉诺塔 void main () int n ; printf( Input the number of diskes:n “) ; scanf(“%d”,&n) ; hanoi ( n, A , B , C ) ; StackH ( 3, A, B, C )3 A B COutputH(n,A,B,C)/ 汉诺塔汉诺塔 void main () int n

3、 ; printf( Input the number of diskes:n “) ; scanf(“%d”,&n) ; hanoi ( n, A , B , C ) ; StackH ( 3, A, B, C )3 A B COutputH(n,A,B,C)void hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; / 汉诺塔汉诺塔StackH ( 3, A, B, C )3 A B C2 A C

4、 B1 A B COutputH(n,A,B,C)H(n-1,a,c,b)H(n-1,a,c,b)H ( 0, A, C, B )H(n-1,a,c,b)0 A C BH ( 2, A, C, B )H ( 1, A, B, C )void hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BH ( 1

5、, A, B, C )1 A B COutputH(n,A,B,C)H(n-1,a,c,b)H(n-1,a,c,b)H ( 0, A, C, B )H(n-1,a,c,b)0 A C Bvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BH ( 1, A, B, C )1 A B COutpu

6、tA CH(n,A,B,C)H(n-1,a,c,b)H(n-1,a,c,b)coutvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BH ( 1, A, B, C )1 A B COutputA CH(n,A,B,C)H(n-1,a,c,b)H(n-1,a,c,b)H ( 0, B , A,

7、 C )H(n-1,b,a,c)0 B A Cvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BH ( 1, A, B, C )1 A B COutputA CH(n,A,B,C)H(n-1,a,c,b)H(n-1,a,c,b)H ( 0, B , A, C )H(n-1,b,a,c)0 B

8、 A Cvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BH ( 1, A, B, C )1 A B COutputA CH(n,A,B,C)H(n-1,a,c,b)H(n-1,a,c,b)void hanoi ( int n, char a, char b, char c ) if ( n

9、 = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BOutputA CA BH(n,A,B,C)H(n-1,a,c,b)coutvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH

10、 ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BOutputA CA BH(n,A,B,C)H(n-1,a,c,b)1 C A BH(n-1,b,a,c)H ( 1, C, A, B )void hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BOutputA

11、 CA BH(n,A,B,C)H(n-1,a,c,b)H ( 1, C, A, B )1 C A BH(n-1,b,a,c)H ( 0, C, B , A)H(n-1,a,c,b)0 C B Avoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BOutputA CA BH(n,A,B,C)H(

12、n-1,a,c,b)H ( 1, C, A, B )1 C A BH(n-1,b,a,c)H ( 0, C, B , A)H(n-1,a,c,b)0 C B Avoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BOutputA CA BH(n,A,B,C)H(n-1,a,c,b)H ( 1,

13、C, A, B )1 C A BH(n-1,b,a,c)C Bcoutvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BOutputA CA BH(n,A,B,C)H(n-1,a,c,b)H ( 1, C, A, B )1 C A BH(n-1,b,a,c)C BH ( 0, A, C ,

14、B )H(n-1,b,a,c)0 A C Bvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BOutputA CA BH(n,A,B,C)H(n-1,a,c,b)H ( 1, C, A, B )1 C A BH(n-1,b,a,c)C BH ( 0, A, C , B )H(n-1,b,a,

15、c)0 A C Bvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BOutputA CA BH(n,A,B,C)H(n-1,a,c,b)H ( 1, C, A, B )1 C A BH(n-1,b,a,c)C Bvoid hanoi ( int n, char a, char b, char

16、 c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BOutputA CA BH(n,A,B,C)H(n-1,a,c,b)C Bvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c

17、) ; StackH ( 3, A, B, C )3 A B CH ( 2, A, C, B )2 A C BOutputA CA BH(n,A,B,C)H(n-1,a,c,b)C BA Ccoutvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B

18、A CH(n-1,b,a,c)A Cvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B A C1 B C AH(n-1,b,a,c)H(n-1,a,c,b)A CH ( 0, B, A, C )H(n-1,a,c,b)0 B A CH ( 1, B,

19、 C, A )void hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B A CH ( 1, B, C, A )1 B C AH(n-1,b,a,c)H(n-1,a,c,b)A CH ( 0, B, A, C )H(n-1,a,c,b)0 B A Cvoid

20、 hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B A CH ( 1, B, C, A )1 B C AH(n-1,b,a,c)H(n-1,a,c,b)A CB Acoutvoid hanoi ( int n, char a, char b, char c

21、) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B A CH ( 1, B, C, A )1 B C AH(n-1,b,a,c)H(n-1,a,c,b)A CB AH ( 0, C , B , A)H(n-1,b,a,c)0 C B Avoid hanoi ( int n, char a, char b, char c ) if (

22、n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B A CH ( 1, B, C, A )1 B C AH(n-1,b,a,c)H(n-1,a,c,b)A CB AH ( 0, C , B , A)H(n-1,b,a,c)0 C B Avoid hanoi ( int n, char a, char b, char c ) if ( n = 1 )

23、 hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B A CH ( 1, B, C, A )1 B C AH(n-1,b,a,c)H(n-1,a,c,b)A CB Avoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a

24、,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B A CH ( 1, B, C, A )1 B C AH(n-1,b,a,c)H(n-1,a,c,b)A CB AB Ccoutvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH (

25、 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B A CH(n-1,b,a,c)A CB A1 A B CH(n-1,b,a,c)B CH ( 1, A, B, C )void hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,

26、C)C BH ( 2, B, A, C )2 B A CH(n-1,b,a,c)A CB AH ( 1, A, B, C )1 A B CH(n-1,b,a,c)B CH ( 0, A, C , B)H(n-1,a,c,b)0 A C Bvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C B

27、H ( 2, B, A, C )2 B A CH(n-1,b,a,c)A CB AH ( 1, A, B, C )1 A B CH(n-1,b,a,c)B CH ( 0, A, C, B )H(n-1,a,c,b)0 A C Bvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2

28、, B, A, C )2 B A CH(n-1,b,a,c)A CB AH ( 1, A, B, C )1 A B CH(n-1,b,a,c)B CA Ccoutvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; / 汉诺塔汉诺塔void hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; c

29、outa c= 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B A CH(n-1,b,a,c)A CB A1 A B CB CA CH ( 1, A, B, C )H(n-1,b,a,c)void hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; p

30、rintf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B COutputA CA BH(n,A,B,C)C BH ( 2, B, A, C )2 B A CH(n-1,b,a,c)A CB AB CA Cvoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; StackH ( 3, A, B, C )3 A B

31、COutputA CA BH(3,A,B,C)C BA CB AB CA COvervoid hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ; OverStackOutputA CA BC BA CB AB CA C/ 汉诺塔汉诺塔void hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b) ; printf(“%c -%cn“,a,c); hanoi (n-1, b, a, c) ;