44 lines
2.2 KiB
JavaScript
44 lines
2.2 KiB
JavaScript
/**
|
||
有三根柱子，分别命名为 A、B、C。A 上有若干个盘子，盘子的大小不等，且每个盘子都可以放在另一根柱子上。要求从柱子 A 上将所有盘子移动到柱子 C 上，且必须遵守以下规则：
|
||
|
||
一次只能移动一个盘子。
|
||
每次移动时，盘子只能从柱子顶部移动，且一个盘子不能放在比它小的盘子上。
|
||
目标是使用柱子 B 作为辅助柱子，最少移动次数将盘子从柱子 A 移动到柱子 C。
|
||
*/
|
||
|
||
/**
|
||
*
|
||
* @param {number} n 汉诺塔问题的规模
|
||
* 思路：假设我们只有两个盘子，只需要把小盘子移动到B柱上，再把大盘子移动到C柱子上，最后把小盘子从B柱移动到C柱子，我们把问题做一个抽象，假设有三个盘子，因为要想移动
|
||
* 大盘子就必须把它上面的所有小盘子移动到B住上去，之后才能把这个大盘子移动到C柱，至于怎么移动我不管
|
||
*
|
||
* 分析：假设现在有三个盘子，第一步我们发现底部的盘子无法直接移动，把问题抽象为移动n-1个盘子，在这里就是移动上面的两个盘子，之后会发现第二个盘子也移不动，所以再把问题抽象为
|
||
* (n-1)-1,也就是移动第一个盘子，第一个盘子可以直接移动，这样就可以把第一个盘子移动到B上，第二个盘子移动到C,......
|
||
*/
|
||
function towerOfHanoi(n) {
|
||
// 将n个盘子从A借助B移动到C
|
||
howToMove(n, 'A', 'C', 'B');
|
||
}
|
||
|
||
/**
|
||
* @param {*} n 要移动的所有盘子
|
||
* @param {*} from 初始位置
|
||
* @param {*} to 目标位置
|
||
* @param {*} aux 辅助柱
|
||
*/
|
||
function howToMove(n, from, to, aux) {
|
||
// 如果只有一个盘子那就直接移动到目标位置即可（这也是递归结束的条件）
|
||
if (n === 1) {
|
||
console.log(`${n} 从 ${from} 移动到 ${to}`);
|
||
return;
|
||
}
|
||
// 1.移动n-1个盘子，因为如果不把所有的小盘子移动到辅助位置，大盘子就不可能移动到目标位置
|
||
howToMove(n - 1, from, aux, to);
|
||
// 2.将大盘子移动到目标位置
|
||
console.log(`${n} 从 ${from} 移动到 ${to}`);
|
||
// 3.将剩下的所有盘子从辅助位置移动到目标位置
|
||
howToMove(n - 1, aux, to, from);
|
||
}
|
||
|
||
towerOfHanoi(3);
|