必威体育Betway必威体育官网
当前位置:首页 > IT技术

对hanoi问题的理解

时间:2019-09-30 19:13:24来源:IT技术作者:seo实验室小编阅读:64次「手机版」
 

hanoi

首先,我谈一下自己对原版hanoi问题递归公式的推导。

优秀的理解网址,有图形

我按照他的,也就是将A上的n个圆盘(编号从下往上是n->1)通过B移动到C。

首先,在什么也不知道的情况下,我自己模拟一下,来发现规律(不会画图,自己在草稿本上画吧)。

首先是1->C,2->B,然后就是1->B(先不要直接1->A,否则不利于找出子过程),现在的情况是A:n->3,B:2->1,C没有.然后就发现(有一种直接用n=1,n=2,n=3来发现子过程),就是将1->n-1先移动到B,然后将n移动到C,此时C相当于空的(因为最大的在下面)然后将剩余的1->n-1通过中间C移动到B,最后的递归条件就是n=1.

通俗地讲就是,现将最大的那个移动到C,这就现要求将上面的1->n-1先移动到B。然后C相当于空的,所以此时,规模为n-1的问题与原问题形式一样,全部在一个柱子上,然后通过一个空的柱子,全部移动到另外一个柱子上。然后就可以递归了。知道规模缩小到n=1,虽然我并不知道,具体如何将1->n-1移动到C。

 public static void hanoi(int n,char A,char B,char C)
    {
        if(n == 1)//圆盘只有一个时,只需将其从A塔移到C塔
            TowersOfHanoi.move(1, A, C);//将编b号为1的圆盘从A移到C
        else
        {//否则
            hanoi(n - 1, A, C, B);//递归,把A塔上编号1~n-1的圆盘移到B上,以C为辅助塔
            TowersOfHanoi.move(n, A, C);//把A塔上编号为n的圆盘移到C上
            hanoi(n - 1, B, A, C);//递归,把B塔上编号1~n-1的圆盘移到C上,以A为辅助塔
        }
    }

然后就是对代码的理解,函数的声明意思是:现在规模为n的hanoi(相当于A:1->n,B:0,C:0),将A上的n个圆盘通过B移动到C.

函数内部的理解:首先是递归结束条件。然后:三个核心子过程,将1->n-1从目前认为的A(等价意义,比如现在的C相当于原来的A)通过C移动到B,然后将最下面的n从A移动到C,最后将1->n-1从B通过A移动到C。

至于n=x时要操作多少次,可以打表观察规律,也可以理论分析出来。

这个对思维能力还是要求比较高,不过还是递归蛮有意思,将一个复杂问题简单化。

hanoi变式题-HDU集锦

相关阅读

做私域流量前,先想想这三个问题

自从微信封杀朋友圈诱导分享后,运营的裂变之道开始寻求一条新出路,而私域流量成为了解决这个问题的答案。但是提到私域流量的人很多

解决sql server2008数据库安装之后,web程序80端口被占

前言: 原来电脑上的Apache一直使用正常,在安装sql server2008后,突然发现Apache无法启动,检查了一下是因为80端口被强制占用了。 解

关于无法进入电子科大信息门户的相关问题研究

关键词: 电子科大信息门户进不去   192.168.1.1用户名或密码有误   路由器设置经验1:如果按官方给出的两个方法做了还是进不去

0-1背包问题、贪心算法、动态规划

1、0-1背包问题  0-1背包问题:有一个贼在偷窃一家商店时,发现有n件物品,第i件物品价值vi元,重wi磅,此处vi与wi都是整数。他希望带走

如何解决浏览网页出现http404错误问题

我最近发现一个问题,在浏览我经常浏览的一些网站时,浏览器总是提示http 404错误,无法找到文件。起初,以为是该网站在进行日常维护,打开

分享到:

栏目导航

推荐阅读

热门阅读