数学中国

用户名  找回密码
 注册
帖子
热搜: 活动 交友 discuz
查看: 7203|回复: 18

汉诺塔的确切解

[复制链接]
发表于 2016-6-11 07:47 | 显示全部楼层 |阅读模式
大家好,我叫陈墨仙,毕业于西安电子科技大学,就职于网龙天晴在线任务设计部,是一名脚本程序员

(服务器端)。

我似乎发现了汉诺塔的确切解。目前先把猜想发上来,一会儿我将写一个程序来证明。

假设

1
2
3
——  —— ——
1柱子 2柱子3柱子


要把这1到3号从1柱子移到3柱子。

目标柱子:3
本身柱子:1
中间柱子:2

本身柱子上的数量是3。

3mod2=1

所以第一个1号盘子,要移到目标柱子上。

2
3            1
——  —— ——
1柱子 2柱子3柱子

接下来,目标柱子是空的,本身柱子上的数量是2。

2mod2=0

所以本身柱子上,最上面的2号盘,要移到中间柱子上。

3      2     1
——  —— ——
1柱子 2柱子3柱子


接下来,目标柱子和中间柱子都有盘子。本身柱子1上的数量为1。
1mod2=1。
所以目前要把目标柱子上的盘子往中间柱子移。
这时候,
第二层
目标柱子:2
本身柱子:3
中间柱子:1

本身柱子3上的数量为1,
1mod2=1
所以要把3柱子上的1号盘子往目标柱子上移。
       1
3      2     
——  —— ——
1柱子 2柱子3柱子

等到第二层本身柱子3空了,又恢复成

目标柱子:3
本身柱子:1
中间柱子:2

好了,目前本身柱子上的盘子数量为1
1mod2=1。
所以1柱子上的3盘子,要移到目标柱子3上。
       1
       2    3
——  —— ——
1柱子 2柱子3柱子

这时候,本身柱子1空了,目标,本身,中间再次变化。

本身柱子:2
目标柱子:3
中间柱子:1

本身柱子盘子数量2,
2mod2=0
所以2号柱子上的1号盘子,要移到中间柱子上。

      
  1    2    3
——  —— ——
1柱子 2柱子3柱子

本身柱子盘子数量1,
1mod2=1
所以2号柱子上的2号盘子,要移到目标柱子上。
            2
  1         3
——  —— ——
1柱子 2柱子3柱子

本身柱子空了,本身,目标,中间柱子再次变化。

由2->3变为1->3

本身柱子1号柱子的数量为1
1mod2=1
所以,将1号柱子上的1号盘,移到目标柱子上。

            1
            2
  1         3
——  —— ——
1柱子 2柱子3柱子

综上所述,若本身柱子数量对2取模,值为1,则移到目标柱子上,若值为0,则移到中间柱子上。

若本身柱子盘子数为0,则变换目标和本身,中间柱子。

1->3变为2->3

若目标柱子和中间柱子都有盘子,则进入第二层目标,本身,中间柱子。

若第一层本身柱子数量对2取模,值为1,则第二层目标柱子为第一层的中间柱子,第二层本身柱子为第

一层的目标柱子。
若值为0,则反过来。

还有一种更方便的判断方法,即看柱子上的盘子大小来判断目标柱子和本身柱子。
 楼主| 发表于 2016-6-11 08:52 | 显示全部楼层
排版有点乱……

核心思路就是 本身柱子的数量mod2若为1,则将最上方的盘子移到目标柱子,若为0,则移到中间柱子。

至于本身柱子是哪个,目标柱子是哪个,肉眼可以看出来。但是具体的量化规则,得让我想想。
 楼主| 发表于 2016-6-11 09:11 | 显示全部楼层
我们现在来看看6个盘子的情况。

1
2
3
4
5
6
——  —— ——
1柱子 2柱子3柱子

用倒推法,要把6个盘子移到3柱子上,则
需要
        1
        2
        3
        4
6       5
——  —— ——
1柱子 2柱子3柱子

             1
             2
             3      
6       5    4
——  —— ——
1柱子 2柱子3柱子

        1
5       2            
6       3     4
——  —— ——
1柱子 2柱子3柱子


4        
5            1      
6       3    2
——  —— ——
1柱子 2柱子3柱子

2
3
4        
5                  
6       1   
——  —— ——
1柱子 2柱子3柱子

也就是说5号盘要移到2号柱子上,4号盘要移到3号柱子上,3号盘2号,2号盘3号,1号盘2号。规律是n号盘,(6-n)mod2,若为1,则中间柱子,2号,若为0,则目标柱子,3号。

而移动的方法,就是我刚才用123个盘子进行移动的方法。
 楼主| 发表于 2016-6-11 09:17 | 显示全部楼层
:lol不知道我讲清楚没有。

按我说的方法,玩文曲星上的汉诺塔,是可以通关的。(十几年前的游戏了吧!)

:Q:Q
 楼主| 发表于 2016-6-11 09:24 | 显示全部楼层

怎么获取具体某一步的移法?

还是以6个盘子为例,假设我们想知道3号盘子第二次移动,是从哪移到哪。

首先(6-3)mod2=1,则3号盘子第一次移动应该是中间柱子,2号,即1->2

这个时候,柱子为

4        
5            1      
6       3    2
——  —— ——
1柱子 2柱子3柱子

那么接下来与三号盘无关的移动直到

        1
5       2            
6       3     4
——  —— ——
1柱子 2柱子3柱子

(3-3)mod2=0,即3号盘要移到目标柱子3号柱子。
所以3号盘第二次移动是,2->3。
 楼主| 发表于 2016-6-11 09:34 | 显示全部楼层
所以1号盘的第一次移动是
(6-1)mod2=1,移到中间位置,1->2
本身柱子与中间柱子互换,目标柱子不变
第二次一定是移到目标位置,2->3
本身柱子与目标柱子互换,中间柱子不变
第三次移到中间位置,3->1
本身柱子与中间柱子互换,目标柱子不变
第四次移到目标位置,1->2



也即是说奇数次,移到中间位置,偶数次移到目标位置。移动之后,本身柱子与中间或目标柱子互换身份。
 楼主| 发表于 2016-6-11 09:47 | 显示全部楼层
本帖最后由 高冷宅小胖妞 于 2016-6-11 11:23 编辑

我们再抽象归纳一下。

6个盘子,1号盘的第n次是怎么移动的函数设为(f,k)(n)
f为源位子,k为目标位子。

f(1)=1
f(n)=k(n-1)
k(n)=3-((n mod 3-2)mod 3)
 楼主| 发表于 2016-6-11 10:36 | 显示全部楼层
从上面我们可以得知,如果盘号的奇偶性一样的话,那么他们前n次移动的顺序是一样的。
 楼主| 发表于 2016-6-11 10:50 | 显示全部楼层
本帖最后由 高冷宅小胖妞 于 2016-6-11 10:54 编辑

从上面我们可以得知,如果盘号的奇偶性一样的话,那么他们前n次移动的顺序是一样的。

所以我们又可以简化为,若总共有偶数个盘子,偶数号盘的第n次是怎么移动的。
或者,若总共有奇数个盘子,奇数号盘的第n次是怎么移动的。

k(n,总共偶数,盘号偶数)= 3-((n mod 3)-1)mod3
k(n,总共偶数,盘号奇数)= 3-((n mod 3)-2)mod3
您需要登录后才可以回帖 登录 | 注册

本版积分规则

LaTEX预览输入 教程 符号库 加行内标签 加行间标签 
对应的 LaTEX 效果:

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2025-7-10 23:01 , Processed in 0.096592 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表
\frac{\square}{\square}\sqrt{\square}\square_{\baguet}^{\baguet}\overarc{\square}\ \dot{\baguet}\left(\square\right)\binom{\square}{\square}\begin{cases}\square\\\square\end{cases}\ \begin{bmatrix}\square&\square\\\square&\square\end{bmatrix}\to\Rightarrow\mapsto\alpha\ \theta\ \pi\times\div\pm\because\angle\ \infty
\frac{\square}{\square}\sqrt{\square}\sqrt[\baguet]{\square}\square_{\baguet}\square^{\baguet}\square_{\baguet}^{\baguet}\sum_{\baguet}^{\baguet}\prod_{\baguet}^{\baguet}\coprod_{\baguet}^{\baguet}\int_{\baguet}^{\baguet}\lim_{\baguet}\lim_{\baguet}^{\baguet}\bigcup_{\baguet}^{\baguet}\bigcap_{\baguet}^{\baguet}\bigwedge_{\baguet}^{\baguet}\bigvee_{\baguet}^{\baguet}
\underline{\square}\overline{\square}\overrightarrow{\square}\overleftarrow{\square}\overleftrightarrow{\square}\underrightarrow{\square}\underleftarrow{\square}\underleftrightarrow{\square}\dot{\baguet}\hat{\baguet}\vec{\baguet}\tilde{\baguet}
\left(\square\right)\left[\square\right]\left\{\square\right\}\left|\square\right|\left\langle\square\right\rangle\left\lVert\square\right\rVert\left\lfloor\square\right\rfloor\left\lceil\square\right\rceil\binom{\square}{\square}\boxed{\square}
\begin{cases}\square\\\square\end{cases}\begin{matrix}\square&\square\\\square&\square\end{matrix}\begin{pmatrix}\square&\square\\\square&\square\end{pmatrix}\begin{bmatrix}\square&\square\\\square&\square\end{bmatrix}\begin{Bmatrix}\square&\square\\\square&\square\end{Bmatrix}\begin{vmatrix}\square&\square\\\square&\square\end{vmatrix}\begin{Vmatrix}\square&\square\\\square&\square\end{Vmatrix}\begin{array}{l|l}\square&\square\\\hline\square&\square\end{array}
\to\gets\leftrightarrow\nearrow\searrow\downarrow\uparrow\updownarrow\swarrow\nwarrow\Leftarrow\Rightarrow\Leftrightarrow\rightharpoonup\rightharpoondown\impliedby\implies\Longleftrightarrow\leftharpoonup\leftharpoondown\longleftarrow\longrightarrow\longleftrightarrow\Uparrow\Downarrow\Updownarrow\hookleftarrow\hookrightarrow\mapsto
\alpha\beta\gamma\Gamma\delta\Delta\epsilon\varepsilon\zeta\eta\theta\Theta\iota\kappa\varkappa\lambda\Lambda\mu\nu\xi\Xi\pi\Pi\varpi\rho\varrho\sigma\Sigma\tau\upsilon\Upsilon\phi\Phi\varphi\chi\psi\Psi\omega\Omega\digamma\vartheta\varsigma\mathbb{C}\mathbb{H}\mathbb{N}\mathbb{P}\mathbb{Q}\mathbb{R}\mathbb{Z}\Re\Im\aleph\partial\nabla
\times\cdot\ast\div\pm\mp\circ\backslash\oplus\ominus\otimes\odot\bullet\varnothing\neq\equiv\not\equiv\sim\approx\simeq\cong\geq\leq\ll\gg\succ\prec\in\ni\cup\cap\subset\supset\not\subset\not\supset\notin\not\ni\subseteq\supseteq\nsubseteq\nsupseteq\sqsubset\sqsupset\sqsubseteq\sqsupseteq\sqcap\sqcup\wedge\vee\neg\forall\exists\nexists\uplus\bigsqcup\bigodot\bigotimes\bigoplus\biguplus\bigcap\bigcup\bigvee\bigwedge
\because\therefore\angle\parallel\perp\top\nparallel\measuredangle\sphericalangle\diamond\diamondsuit\doteq\propto\infty\bowtie\square\smile\frown\bigtriangledown\triangle\triangleleft\triangleright\bigcirc \wr\amalg\models\preceq\mid\nmid\vdash\dashv\nless\ngtr\ldots\cdots\vdots\ddots\surd\ell\flat\sharp\natural\wp\clubsuit\heartsuit\spadesuit\oint\lfloor\rfloor\lceil\rceil\lbrace\rbrace\lbrack\rbrack\vert\hbar\aleph\dagger\ddagger

MathQuill输入:

Latex代码输入: