hdu 2064 2077 汉诺塔变形

没什么,都是推公式。2064中设n个盘子需要g(n)步,则g(n)=3*g(n-1)+2,很好想,从而得通项公式g(n)=3^n-1;2077中加了一个条件,难想一些,为了便于说明,我们把三根柱子分别记为柱A、柱B、柱C,第n个盘子记为盘n,那么最优情况肯定是先把上面n-2个盘子移到柱C上,再把盘n-1和盘n依次移到柱B上,然后把柱C上的n-2个盘子移回柱A,接着把盘n-1和盘n移到柱C上,最后再把n-2个盘子移到柱C即可,这个过程中,把n-2个盘子从柱A移到柱C(或反向移动)的过程与2064题是完全一样的。故移动n个盘子的步数f(n)=3*g(n-2)+4,代入上面的通项公式得f(n)=3^(n-1)+1

原文地址:https://www.cnblogs.com/moonbay/p/2122923.html