a227 - 三龍杯 -> 河內之塔

🔗 前往 ZeroJudge 原題

題目描述

題目要求輸出將 N 個環從 A 柱移動到 C 柱的步驟，遵循河內之塔的規則：每次只能移動一個環，且大環必須在小環下方。

解題思路

河內之塔是一個經典的遞迴問題。解決方案的核心思想是：

1. 將 N-1 個環從 A 柱移動到 B 柱，使用 C 柱作為輔助。
2. 將第 N 個環從 A 柱移動到 C 柱。
3. 將 N-1 個環從 B 柱移動到 C 柱，使用 A 柱作為輔助。

f(n, s, t) 函數表示將 n 個環從起始柱 s 移動到目標柱 t。其中，198-s-t 計算的是剩餘的輔助柱。

複雜度分析

• 時間複雜度: O(2^n)
• 空間複雜度: O(n)

程式碼

#include <stdio.h>
int f(int n,int s,int t){
    if(n==0) return 0;
    f(n-1,s,198-s-t);
    printf("Move ring %d from %c to %c\n",n,s,t);
    f(n-1,198-s-t,t);
    return 0;
}
int main(){
    int m;
    while(scanf("%d",&m)>0)
    	f(m,65,67);
}