首页 > 其他 > 详细

BZOJ 1009 [汉诺塔]

时间:2020-01-22 01:17:38      阅读:133      评论:0      收藏:0      [点我收藏+]

题面

题意

??对于 \(n\) 层的汉诺塔,将一个盘子从一个柱子挪到另一个柱子,这样的操作一共有六种:AB,AC,BC,BA,CA,CB,对这六种操作给出优先级,每一次从所有合法的操作中选择出上一次没有移动过的盘子中操作优先级最高的操作执行,求出需要的步数。

题解

??假设空的塔底有无穷大的盘子。只考虑塔顶的盘子,每次只可能移动最小的和次小的两个盘子,而移动次小的盘子之后,次小的盘子依旧是下一时刻次小的盘子,所以最小和次小的盘子必定有一个在上一时刻被移动过,所以操作只可能是移动最小的盘子到优先级较高的堆上,以及移动次小的盘子到最大的盘子上这两个步骤的循环。

??因为优先级只对最小的盘子有影响,而最小的盘子每次操作时的开始位置都确定,所以只有从同一盘子出发的操作优先级才有意义。而根据上面步骤是循环的结论,我们已经可以模拟出最小的盘子的移动轨迹。不妨令第一个塔出发到第二个塔的优先级比到第三个塔上高(如非如此,交换第二个塔和第三个塔),这样,最小的盘子的轨迹只有三种情况:\(1,2,3,1,2,3,\dots\)\(1,2,1,2,\dots\)\(1,2,3,2,3,\dots\)

??以 \(n=4\) 为例,对于三种情况分别模拟所有盘子的移动轨迹,其中除第一列外,第 \(i\) 行第 \(j\) 列上有数字代表第 \(j\) 次操作时第 \(i\) 个盘子移动到了数字表示的塔上:

  1. \(1,2,3,1,2,3,\dots\)
    \[\begin{aligned} 1&\;&2 &\;&3 &\;&1 &\;&2 &\;&3 &\;&1 &\;&2 &\;&3 \1&\;&\;&3 &\;&\;&\;&2 &\;&\;&\;&1 &\;&\;&\;&3 &\;\1&\;&\;&\;&\;&2 &\;&\;&\;&\;&\;&\;&\;&3 &\;&\;&\;\1&\;&\;&\;&\;&\;&\;&\;&\;&3 &\;&\;&\;&\;&\;&\;&\;\\end{aligned}\]

BZOJ 1009 [汉诺塔]

原文:https://www.cnblogs.com/Kilo-5723/p/12227494.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!