【破解硬幣組合難題】C語言編程實戰指南

引言

硬幣組剖析績是一個經典的編程成績，它涉及到算法計劃跟靜態打算的不雅點。在這個成績中，我們須要經由過程差別面值的硬幣來湊出特定的金額，並打算起碼須要多少個硬幣。本文將利用C言語來處理這個成績，並供給具體的代碼闡明跟闡明。

成績分析

假設我們有以下硬幣面值：1分、5分、10分、20分、50分跟100分。我們的目標是湊出一定的金額，比方1000分，我們須要編寫一個順序來打算起碼須要多少個硬幣。

數據構造

為懂得決這個成績，我們可能利用一個一維數組來存儲每種面值的硬幣數量，以及一個變量來存儲目標金額。

#define MAX_COIN 6
#define TARGET_AMOUNT 1000

int coin[MAX_COIN] = {0}; // 存儲每種硬幣的數量

靜態打算數組

靜態打算的核心是創建一個數組dp，其大小等於目標金額加1。數組的每個元素代表達到該金額所需的起碼硬幣數。

int dp[TARGET_AMOUNT + 1];

初始狀況平日是全部值為正無窮大年夜，表示不道路能達到這些金額，除了金額為0時，其對應的dp[0]應為0。

for (int i = 0; i <= TARGET_AMOUNT; i++) {
    dp[i] = INT_MAX;
}
dp[0] = 0;

狀況轉移方程

順序會遍歷全部硬幣的面值，對每個硬幣，從dp[i]（i為目標金額）到dp[i - coin]（i減去硬幣面值）停止迭代。假如dp[i - coin] + 1小於dp[i]，則更新dp[i]為dp[i - coin] + 1。

for (int coinIndex = 0; coinIndex < MAX_COIN; coinIndex++) {
    for (int amount = coin[coinIndex]; amount <= TARGET_AMOUNT; amount++) {
        if (dp[amount - coin[coinIndex]] != INT_MAX) {
            dp[amount] = (dp[amount] < dp[amount - coin[coinIndex]] + 1) ? dp[amount] : dp[amount - coin[coinIndex]] + 1;
        }
    }
}

主輪回

全部過程會包含一個主輪回，用於履行上述狀況轉移，平日以硬幣的個數或目標金額為輪回前提。

int minCoins = dp[TARGET_AMOUNT];

成果輸出

在輪回結束後，dp[TARGET_AMOUNT]將保存起碼的硬幣數量，此時可能經由過程printf或其他輸出函數打印成果。

printf("起碼須要 %d 個硬幣\n", minCoins);

完全代碼

以下是完全的C言語代碼示例：

#include <stdio.h>
#include <limits.h>

#define MAX_COIN 6
#define TARGET_AMOUNT 1000

int coin[MAX_COIN] = {1, 5, 10, 20, 50, 100};

int main() {
    int dp[TARGET_AMOUNT + 1];
    for (int i = 0; i <= TARGET_AMOUNT; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;

    for (int coinIndex = 0; coinIndex < MAX_COIN; coinIndex++) {
        for (int amount = coin[coinIndex]; amount <= TARGET_AMOUNT; amount++) {
            if (dp[amount - coin[coinIndex]] != INT_MAX) {
                dp[amount] = (dp[amount] < dp[amount - coin[coinIndex]] + 1) ? dp[amount] : dp[amount - coin[coinIndex]] + 1;
            }
        }
    }

    int minCoins = dp[TARGET_AMOUNT];
    printf("起碼須要 %d 個硬幣\n", minCoins);
    return 0;
}

總結

經由過程以上步調，我們可能利用C言語處理硬幣組剖析績。靜態打算是一種有效的算法計劃方法，實用於處理這類組剖析績。在現實利用中，可能根據須要調劑硬幣面值跟目標金額，以處理差其余成績。