JavaOJ & 汉诺塔问题
汉诺塔定义：
通俗地来讲就是：
一堆盘子从一根柱子全部挪向另一根柱子
并且有如下规则：
一次只能移动一个盘子
大盘子不能叠在小盘子之上
老规矩，我们先学会思想
1. ”整体性假设“思想
在这里不给动图以及不给手解方法的原因是：真的很难理解的了，即使会怎么摆了，但是也可能不会是正确解法。
现在是《幻想时刻》
假设，我说假设！
如果如果如果有一个方法hanoi(x)（x代表总盘子数）,它可以帮我们将A柱子的所有挪向C柱子*
那么那么那么是不是hanoi(x - 1)就可以将A柱子的x - 1个盘子挪向B柱子！是不是？
然后A柱子剩余的一个盘子是不是就可以直接放在C柱子上？
那么接下来请问，hanoi(x - 1)是不是也有能力让B柱子的x - 1个盘子子全部挪到C盘子上？
*没错，我们幻想了一下，发现只要知道x - 1个盘子怎么移动，那么我就可以利用刚才的方法，去挪动x个盘子。
那么那么那么是不是我们会挪一个盘子
就会挪两个盘子，= =》就会挪三个盘子，= = = = = = = = = = = =》
那就会挪x个盘子！
2. 代码设计
参数：
三根柱子：ABC
n个盘子。
public class Hanata { public static int count = 1; //在自己类之中，静态的全局性变量 public static void hanoi(int n, char pos1, char pos2, char pos3){ //1. ************************************ if(n == 1) { move(pos1, pos3); return; //return !!! } //2. ************************************ hanoi(n - 1, pos1, pos3, pos2); move(pos1, pos3); hanoi(n - 1, pos2, pos1, pos3); } //3. ************************************ public static void move(char pos1, char pos2) { System.out.println("第" + count++ + "次移动: " + pos1 + " -> " + pos2 + " "); } //4. ************************************ public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); hanoi(n,'A','B','C'); } }
2.1 区域3：
public static void move(char pos1, char pos2) { System.out.println("第" + count++ + "次移动: " + pos1 + " -> " + pos2 + " "); }
移动盘子并且打印出来
2.2 区域1：
if(n == 1) { move(pos1, pos3); return; //return !!! }
hanoi(1) ==> 第一个盘子的放法，我们默认A(pos1)柱子为起始柱
通过测试，我们改变pos1，pos3，为其他，只是决定了所有盘子初始位置，以及第一个盘子挪向哪。
那么第一个盘子放在C(pos3)柱子就好了
这也是递归出口！
2.3 区域2：
hanoi(n - 1, pos1, pos3, pos2); move(pos1, pos3); hanoi(n - 1, pos2, pos1, pos3);
Ⅰ. 跟刚才的想法一致，我们将A（pos1）的 n - 1 个盘子通过C(pos3)挪到B(pos2)
通过上面动图思想的分析，不难发现，总有一个中间柱子充当媒介，帮助n-1个盘子的挪动
Ⅱ. 将A(pos1)放置到C(pos3)
Ⅲ.将B(pos2)的n-1个盘子以相同的方式通过A(pos1)挪到C(pos3)
2.4 测试
public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); hanoi(n,'A','B','C'); }
这里为什么是31次呢，其实就是 2n -1
一个盘子要1次
那么两个要1 + 1 + 1 = 3
那么三个要 3 + 1 + 3 = 7
那么四个要 7 + 1 + 7 = 15
即an = 2an-1 + 1; ==>等比数列 ==》 通式：an = 2 n - 1；*
3. 用C实现后再VS2022测试（有时停函数与清屏，更加好观察）
C语言实现汉诺塔自走版
代码有点长，不做为重点，只是为了测试
汉诺塔自走版视频
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<string.h> #include<Windows.h> #include<stdlib.h> #define NUM 5 int count = 0; typedef struct hanuota { char X; char Y[NUM+1]; int count; }sh; void print(sh* pa, sh* pb, sh* pc) { sh s[3] = { *pa,*pb,*pc }; int i = 0; int j = 0; sh tmp; for (i = 0; i < 3; i++) { for (j = 1; j < 3 - i; j++) { if (s[j].X < s[j - 1].X) { tmp = s[j - 1]; s[j - 1] = s[j]; s[j] = tmp; } } } for (i = 0; i < 3; i++) { printf("柱%c:%s\n", s[i].X, s[i].Y); } Sleep(500); } void step(int n, sh* pa, sh* pb, sh* pc) { if (n == 1) { system("cls"); printf("第%2d步：%c-->%c\n\n", ++count, pa->X, pc->X); pc->Y[(pc->count)] = pa->Y[(pa->count)-1]; pa->Y[(pa->count)-1] = ' '; (pc->count)++; (pa->count)--; print(pa, pb, pc); } else { step(n - 1, pa, pc, pb); { system("cls"); printf("第%2d步：%c-->%c\n\n", ++count, pa->X, pc->X); pc->Y[(pc->count)] = pa->Y[(pa->count)-1]; pa->Y[(pa->count)-1] = ' '; (pc->count)++; (pa->count)--; print(pa, pb, pc); } step(n - 1, pb, pa, pc); } } init(sh* pa) { int i = 0; int j = 0; for (i = NUM-1; i >=0; i--,j++) { pa->Y[j] = 'A' + i; } } int main() { int n = 0; sh a = { 'A',{0},NUM }, b = { 'B',{0},0 }, c = { 'C',{0},0 }; sh* pa = &a, * pb = &b, * pc = &c; init(pa); print(pa, pb, pc); Sleep(2500); step(NUM, pa,pb,pc); system("cls"); print(pa, pb, pc); return 0; }
文章到此结束！谢谢观看 —>内容参考【比特科技】
可以叫我 小马，我可能写的不好或者有错误，但是一起加油鸭🦆！
这是我的代码仓库！（在马拉圈的23.2里）代码仓库
汉诺塔 · Java版代码位置
汉诺塔电脑自走版 · C代码位置
