POJ 1958 Strange Towers of Hanoi

      重温汉诺塔~~
      这题题很长，也蛮吓人的，可是仔细一想是道很简单的DP。关键在于找到基本的公式，即3阶Hanoi的步数。其实也不难，和我们当时学习递归的思想是一样的，考虑3阶汉诺塔，要移动n个盘子，则必须先将前n-1个盘子放到柱子2上，将最大的盘子放到柱子3上，再将n-1个盘子放到柱子3上，第1步和第3步就是将n-1个盘子的3阶Hanoi放法。故有：
      hanoi3[1]= 1;
      hanoi3[i]= hanoi3[i-1]*2+ 1;
      对于4阶，题目给出了思路，很容易写出状态转移方程：
      hanoi4[i]= min( hanoi4[j]*2+ hanoi3[i-j] ), j= 1~i-1
下面是实现代码：

#include <iostream>

using namespace std;

int hanoi3[13], hanoi4[13];

int main(){

int i, j;

hanoi3[1]= hanoi4[1]= 1;

puts("1");

for( i= 2; i<= 12; i++ )

hanoi3[i]= 2*hanoi3[i-1]+1;

for( i= 2; i<= 12; i++ ){

hanoi4[i]= 2+hanoi3[i-1];

for( j= 2; j< i; j++ )

if( hanoi4[i]> 2*hanoi4[j]+hanoi3[i-j] )

hanoi4[i]= 2*hanoi4[j]+hanoi3[i-j];

printf("%d\n",hanoi4[i]);

}

return 0;

}

posted on 2009-06-22 15:50 古月残辉阅读(599) 评论(0) 编辑收藏引用所属分类: POJ

常用链接

留言簿(3)

随笔分类(18)

随笔档案(20)

文章分类(36)

文章档案(36)

新闻档案(1)

牛人博客

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

只有注册用户登录后才能发表评论。


相关文章: POJ 3122 Pie POJ 1140 Expanding Fractions POJ 1013 Counterfeit Dollar POJ 1958 Strange Towers of Hanoi POJ 1915 Knight Moves POJ 1837 Balance POJ 1556 The Doors Bellman-Ford 1631 Bridging signals 1606 Jugs (3414 Pots)

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理