例题4-12 贪心法-找零钱 C语言

例题4-12 贪心法 - 找零钱的C语言实现通常是一个经典的计算机科学问题，它涉及到动态规划或者贪心策略。假设你需要找给用户一定金额的零钱，但是只有有限几种面额可供选择（比如1元、5元、10元等）。贪心算法在这种情况下会尽可能地选择最大面额的钞票，直到达到目标金额。

以下是简单的C语言代码示例：

#include <stdio.h>

// 面额数组
int coins[] = {1, 5, 10}; // 例如1元、5元、10元
int num_coins = sizeof(coins) / sizeof(coins[0]); // 面额种类

void change(int amount) {
    int i;
    for (i = num_coins - 1; i >= 0 && amount > 0; i--) { // 从大到小遍历面额
        while (amount >= coins[i]) { // 只要能减去就减
            amount -= coins[i]; // 使用当前面额
        }
    }
    printf("最少需要找回 %d 张\n", i + 1); // 输出所需张数，+1是因为数组下标从0开始
}

int main() {
    int amount = 37; // 假设需要找零37元
    change(amount);
    return 0;
}

在这个例子中，程序会输出`最少需要找回6张`，因为可以找一张10元、两张5元和一张1元的零钱组合。