汉诺塔从模型到实现递归&循环两种方式 java

2024-03-01 02:21| 来源: 网络整理| 查看: 265

汉诺塔递归模型建立 public class test2 { public static void main(String[] args) { hanio(3, 'a', 'b', 'c'); } static void hanio(int n, char a, char b, char c) { if (n == 1) { System.out.println(String.format("移动第%s个盘子 %s -> %s", n, a, c)); } else { hanio(n - 1, a, c, b); System.out.println(String.format("移动第%s个盘子 %s -> %s", n, a, c)); hanio(n - 1, b, a, c); } } }

说明：上面是一个动态规划（数学中的一个术语）模型，通过递归（计算机术语）实现的汉诺塔例子，这个过程只是获取移动步骤这个方法，并没有实现移动效果。

递归的实现 package stackAndQueue; import java.util.ArrayList; import java.util.Observable; import java.util.Stack; import static java.lang.System.out; import java.lang.reflect.Array; public class t6_Hanoi_Tower_ex { static private Stack st1; static private Stack st2; static private Stack st3; public static void main(String[] args) { // 1.定义三个栈，表示三个托盘柱 int nu = 25;// 设定有多少盘在第根柱子上 st1 = new Stack();//第一个托盘 for (int i = nu; i >= 1; i--) { st1.push(i); } // 把数字当做盘号，一个一个塞进栈里面 st2 = new Stack();//第二个托盘 st3 = new Stack();//第三个托盘 ArrayList lst = new ArrayList();// 收集步骤用， // 展示开始时三个栈的情况 out.println(st1); out.println(st2); out.println(st3); // 2.获取模型步骤 long startTime1 = System.currentTimeMillis();// 计时用，看花费多少时间 hanio(nu, 1, 2, 3, lst);// .........这时调用的模型 long endTime1 = System.currentTimeMillis();// 计时用，看花费多少时间 long usedTime1 = (endTime1 - startTime1) / 1000;// 计时用，看花费多少时间 out.println("模型建立时间：" + usedTime1);// 计时用，看花费多少时间 /* 3.按步骤执行 */ long startTime = System.currentTimeMillis();// 计时用，看花费多少时间 for (Integer[] ly : lst) { if (ly[0] == 1) { if (ly[1] == 2) st2.push(st1.pop()); else { st3.push(st1.pop()); } } else if (ly[0] == 2) { if (ly[1] == 1) st1.push(st2.pop()); else { st3.push(st2.pop()); } } else { if (ly[1] == 1) st1.push(st3.pop()); else { st2.push(st3.pop()); } } } long endTime = System.currentTimeMillis();// 计时用，看花费多少时间 long usedTime = (endTime - startTime) / 1000;// 计时用，看花费多少时间 // 展示过后三个栈的情况 out.println(st1); out.println(st2); out.println(st3); out.println("执行时间为：" + usedTime); } /** * 汉诺塔移动步骤的模型， * * @param n //表示层数 * @param a //第一个柱，想象成空柱 * @param b //第二给柱 * @param c //第三给柱 * @param lst //用于收集模型步骤 */ static void hanio(int n, int a, int b, int c, ArrayList lst) { if (n == 1) { // out.println(String.format("移动第%s个盘子 %s -> %s", n,a,c)); Integer[] il = new Integer[2]; il[0] = a; il[1] = c; lst.add(il); } else { hanio(n - 1, a, c, b, lst); // out.println(String.format("移动第%s个盘子 %s -> %s", n,a,c)); Integer[] il = new Integer[2]; il[0] = a; il[1] = c; lst.add(il); hanio(n - 1, b, a, c, lst); } } }

一切递归能转循环，可以理解为递归就能递推，肯定比较复杂

循环模型建立中实现 package stackAndQueue; import java.util.*; import static java.lang.System.out; public class t6_Hanoi_Tower { public static void main(String[] args) { action(4); out.println("Over!!!!!!!!!!"); } static void action(int n) { char[] s = { 'q', 'a', 'b', 'c' }; ArrayList sts = new ArrayList(); sts.add(new Stack()); sts.add(new Stack()); sts.add(new Stack()); sts.add(new Stack()); int N = n, count = 0; for (int i = 0; i < N; i++) sts.get(1).push(N - i); if (N % 2 == 1) { s[2] = 'c'; s[3] = 'b'; } while (true) { ++count; move((count - 1) % 3 + 1, (count) % 3 + 1, sts, s); if (!move((count - 1) % 3 + 1, (count + 1) % 3 + 1, sts, s) && !move((count + 1) % 3 + 1, (count - 1) % 3 + 1, sts, s)) break; } } static Boolean move(int before, int after, ArrayList sts, char[] s) { if (sts.get(before).empty()) return false; if (!sts.get(after).empty()) if ((sts.get(after).peek() - sts.get(before).peek()) < 0) return false; sts.get(after).push(sts.get(before).peek()); sts.get(before).pop(); out.println(String.format("%c -> %c\n", s[before], s[after])); return true; } }

这个循环实际上是和递归相反的递推，目前只是看懂代码，还没有彻底理解逻辑。借鉴的这位c语言大神的，java翻译都不容易，java问题真多。

https://blog.csdn.net/yhf_naive/article/details/53384148

主要的是那个while循环，尤其是if中&&的两句，说实话不完全不晓得怎么推理来的。若没有那两句，可以知道是1-2，2-3，3-1的循环这是三组，每组首次移动到达的柱，不再移动，然后尝试继续移动到后面一个柱以外的另外一个柱上，出现失败的情况，换者尝试另外一个柱移动到开始元素所在柱上，嵌套着组不断循环，出现相互移动失败的情况则完成了。比较复杂，自己画画组图看看！

【本文地址】

公司简介

联系我们

汉诺塔从模型到实现 递归&循环两种方式 java

汉诺塔从模型到实现递归&循环两种方式 java