WHCSRL 技术网

汉诺塔c语言实现及分析

目录

起源

c语言实现


起源

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

一次只移动一片,不管在哪根针上,小片必须在大片上面。

c语言实现

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<stdio.h>
  3. static int count = 0;//计数器
  4. void move(int n,char A,char C)
  5. {
  6. printf("将%%%%d号盘子从%%%%c移动到%%%%c ", n, A, C);
  7. count++;
  8. }
  9. void hannio(int n, char A, char B, char C)
  10. {
  11. int count = 0;
  12. int i = 0;
  13. if (n == 1)
  14. {
  15. move(n,A,C);
  16. printf("将%%%%d号盘子从%%%%c移动到%%%%c ", n,A,C);
  17. }
  18. else
  19. {
  20. hannio(n - 1,A,C,B);//借助C将n-1个从A移到B
  21. move(n, A, C);//将最大那个从A移到C
  22. hannio(n - 1, B, A, C);//借助A将n-1个从B移到C
  23. }
  24. }
  25. int main()
  26. {
  27. char ch1 = 'A';
  28. char ch2 = 'B';
  29. char ch3 = 'C';
  30. int n = 0;
  31. scanf("%%%%d", &n);
  32. hannio(n,'A','B','C');
  33. printf("总共移动%%%%d次 ", count);
  34. return 0;
  35. }
  36. //代码分析:
  37. //n = 3为例
  38. //n = 3不满足n = 1条件, 进入else
  39. //hannio(3, A, B, C) A - A B - B C - C
  40. // hannio(2, A, C, B) A - A B - C, C - B 此时B里面是C, C里面是B
  41. // hannio(1, A, C, B) A - A B - B C - C
  42. // printf 将1号从A移动到C n = 1 执行if语句
  43. // printf("将%%%%d号盘子从%%%%c移动到%%%%c ", n, A, C)此时n为2 A - A B - C, C - B 将2号从A移到B
  44. // hannio(1, B, A, C); B里面存放的是C, A里面存放的是A, C里面存放的是B 把C传给A, 把A传给B, 把B传给C A - C B - A C - B
  45. // printf 将1号从A移到C 即从C移到B
  46. //printf n = 3执行完毕, 此时n = 3, 将3号从A移到C
  47. // hannio(2, B, A, C) A-B B-A C-C
  48. // hannio(1, A, C, B) A-B B-C C-A A里面是B赋给A C里面是C赋给C B里面是A赋给C
  49. // printf 将1号从B移到A
  50. // printf 此时n=2 将2号从B移到C
  51. // hannio(1, B, A, C); A-A B-B C-C 将一号从A移到C

将1号盘子从A移动到C
将1号盘子从A移动到C
将2号盘子从A移动到B
将1号盘子从C移动到B
将1号盘子从C移动到B
将3号盘子从A移动到C
将1号盘子从B移动到A
将1号盘子从B移动到A
将2号盘子从B移动到C
将1号盘子从A移动到C
将1号盘子从A移动到C
总共移动7次

 

推荐阅读