培训制作网站源码,网盟推广和搜索推广的区别,免费自助在线公司起名,个人网店店铺名字汉诺塔 汉诺塔#xff08;Tower of Hanoi#xff09;#xff08;河内塔#xff09;#xff1a;把圆盘从下面开始按大小顺序重新摆放到另一根柱子上#xff0c;并且小圆盘上不能放大圆盘#xff0c;在三根柱子之间一次只能移动一个圆盘。 汉诺塔规则 disk表示圆盘数一次只… 汉诺塔 汉诺塔Tower of Hanoi河内塔把圆盘从下面开始按大小顺序重新摆放到另一根柱子上并且小圆盘上不能放大圆盘在三根柱子之间一次只能移动一个圆盘。 汉诺塔规则 disk表示圆盘数一次只能移动一个圆盘小圆盘只能在大圆盘的上方A 、B 、C分别表示圆柱A为起始圆柱、B为中转圆柱、C为终止圆柱 disk 1 时
移动次数为2^1 - 1
只需要将绿色圆盘从 A-C 直接移过去 A-C disk 2 时
移动次数为2^2 - 1一次只能移动一个圆盘
黄色圆盘从 A-B绿色圆盘从 A-C黄色圆盘从 B-C A-B A-C B-C disk 3 时
移动次数为2^3 - 1一次只能移动一个圆盘
粉色圆盘从 A-C黄色圆盘从 A-B粉色圆盘从 C-B绿色圆盘从 A-C粉色圆盘从 B-A黄色圆盘从 B-C粉色圆盘从 A-C A-C A-B C-B A-C B-A B-C A-C 递归分析 先看desk 3 个圆盘时我们是先将圆柱A上面的2个圆盘3 - 1借助圆柱C最终移动到圆柱B上此时圆柱A上就只剩1个圆盘就可以直接将圆盘从圆柱A移动到圆柱C desk 2个圆盘先将圆柱B上面的那1个圆盘2 - 1最终直接从圆柱B移动到圆柱A上此时圆柱B上就只剩1个圆盘就可以直接从圆柱B移动到圆柱C上 只剩最后1个圆盘了则是直接从圆柱A上移动到圆柱C上 disk n 时
移动次数为2^n - 1一次只能移动一个圆盘
错误递归分析 当desk n个圆盘时需要将圆柱A上面的n-1个圆盘借助圆柱C最终移动到圆柱B上此时圆柱A上就只剩1个圆盘则直接从圆柱A移动到圆柱C desk n 时先将圆柱B上面的n-1个圆盘借助圆柱C最终移到圆柱A上此时圆柱A上有n-1个圆盘递归以上步骤 当 desk n-1时需要将圆柱A上面的(n-1) - 1个圆盘借助圆柱C移到圆柱B上这里已经在开始和desk n 的情况一样此时圆柱A上就只剩1个圆盘则直接从圆柱A移动到圆柱C desk n-1时先将圆柱B上面的(n-1) - 1个圆盘借助圆柱C最终移到圆柱A上此时圆柱A上有(n-1) - 1个圆盘递归以上步骤 错误代码分析
public class TowerOfHanoi {public static void hanoi(int n, char posA, char posB, char posC) {// hanoi(圆盘个数参数1参数2参数3)// 参数1表示起始位置、参数2表示中转位置、参数3表示终止位置if(n 1) {move(posA, posC);return; // 递归一定要return}// 这一步就是将 圆柱A 上的 n-1个 圆盘// 借助圆柱C 移动到 圆柱B上hanoi(n-1, posA, posC, posB);// 将圆柱A上剩下的一个移到圆柱C上move(posA, posC);// 将 圆柱B 上的所有圆盘 借助圆柱C 移到圆柱A上hanoi(n-1, posB, posC, posA); // 这里是错的}public static void move(char pos1, char pos2) {System.out.println(pos1 - pos2);}public static void main(String[] args) {hanoi(3, A, B, C);}
} 正确递归分析 当desk n个圆盘时需要将圆柱A上面的n-1个圆盘借助圆柱C最终移动到圆柱B上此时圆柱A上就只剩1个圆盘则直接从圆柱A移动到圆柱C将圆柱B上的n-1个圆盘借助圆柱A最终移动到圆柱C上此时圆柱B上就只剩一个圆盘则直接从圆柱B移动到圆柱C 正确代码分析
public class TowerOfHanoi {public static void hanoi(int n, char posA, char posB, char posC) {// hanoi(圆盘个数参数1参数2参数3)// 参数1表示起始位置、参数2表示中转位置、参数3表示终止位置if(n 1) {move(posA, posC);return; // 递归一定要return}// 这一步就是将 圆柱A 上的 n-1个 圆盘// 借助圆柱C 移动到 圆柱B上hanoi(n-1, posA, posC, posB);// 将圆柱A上剩下的一个移到圆柱C上move(posA, posC);hanoi(n-1, posB, posA, posC);}public static void move(char pos1, char pos2) {System.out.println(pos1 - pos2);}public static void main(String[] args) {hanoi(3, A, B, C);}
}
