随笔-20  评论-16  文章-36  trackbacks-0
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 古月残辉 阅读(621) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 古月残辉