Strange Towers of Hanoi (POJ1958)

柔光的暖阳◎ 2021-12-22 15:34 312阅读 0赞

Strange Towers of Hanoi (POJ1958)

n个盘子4座塔的Hanoi问题至少需要多少步?(1<=n<=12)

分析:

n盘3塔: \(d[n] = 2*d[n-1]+1\) => \(d[n] = 2^n - 1\)

  1. 前n-1盘子 A -> B
  2. 第n盘子 A -> C
  3. 前n-1盘子 B -> C

n盘4塔:\(f[n] = min_{1\leq i<n}\{2*f[i] + d[n-i]\}\)

  1. 把i个盘子 A->B (四塔模式)
  2. 把n-i个盘子 A->D (三塔模式)
  3. 把i个盘子 B-> D (四塔模式)
  4. 考虑所有可能i取最小值

题解:

  1. #include<iostream> #include<cmath> using namespace std; int main(){ int f[13] = {0}; int minstep,step; f[1] = 1; for(int n=2;n<=12;n++){ minstep = 0x3f3f3f3f; step=0; for(int i=1;i<n;i++){ step = 2*f[i] + pow((float)2,n-i)-1; //POJ C++的pow格式严格 if(step<minstep) minstep = step; } f[n] = minstep; } for(int n=1;n<=12;n++){ cout<<f[n]<<endl; } return 0; }

转载于:https://www.cnblogs.com/wendiudiu/p/10762157.html

发表评论

表情:
评论列表 (有 0 条评论,312人围观)

还没有评论,来说两句吧...

相关阅读

    相关 uva 437——The Tower of Babylon

    题意:给定n个长方体,然后堆积最高的塔,要求上面的面积小于下面的面积。 思路:Dp,先把长方体的所有放的情况都构造出来放到数组里,对于当前节点,如果能够在

    相关 1958 刺激 (dfs)

    题目描述 Description saffah的一个朋友S酷爱滑雪,并且追求刺激(exitement,由于刺激过度导致拼写都缺了个字母),喜欢忽高忽低的感觉。现在S拿到了一张