BNU 34978 漢諾塔期望步數 - 動態規劃推導遞推公式

遞推關係推導

考慮最大盤子 n 的隨機放置：

• 概率 1/3 放到目標柱子 3：需先將 n-1 個盤子移到柱子 2（期望 dp[n-1]），再將它們移到柱子 3（標準步數 f[n-1]），共 dp[n-1] + f[n-1] + 1 步（+1 為移動盤子 n）。
• 概率 1/3 放到起始柱子 1：需將 n-1 個盤子移到柱子 2（dp[n-1]），移動盤子 n 到柱子 3（1 步），再將 n-1 個盤子從柱子 2 移到柱子 3（標準 f[n-1]），共 dp[n-1] + f[n-1] + 1 步。
• 概率 1/3 放到中間柱子 2：直接進入 n-1 盤子的隨機過程，期望 dp[n-1] 步。

計算

預計算 f[i] 和 dp[i] 至 i=100，每組查詢 O(1) 輸出 dp[n] 保留兩位小數。

參考代碼 (C++)

#include <cstdio>
const int N = 105;
double f[N], dp[N];

int main() {
    f[1] = 1;
    for (int i = 2; i < N; ++i) f[i] = 2*f[i-1] + 1;
    dp[1] = 2.0/3;
    for (int i = 2; i < N; ++i)
        dp[i] = dp[i-1] + 2.0/3 * (f[i-1] + 1);
    int T, n; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%.2f\n", dp[n]);
    }
    return 0;
}