逻辑训练--经典汉诺塔问题(C和JAVA递归实现)

简介: 逻辑训练--经典汉诺塔问题(C和JAVA递归实现)

一.汉诺塔问题



1.汉诺塔问题的来源


源自古印度的汉诺塔游戏,具体相传来源,可自行搜索


2.汉诺塔问题的意义


有人觉得,汉诺塔是一个非常无聊的问题,只有一个盘子的时候,直接移动就完成了,两个盘子的时候也只是稍微多了2次,三个盘子的时候也仅较两个盘子多移动了4次…

这样下去,无论你是10个盘子,还是20个盘子,总能在经过一定移动次数过后完成目标,那这样你是否会觉得很无聊?这有什么用呢?为什么还是有那么多人去想着用各种各样的方式去解决它?


究其原因(浅显理解),我认为有一下几点:

1.锻炼脑力,考验耐性

2.理解递归、栈等重要应用


3.汉诺塔游戏规则


该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置N个盘子。

image.png


游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。


操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。


二.代码实现



1.问题分析


对于汉诺塔问题,该怎样去理解呢?


1.N=1,一个盘子的时候,我们只需要移动一次,直接将其从A上移动到C上

2.N>=2,两个以上盘子的时候,我们只需要将N-1个盘子借助C先移动到B,在将A中第N个盘子移动到C(如下图)

c256916c2fb44e14a3f0f4e791e435fa.png


3.当N移动到C上后,此时A上没有盘子,可以作为我们N-1个盘子中把第N-2个盘子通过A中转挪到C上的桥梁。

4.当第N-1个盘子移动到C上后,此时B上没有盘子,可以作为N-2个盘子中第N-3个盘子通过B移动到C上的桥梁

619dda1425424ea6ac23a7cd20c7f072.png


5.如此往复,通过A,B两根柱子的中装,直至将所有的盘子全部按照规则挪到C上


通过上面的分析,不难发现这是一个对于同一件事情不断反复操作,即将N-1个盘子通过B©中转直至都挪到C上,与递归的思想一致,因此,解决上述问题,我们可以采用递归的方法


2.代码实现


C语言实现:

//A - 起始位置
//B - 中转位置
//C - 目标位置
#include<stdio.h>
int count = 0;
void hanoi_tower(int n, char dest1, char dest2, char dest3)
{
  if (n == 1)
  {
    printf("第%d次:%c->%c ", ++count, dest1, dest3);
  }
  //里面即为完成将N-1个盘子中的第N-1个盘子从A移动到C
  else
  {
    //将n-1个盘从A通过C移动到B
    hanoi_tower(n - 1, dest1, dest3, dest2);
    printf("第%d次:%c->%c ", ++count, dest1, dest3);
    //将n-1个盘子从B通过A移动到C
    hanoi_tower(n - 1, dest2, dest1, dest3);
  }
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  hanoi_tower(n, 'A', 'B', 'C');
  printf("一共移动了%d次", count);
}


运行结果如下:

021ae3c69623432cb7fbf21901da9f4a.png


JAVA实现:

/*  dest1--起始位置
*   dest2--中转位置
*   dest3--目标位置
* */
    public static void hanoi_tower(int n, char dest1, char dest2, char dest3) {
        if (n == 1) {
            move(dest1, dest3);
            return;
        } else {
            //1.把n-1个盘 从dest1借助dest3放到dest2上
            hanoi_tower(n - 1, dest1, dest3, dest2);
            //2.将dest1上最地下那个盘从dest1直接放到dest3上 完成将最大得先放在目标中
            move(dest1, dest3);
            //3.把dest2上得n-1盘从dest2借助dest1放到dest3上 完成整个挪动
            hanoi_tower(n - 1, dest2, dest1, dest3);
        }
    }
    //模拟盘子移动
    public static void move(char dest1, char dest2) {
        System.out.print(dest1 + "->" + dest2 + " ");
    }
    //经典汉诺塔问题
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        hanoi_tower(n, 'A', 'B', 'C');
    }


运行结果如下:

1016cd4ed35743b8a3d14444c218dbb3.png


三.汉诺塔问题总结



汉诺塔问题是需要预先计划和回顾性计划,非常的考研耐性和逻辑规划,在递归解决汉诺塔问题中,最主要的是有一个整体性的思想,将除了N个盘子中,第N个盘子以外的N-1个盘子当作整体移动即可,把N-1个盘子、N-2个盘子的移动看作是一个问题(将A中的盘子挪到C上)的子问题(将N-1个盘子借助B或者A中转挪到C上)

相关文章
|
4月前
|
搜索推荐 Java 索引
|
4月前
|
Java
【思维导图】JAVA网络编程思维升级:URL与URLConnection的逻辑梳理,助你一臂之力!
【思维导图】JAVA网络编程思维升级:URL与URLConnection的逻辑梳理,助你一臂之力!
60 1
|
4月前
|
搜索推荐 Java 索引
|
4月前
|
搜索推荐 Java 索引
|
4月前
|
搜索推荐 Java 索引
|
3月前
|
Java
java基础(11)函数重载以及函数递归求和
Java支持函数重载,即在同一个类中可以声明多个同名方法,只要它们的参数类型和个数不同。函数重载与修饰符、返回值无关,但与参数的类型、个数、顺序有关。此外,文中还展示了如何使用递归方法`sum`来计算两个数之间的和,递归的终止条件是当第一个参数大于第二个参数时。
32 1
java基础(11)函数重载以及函数递归求和
|
1月前
|
存储 缓存 NoSQL
一篇搞懂!Java对象序列化与反序列化的底层逻辑
本文介绍了Java中的序列化与反序列化,包括基本概念、应用场景、实现方式及注意事项。序列化是将对象转换为字节流,便于存储和传输;反序列化则是将字节流还原为对象。文中详细讲解了实现序列化的步骤,以及常见的反序列化失败原因和最佳实践。通过实例和代码示例,帮助读者更好地理解和应用这一重要技术。
33 0
|
4月前
|
运维 Java 程序员
新手进阶:用对if-else,让你的Java逻辑判断不再纠结!
新手进阶:用对if-else,让你的Java逻辑判断不再纠结!
78 3
|
4月前
|
Java 开发者
在Java编程中,if-else与switch作为核心的条件控制语句,各有千秋。if-else基于条件分支,适用于复杂逻辑;而switch则擅长处理枚举或固定选项列表,提供简洁高效的解决方案
在Java编程中,if-else与switch作为核心的条件控制语句,各有千秋。if-else基于条件分支,适用于复杂逻辑;而switch则擅长处理枚举或固定选项列表,提供简洁高效的解决方案。本文通过技术综述及示例代码,剖析两者在性能上的差异。if-else具有短路特性,但条件增多时JVM会优化提升性能;switch则利用跳转表机制,在处理大量固定选项时表现出色。通过实验对比可见,switch在重复case值处理上通常更快。尽管如此,选择时还需兼顾代码的可读性和维护性。理解这些细节有助于开发者编写出既高效又优雅的Java代码。
62 2