1. 问题分析与算法设计
这个换硬币问题看似简单，但蕴含着典型的组合数学和穷举算法思想。我们需要将给定金额（8分到99分之间）拆分成5分、2分和1分硬币的组合，且每种硬币至少有一枚。
1.1 问题建模
设总金额为money（单位：分），5分硬币数量为n5，2分硬币数量为n2，1分硬币数量为n1。根据题意可以建立以下约束条件：
- 5n5 + 2n2 + n1 = money
- n5 ≥ 1, n2 ≥ 1, n1 ≥ 1
- 8 < money < 100
1.2 算法选择
这是一个典型的组合问题，适合使用穷举法（暴力搜索）解决。穷举法的基本思路是：
- 首先确定5分硬币的最大可能数量：n5_max = money / 5
- 对于每个可能的n5值（从n5_max递减到1）
- 在剩余金额(money - 5n5)中确定2分硬币的最大可能数量：n2_max = (money - 5n5) / 2
- 对于每个可能的n2值（从n2_max递减到1）
- 计算n1 = money - 5n5 - 2n2
- 检查n1是否≥1，满足则为一个有效组合
这种嵌套循环的穷举方式能确保遍历所有可能的硬币组合，时间复杂度为O(n²)，对于小规模问题完全可行。
2. C语言实现详解
2.1 基础代码实现
c复制#include <stdio.h>
int main() {
int n1, n2, n5; // 1分、2分、5分硬币数量
int money; // 总金额（分）
int count = 0; // 有效组合计数器
printf("请输入金额（8-99分）：");
scanf("%d", &money);
// 输入有效性检查
if (money <= 8 || money >= 100) {
printf("金额必须大于8分且小于1元！\n");
return 1;
}
// 外层循环：5分硬币数量（从最多开始递减）
for (n5 = money / 5; n5 >= 1; n5--) {
// 中层循环：2分硬币数量（剩余金额中的最多可能）
for (n2 = (money - n5 * 5) / 2; n2 >= 1; n2--) {
n1 = money - n5 * 5 - n2 * 2;
// 检查1分硬币是否满足至少1枚
if (n1 >= 1) {
count++;
printf("方案%d：5分×%d，2分×%d，1分×%d，总硬币数：%d\n",
count, n5, n2, n1, n5+n2+n1);
}
}
}
printf("共有%d种兑换方案\n", count);
return 0;
}
2.2 代码优化与改进
原始代码有几个可以优化的地方：
- 输入验证：增加对输入金额范围的检查
- 输出格式化：使结果展示更清晰易读
- 变量命名：使用更有意义的变量名
- 效率优化：减少不必要的计算
优化后的版本：
c复制#include <stdio.h>
int main() {
int pennies, nickels, dimes; // 1分、2分、5分硬币
int total_amount;
int solution_count = 0;
printf("硬币兑换计算器（8-99分）\n");
printf("请输入金额（分）：");
scanf("%d", &total_amount);
// 增强的输入验证
if (total_amount <= 8 || total_amount >= 100) {
printf("错误：金额必须大于8分且小于1元（100分）\n");
return 1;
}
printf("\n兑换方案：\n");
printf("--------------------------------\n");
// 优化循环范围
int max_nickels = total_amount / 5;
for (nickels = max_nickels; nickels >= 1; nickels--) {
int remaining_after_nickels = total_amount - 5 * nickels;
int max_dimes = remaining_after_nickels / 2;
for (dimes = max_dimes; dimes >= 1; dimes--) {
pennies = remaining_after_nickels - 2 * dimes;
if (pennies >= 1) {
solution_count++;
int total_coins = nickels + dimes + pennies;
printf("方案%2d：", solution_count);
printf("5分×%d + 2分×%d + 1分×%d = %d分",
nickels, dimes, pennies, total_amount);
printf("（总硬币数：%d）\n", total_coins);
}
}
}
printf("--------------------------------\n");
printf("共找到%d种兑换方案\n", solution_count);
return 0;
}
3. 算法分析与数学原理
3.1 时间复杂度分析
该算法的时间复杂度主要取决于嵌套循环的迭代次数：
- 外层循环次数：最多⌊money/5⌋ ≈ money/5
- 内层循环次数：对于每个n5，最多⌊(money-5n5)/2⌋ ≈ money/2
因此总体时间复杂度约为O(money²/10)，对于money<100的实际应用场景，性能完全足够。
3.2 组合数学视角
从数学角度看，这是一个典型的线性Diophantine方程问题：
5x + 2y + z = money
x ≥ 1, y ≥ 1, z ≥ 1
我们可以将其转化为：
5(x-1) + 2(y-1) + (z-1) = money - 8
x' ≥ 0, y' ≥ 0, z' ≥ 0
这样就变成了标准的非负整数解问题，解的数量为组合数C((money-8)+3-1, 3-1) = C(money-6, 2)
但实际解的数量会少于这个理论值，因为5和2不是互质的，存在一些约束条件。
4. Java实现版本
对于习惯Java的读者，这里提供对应的实现：
java复制import java.util.Scanner;
public class CoinExchange {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入金额（8-99分）：");
int money = scanner.nextInt();
if (money <= 8 || money >= 100) {
System.out.println("金额必须大于8分且小于1元！");
return;
}
int count = 0;
System.out.println("\n兑换方案：");
System.out.println("--------------------------------");
// 从最多5分硬币开始尝试
for (int n5 = money / 5; n5 >= 1; n5--) {
int remainingAfter5 = money - 5 * n5;
// 在剩余金额中尝试2分硬币
for (int n2 = remainingAfter5 / 2; n2 >= 1; n2--) {
int n1 = remainingAfter5 - 2 * n2;
if (n1 >= 1) {
count++;
int totalCoins = n5 + n2 + n1;
System.out.printf("方案%2d：5分×%d + 2分×%d + 1分×%d = %d分（总硬币数：%d）%n",
count, n5, n2, n1, money, totalCoins);
}
}
}
System.out.println("--------------------------------");
System.out.printf("共找到%d种兑换方案%n", count);
}
}
5. 测试用例与验证
5.1 典型测试用例
| 输入金额 | 预期方案数 | 说明 |
|---|---|---|
| 9 | 1 | 最小有效输入 |
| 13 | 2 | 题目示例 |
| 20 | 8 | 中等规模 |
| 50 | 49 | 较大规模 |
| 99 | 235 | 最大有效输入 |
5.2 边界测试
- 输入8分：应提示错误（刚好等于下限）
- 输入100分：应提示错误（刚好等于上限）
- 输入0分：应提示错误
- 输入101分：应提示错误
5.3 测试方法
可以通过以下方法验证程序正确性：
- 对于每个输出方案，检查5n5 + 2n2 + n1是否等于输入金额
- 检查每种硬币数量是否≥1
- 检查总方案数是否符合预期
- 检查是否有重复方案
6. 常见问题与解决方案
6.1 为什么从最大硬币数量开始递减？
这种"贪心"策略的优点是：
- 可以尽早找到使用大面额硬币的方案
- 减少循环次数（小面额硬币的变化更多）
- 结果输出更有条理，从大面额到小面额排列
6.2 如何避免重复计算？
本算法通过以下方式确保不重复：
- 固定5分硬币数量后，再确定2分硬币数量
- 两层循环确���了(n5,n2)组合的唯一性
- n1由前两者唯一确定
6.3 如果要求硬币总数最少怎么办？
可以在循环过程中记录硬币总数最少的方案：
c复制int min_coins = INT_MAX;
int best_n5, best_n2, best_n1;
// 在找到有效组合时：
if (n5 + n2 + n1 < min_coins) {
min_coins = n5 + n2 + n1;
best_n5 = n5;
best_n2 = n2;
best_n1 = n1;
}
// 最后输出最优方案
printf("最优方案（最少硬币数%d）：5分×%d，2分×%d，1分×%d\n",
min_coins, best_n5, best_n2, best_n1);
6.4 如果取消"每种硬币至少一枚"的限制？
算法需要相应调整：
- 外层循环从n5=0开始
- 内层循环从n2=0开始
- 只需检查n1≥0
这将显著增加可能的组合数量，特别是对于大金额。
7. 算法扩展与变种
7.1 不同面额组合
如果硬币面额变化（如1分、3分、4分），只需修改循环条件：
c复制int coin1 = 1, coin2 = 3, coin3 = 4; // 面额定义
for (n3 = money / coin3; n3 >= 0; n3--) {
for (n2 = (money - n3*coin3) / coin2; n2 >= 0; n2--) {
n1 = money - n3*coin3 - n2*coin2;
if (n1 >= 0) {
// 有效组合
}
}
}
7.2 动态规划解法
对于更大金额或更多面额，可以使用动态规划提高效率：
java复制public int coinChangeWays(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
7.3 递归回溯解法
另一种思路是使用递归回溯：
python复制def change_coins(amount, coins, current, result):
if amount == 0:
result.append(current.copy())
return
if amount < 0:
return
for i in range(len(coins)):
coin = coins[i]
if amount >= coin:
current.append(coin)
change_coins(amount - coin, coins[i:], current, result)
current.pop()
# 使用示例
result = []
change_coins(13, [5, 2, 1], [], result)
print(result)
在实际编程练习中，我经常发现初学者容易忽略的几个关键点：一是循环的边界条件设置，比如n5应该从money/5开始递减而不是递增；二是每种硬币至少一枚的约束条件，这需要在循环初始值和n1的判断条件中体现；三是输出格式的规范性，清晰的输出能大大提升调试效率。