首页 > 代码库 > BNU 34978 汉诺塔 求期望步数
BNU 34978 汉诺塔 求期望步数
题目链接:点击打开链接
我们用dp[i]表示 随机i个盘子时,恢复原位需要的步数的期望
f[i]表示i个盘子下普通的汉诺塔玩法的步数
既然是随机,那么我们就认为是在上一次随机的情况下,
把第n个放到任意一根柱子的底部
那么若随机放到了第3个柱子,则步数就是dp[n-1]
若放到了第1根柱子,则先把前面的n-1个盘子移动到第2根柱子上,花费是dp[n-1]
然后再把n盘子移动到第三根柱子,再把其他盘子移动到第三根柱子, 花费是 1+f[n-1]
就是这样_(:зゝ∠)_
#include <cstdio> #include <iostream> #include <algorithm> #include <string.h> #include <vector> #include <cmath> using namespace std; #define N 100 #define ll long long ll n; double f[N]; double dp[N]; int main() { f[1] = 1.0; for(int i = 2; i < N; i++) f[i] = f[i-1]*2.0+1.0; dp[1] = 0.666666666666666; for(int i = 2; i < N; i++) dp[i] = dp[i-1]/3.0 + 2.0 * (dp[i-1] + f[i-1] +1.0) / 3.0; int T, j;scanf("%d",&T); while(T--) { scanf("%d",&j); printf("%.2f\n", dp[j]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。