爬動的蠕蟲問題：井口逃脫的數學建模與代碼實現

題目：爬動的蠕蟲（ZJU PAT 循環-07）

一蠕蟲在深 n 寸的井底，每分鐘上爬 u 寸，下一分鐘下滑 d 寸，交替進行。問幾分鐘能爬出井口？

核心代碼

#include <stdio.h>

int main(void) {
    int n, u, d;
    scanf("%d %d %d", &n, &u, &d);
    int time = 0, distance = 0;
    do {
        time++;
        if (time % 2 != 0)      // 奇數分鐘：上爬
            distance += u;
        else                    // 偶數分鐘：下滑
            distance -= d;
    } while (distance < n);
    printf("%d\n", time);
    return 0;
}

關鍵邏輯分析

• 時間單位：題目隱含「每分鐘」交替爬滑，這是理解關鍵
• 終止條件：爬升過程中只要距離 ≥ n 即可，不需完成下滑
• 邊界情況：若 u ≥ n，第一分鐘即爬出，time=1

數學優化思路（大數據場景）

若 n 極大（如 10^9），模擬會超時。可用數學公式：

1. 每兩分鐘淨進度 = u - d
2. 最後一次爬升不需下滑
3. 設 k 為完整「爬+滑」週期數，則 k = ceil((n - u) / (u - d))
4. 總時間 = 2k + 1（若 n > u），否則 1

// 優化版 O(1) 算法
if (u >= n) { printf("1\n"); return 0; }
int net = u - d;
int k = (n - u + net - 1) / net;  // 向上取整
printf("%d\n", 2 * k + 1);

相關知識擴展

蠕蟲生物學小知識

• 「蠕蟲」非單一物種，泛指扁形動物、環節動物、紐形動物等無脊椎動物
• 非厭氧生物，多需氧或兼性厭氧
• 電腦病毒中的「蠕蟲」利用網絡漏洞自我複製傳播，與生物無關

考試應試技巧

1. 仔細閱讀題目隱含條件（如「每分鐘」）
2. 先寫模擬版保證正確，再考慮優化
3. 測試邊界：u≥n, u≤d(永遠爬不出), n=0
4. 注意整數溢出，大數據用 long long

題目鏈接

ZJU PAT Basic Programming - 循環-07 爬動的蠕蟲