gpt4 book ai didi

java - 汉诺塔 : Finding the n-th configuration

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:12:50 25 4
gpt4 key购买 nike

我想在给定圆盘数和移动数的情况下找到解决汉诺塔问题的第 n 个配置。

以下代码使用尾递归找到第 n 步:


public static String N_th_Move(int k_discs, int move){
return HanoiRec(k_discs, move, "A", "B", "C");
}

private static String HanoiRec(int k_discs, int move, String rod_a, String rod_b, String rod_c) {
int max_n_moves = (int) (Math.pow(2, k_discs) - 1);
int bound =(int) Math.pow(2, k_discs - 1);
if(move > max_n_moves){
return "Not valid";
} else if(move == bound ){
return rod_a + " -> " + rod_b;
} else if(move < bound){
return HanoiRec(k_discs-1, move , rod_a, rod_c, rod_b);
} else {
return HanoiRec(k_discs-1, move - bound, rod_c, rod_b, rod_a);
}
}


如何使用相同的方法找到第 n 个配置?

例如:

N_th_configuation(3, 4) #{rod_a: 0, rod_b: 1, rod_c: 2}

添加:3 个圆盘的二叉树(遵循上述代码):


(0 1 2)
/ \
(1 1 1) (0 2 1)
/ \ / \
(2 1 0) (1 0 2) (1 1 1) (0 3 0)

其中第一个数字是 rod_a 上的圆盘数,第二个是 rod_b 上的圆盘数,第三个是 rod_c 上的圆盘数。左下角的叶子是第一次移动后的配置,右下角的叶子是最后一次移动后的配置。我没有找出所有配置之间的关系。

最佳答案

ToH 的规范解决方案是交替使用两种类型的移动:

  1. 将最小的圆盘移动到下一根杆(环绕回到初始杆)
  2. 做出包含最小圆盘的合法移动。

wlog(不失一般性),让我们假设最小的圆盘总是移动到下一个更高编号的杆(标记为 0、1、2)。

该算法的一个结果是奇数盘移动得更高;偶数盘向下移动。

另一个结果是,您可以独立确定任何给定移动编号的圆盘:它是该数字的二进制表示中值最低的 1 位。例如,对于 3 盘问题:

Move  binary disc
1 001 1
2 010 2
3 011 1
4 100 3
5 101 1
6 110 2
7 111 1

要找到匹配任何移动 N 的位置:

  1. 将二进制文件分成单独的数字。
  2. 屏蔽掉每个位中最右边的 1 位。
  3. 添加列。
  4. 对偶数列求反(以表明圆盘向相反方向移动。
  5. 减少总模数 3。

结果是每个圆盘所在的列的列表。

关于java - 汉诺塔 : Finding the n-th configuration,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56495058/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com