题目链接：点击打开链接

我们用dp[i]表示 随机i个盘子时，恢复原位需要的步数的期望

f[i]表示i个盘子下普通的汉诺塔玩法的步数

既然是随机，那么我们就认为是在上一次随机的情况下，

把第n个放到任意一根柱子的底部

那么若随机放到了第3个柱子，则步数就是dp[n-1]

若放到了第1根柱子，则先把前面的n-1个盘子移动到第2根柱子上，花费是dp[n-1]

然后再把n盘子移动到第三根柱子，再把其他盘子移动到第三根柱子， 花费是 1+f[n-1]

就是这样_(:з?∠)_

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         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; }