C 語言演算法：整數分解為奇數和的遞迴解法完整解析

問題定義

輸入正整數 N，求將 N 分解為奇數之和的不同排列組合總數。順序不同視為不同分解方式。
範例：N=5 時，分解方式有 5 種：
1+1+1+1+1、1+1+3、1+3+1、3+1+1、5

遞迴解法分析

此問題屬於典型的整數分割問題，但限制為奇數且考慮順序。遞迴關係式為：

f(n) = Σ f(n - i) ，其中 i 為小於等於 n 的正奇數

邊界條件：f(0) = 1（空分解視為 1 種），f(n) = 0 當 n < 0。

程式碼實現

unsigned int calc(unsigned int n) {
    if (n == 0) return 1;  // 邊界條件修正：空分解算 1 種
    
    unsigned int sum = 0;
    for (unsigned int i = 1; i <= n; i += 2) {  // 遍歷所有可能的奇數
        sum += calc(n - i);
    }
    return sum;
}

// 測試主程式
#include <stdio.h>

int main() {
    for (int n = 1; n <= 10; n++) {
        printf("N=%d: %u 種分解方式\n", n, calc(n));
    }
    return 0;
}

執行結果

N=1: 1 種分解方式
N=2: 1 種分解方式
N=3: 2 種分解方式
N=4: 3 種分解方式
N=5: 5 種分解方式
N=6: 8 種分解方式
N=7: 13 種分解方式
N=8: 21 種分解方式
N=9: 34 種分解方式
N=10: 55 種分解方式

數學規律發現

結果序列為：1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
這正是費波那契數列！
證明：f(n) = f(n-1) + f(n-2) （n ≥ 2）

優化版本：動態規劃

遞迴版本重複計算多，時間複雜度指數級。動態規劃降為 O(N)：

unsigned int calc_dp(unsigned int n) {
    if (n == 0) return 1;
    unsigned int* dp = (unsigned int*)calloc(n + 1, sizeof(unsigned int));
    dp[0] = 1;
    for (unsigned int i = 1; i <= n; i++) {
        for (unsigned int odd = 1; odd <= i; odd += 2) {
            dp[i] += dp[i - odd];
        }
    }
    unsigned int result = dp[n];
    free(dp);
    return result;
}

進階擴展

• 若不考慮順序（組合數），需修改迴圈順序
• 若允許偶數，移除 i += 2 改為 i++
• 大數處理：使用大整數庫或字串模擬加法

掌握遞迴思維與動態規劃優化，是解決組合數學類演算法題的關鍵鑰匙。