从“换硬币”到“找零钱”用C语言模拟真实自动售货机找零逻辑附完整代码在编程学习的道路上很多初学者都会遇到经典的换硬币习题。这道题目看似简单却蕴含着实际商业场景中的核心逻辑——自动售货机的找零系统。本文将带你从课本习题出发逐步构建一个模拟真实场景的找零系统不仅解决基础问题还能应对更复杂的商业需求。1. 从基础习题到实际应用经典的换硬币问题要求将给定金额转换为5分、2分和1分硬币的组合每种硬币至少有一枚。这个问题的解法虽然简单但已经包含了找零系统的核心思想通过穷举所有可能的硬币组合筛选出符合总金额的方案。在实际应用中自动售货机或收银系统的找零逻辑需要考虑更多因素多种面额的纸币和硬币不同面额的可用数量限制找零方案的优化如最少硬币数用户交互界面系统资源限制特别是在嵌入式设备中让我们先回顾基础问题的解法再逐步扩展这些实际考量。2. 基础解法三重循环穷举对于固定面额5分、2分、1分的换硬币问题最直接的解法是使用三重循环穷举所有可能的组合#include stdio.h void basic_coin_change(int amount) { int count 0; // 5分硬币数量从最大可能值递减 for (int fen5 amount / 5; fen5 0; fen5--) { // 2分硬币数量从剩余金额的最大可能值递减 for (int fen2 (amount - fen5 * 5) / 2; fen2 0; fen2--) { // 计算需要的1分硬币数量 int fen1 amount - fen5 * 5 - fen2 * 2; if (fen1 0) { // 确保每种硬币至少一枚 int total fen5 fen2 fen1; printf(5分:%d, 2分:%d, 1分:%d, 总数:%d\n, fen5, fen2, fen1, total); count; } } } printf(总方案数: %d\n, count); } int main() { int amount; printf(请输入金额(分): ); scanf(%d, amount); basic_coin_change(amount); return 0; }这个基础版本已经解决了问题但存在几个可以改进的地方硬编码了硬币面额不够灵活没有考虑找零方案的最优化输出格式可以更友好没有处理边界条件和错误输入3. 进阶实现动态面额与优化找零真实的自动售货机需要处理多种面额并且通常希望用最少数量的硬币完成找零。我们可以改进算法来实现这些功能。3.1 支持动态面额配置首先我们将硬币面额改为可配置的数组#include stdio.h #include stdlib.h // 比较函数用于面额降序排序 int compare_desc(const void *a, const void *b) { return (*(int *)b - *(int *)a); } void dynamic_coin_change(int amount, int *denominations, int size) { // 先对面额进行降序排序 qsort(denominations, size, sizeof(int), compare_desc); int *counts (int *)calloc(size, sizeof(int)); if (!counts) { perror(内存分配失败); return; } printf(\n金额: %d分\n, amount); printf(可用面额: ); for (int i 0; i size; i) { printf(%d分 , denominations[i]); } printf(\n\n); // 递归函数查找所有方案 find_combinations(amount, denominations, counts, size, 0); free(counts); }3.2 递归实现组合查找为了处理可变数量的面额我们使用递归方法void print_solution(int *denominations, int *counts, int size) { printf(方案: ); int total_coins 0; for (int i 0; i size; i) { if (counts[i] 0) { printf(%d分×%d , denominations[i], counts[i]); total_coins counts[i]; } } printf((总数: %d)\n, total_coins); } void find_combinations(int remaining, int *denominations, int *counts, int size, int index) { if (remaining 0) { print_solution(denominations, counts, size); return; } if (index size) { return; } int max_coins remaining / denominations[index]; for (int i max_coins; i 0; i--) { counts[index] i; find_combinations(remaining - i * denominations[index], denominations, counts, size, index 1); counts[index] 0; } }3.3 优化找零方案在实际应用中我们通常希望找到使用硬币数量最少的方案。可以修改算法优先考虑大面额void optimal_coin_change(int amount, int *denominations, int size) { qsort(denominations, size, sizeof(int), compare_desc); int *counts (int *)calloc(size, sizeof(int)); if (!counts) { perror(内存分配失败); return; } int remaining amount; for (int i 0; i size remaining 0; i) { counts[i] remaining / denominations[i]; remaining remaining % denominations[i]; } if (remaining 0) { printf(最优找零方案(最少硬币):\n); print_solution(denominations, counts, size); } else { printf(无法用给定面额找零%d分\n, amount); } free(counts); }4. 完整系统实现模拟自动售货机现在我们将这些功能整合成一个完整的模拟系统包含以下功能支持多种面额配置商品选择和价格输入支付金额输入计算找零方案显示最优找零#include stdio.h #include stdlib.h #include stdbool.h #define MAX_DENOMINATIONS 10 #define MAX_PRODUCTS 5 typedef struct { char name[50]; int price; // 以分为单位 } Product; typedef struct { Product products[MAX_PRODUCTS]; int product_count; int denominations[MAX_DENOMINATIONS]; int denomination_count; } VendingMachine; void init_vending_machine(VendingMachine *vm) { // 初始化商品 strcpy(vm-products[0].name, 矿泉水); vm-products[0].price 150; strcpy(vm-products[1].name, 可乐); vm-products[1].price 300; strcpy(vm-products[2].name, 薯片); vm-products[2].price 450; vm-product_count 3; // 初始化面额 vm-denominations[0] 1000; // 10元 vm-denominations[1] 500; // 5元 vm-denominations[2] 100; // 1元 vm-denominations[3] 50; // 5角 vm-denominations[4] 10; // 1角 vm-denomination_count 5; } void display_products(VendingMachine *vm) { printf(\n 商品列表 \n); for (int i 0; i vm-product_count; i) { printf(%d. %s - %.2f元\n, i 1, vm-products[i].name, vm-products[i].price / 100.0); } } void display_denominations(VendingMachine *vm) { printf(\n 接受面额 \n); for (int i 0; i vm-denomination_count; i) { if (vm-denominations[i] 100) { printf(%.2f元 , vm-denominations[i] / 100.0); } else { printf(%.2f角 , vm-denominations[i] / 10.0); } } printf(\n); } void run_vending_machine(VendingMachine *vm) { while (true) { display_products(vm); display_denominations(vm); int choice; printf(\n请选择商品(1-%d)或0退出: , vm-product_count); scanf(%d, choice); if (choice 0) { break; } if (choice 1 || choice vm-product_count) { printf(无效选择!\n); continue; } Product *selected vm-products[choice - 1]; printf(已选择: %s (%.2f元)\n, selected-name, selected-price / 100.0); float payment; printf(请输入支付金额(元): ); scanf(%f, payment); int payment_cents (int)(payment * 100 0.5); // 处理浮点精度 if (payment_cents selected-price) { printf(金额不足!\n); continue; } int change payment_cents - selected-price; printf(应找零: %.2f元\n, change / 100.0); if (change 0) { optimal_coin_change(change, vm-denominations, vm-denomination_count); } } } int main() { VendingMachine vm; init_vending_machine(vm); run_vending_machine(vm); return 0; }5. 嵌入式环境下的优化考虑在资源受限的嵌入式设备如真实的自动售货机控制器中实现找零系统时需要考虑以下优化内存使用避免动态内存分配使用静态数组执行效率优化算法减少循环次数面额存储使用更紧凑的数据结构错误处理确保系统稳定运行以下是嵌入式优化的示例实现// 嵌入式优化版本 void embedded_coin_change(int amount, const int *denominations, int size) { int counts[MAX_DENOMINATIONS] {0}; int remaining amount; // 简单贪心算法找最少硬币 for (int i 0; i size remaining 0; i) { counts[i] remaining / denominations[i]; remaining remaining % denominations[i]; } if (remaining 0) { // 输出找零方案 for (int i 0; i size; i) { if (counts[i] 0) { printf(%d分×%d , denominations[i], counts[i]); } } printf(\n); } else { printf(无法精确找零\n); } }6. 测试与验证完善的系统需要全面的测试用例来验证各种边界条件void test_coin_change() { int denominations[] {100, 50, 10, 5, 1}; int size sizeof(denominations) / sizeof(denominations[0]); // 测试用例 struct { int amount; int expected_coins; } tests[] { {15, 2}, // 105 → 2硬币 {27, 4}, // 1010511 → 但最优是101052(如果2存在) {99, 10}, // 501010101051111 {0, 0}, // 无需找零 {-5, 0} // 无效输入 }; for (int i 0; i sizeof(tests) / sizeof(tests[0]); i) { printf(测试金额: %d分\n, tests[i].amount); embedded_coin_change(tests[i].amount, denominations, size); } }通过这些扩展和改进我们完成了一个从基础习题到实际应用的完整演变。这个系统不仅解决了最初的换硬币问题还能模拟真实商业场景中的找零需求甚至考虑了嵌入式环境下的特殊要求。
从“换硬币”到“找零钱”：用C语言模拟真实自动售货机找零逻辑（附完整代码）
从“换硬币”到“找零钱”用C语言模拟真实自动售货机找零逻辑附完整代码在编程学习的道路上很多初学者都会遇到经典的换硬币习题。这道题目看似简单却蕴含着实际商业场景中的核心逻辑——自动售货机的找零系统。本文将带你从课本习题出发逐步构建一个模拟真实场景的找零系统不仅解决基础问题还能应对更复杂的商业需求。1. 从基础习题到实际应用经典的换硬币问题要求将给定金额转换为5分、2分和1分硬币的组合每种硬币至少有一枚。这个问题的解法虽然简单但已经包含了找零系统的核心思想通过穷举所有可能的硬币组合筛选出符合总金额的方案。在实际应用中自动售货机或收银系统的找零逻辑需要考虑更多因素多种面额的纸币和硬币不同面额的可用数量限制找零方案的优化如最少硬币数用户交互界面系统资源限制特别是在嵌入式设备中让我们先回顾基础问题的解法再逐步扩展这些实际考量。2. 基础解法三重循环穷举对于固定面额5分、2分、1分的换硬币问题最直接的解法是使用三重循环穷举所有可能的组合#include stdio.h void basic_coin_change(int amount) { int count 0; // 5分硬币数量从最大可能值递减 for (int fen5 amount / 5; fen5 0; fen5--) { // 2分硬币数量从剩余金额的最大可能值递减 for (int fen2 (amount - fen5 * 5) / 2; fen2 0; fen2--) { // 计算需要的1分硬币数量 int fen1 amount - fen5 * 5 - fen2 * 2; if (fen1 0) { // 确保每种硬币至少一枚 int total fen5 fen2 fen1; printf(5分:%d, 2分:%d, 1分:%d, 总数:%d\n, fen5, fen2, fen1, total); count; } } } printf(总方案数: %d\n, count); } int main() { int amount; printf(请输入金额(分): ); scanf(%d, amount); basic_coin_change(amount); return 0; }这个基础版本已经解决了问题但存在几个可以改进的地方硬编码了硬币面额不够灵活没有考虑找零方案的最优化输出格式可以更友好没有处理边界条件和错误输入3. 进阶实现动态面额与优化找零真实的自动售货机需要处理多种面额并且通常希望用最少数量的硬币完成找零。我们可以改进算法来实现这些功能。3.1 支持动态面额配置首先我们将硬币面额改为可配置的数组#include stdio.h #include stdlib.h // 比较函数用于面额降序排序 int compare_desc(const void *a, const void *b) { return (*(int *)b - *(int *)a); } void dynamic_coin_change(int amount, int *denominations, int size) { // 先对面额进行降序排序 qsort(denominations, size, sizeof(int), compare_desc); int *counts (int *)calloc(size, sizeof(int)); if (!counts) { perror(内存分配失败); return; } printf(\n金额: %d分\n, amount); printf(可用面额: ); for (int i 0; i size; i) { printf(%d分 , denominations[i]); } printf(\n\n); // 递归函数查找所有方案 find_combinations(amount, denominations, counts, size, 0); free(counts); }3.2 递归实现组合查找为了处理可变数量的面额我们使用递归方法void print_solution(int *denominations, int *counts, int size) { printf(方案: ); int total_coins 0; for (int i 0; i size; i) { if (counts[i] 0) { printf(%d分×%d , denominations[i], counts[i]); total_coins counts[i]; } } printf((总数: %d)\n, total_coins); } void find_combinations(int remaining, int *denominations, int *counts, int size, int index) { if (remaining 0) { print_solution(denominations, counts, size); return; } if (index size) { return; } int max_coins remaining / denominations[index]; for (int i max_coins; i 0; i--) { counts[index] i; find_combinations(remaining - i * denominations[index], denominations, counts, size, index 1); counts[index] 0; } }3.3 优化找零方案在实际应用中我们通常希望找到使用硬币数量最少的方案。可以修改算法优先考虑大面额void optimal_coin_change(int amount, int *denominations, int size) { qsort(denominations, size, sizeof(int), compare_desc); int *counts (int *)calloc(size, sizeof(int)); if (!counts) { perror(内存分配失败); return; } int remaining amount; for (int i 0; i size remaining 0; i) { counts[i] remaining / denominations[i]; remaining remaining % denominations[i]; } if (remaining 0) { printf(最优找零方案(最少硬币):\n); print_solution(denominations, counts, size); } else { printf(无法用给定面额找零%d分\n, amount); } free(counts); }4. 完整系统实现模拟自动售货机现在我们将这些功能整合成一个完整的模拟系统包含以下功能支持多种面额配置商品选择和价格输入支付金额输入计算找零方案显示最优找零#include stdio.h #include stdlib.h #include stdbool.h #define MAX_DENOMINATIONS 10 #define MAX_PRODUCTS 5 typedef struct { char name[50]; int price; // 以分为单位 } Product; typedef struct { Product products[MAX_PRODUCTS]; int product_count; int denominations[MAX_DENOMINATIONS]; int denomination_count; } VendingMachine; void init_vending_machine(VendingMachine *vm) { // 初始化商品 strcpy(vm-products[0].name, 矿泉水); vm-products[0].price 150; strcpy(vm-products[1].name, 可乐); vm-products[1].price 300; strcpy(vm-products[2].name, 薯片); vm-products[2].price 450; vm-product_count 3; // 初始化面额 vm-denominations[0] 1000; // 10元 vm-denominations[1] 500; // 5元 vm-denominations[2] 100; // 1元 vm-denominations[3] 50; // 5角 vm-denominations[4] 10; // 1角 vm-denomination_count 5; } void display_products(VendingMachine *vm) { printf(\n 商品列表 \n); for (int i 0; i vm-product_count; i) { printf(%d. %s - %.2f元\n, i 1, vm-products[i].name, vm-products[i].price / 100.0); } } void display_denominations(VendingMachine *vm) { printf(\n 接受面额 \n); for (int i 0; i vm-denomination_count; i) { if (vm-denominations[i] 100) { printf(%.2f元 , vm-denominations[i] / 100.0); } else { printf(%.2f角 , vm-denominations[i] / 10.0); } } printf(\n); } void run_vending_machine(VendingMachine *vm) { while (true) { display_products(vm); display_denominations(vm); int choice; printf(\n请选择商品(1-%d)或0退出: , vm-product_count); scanf(%d, choice); if (choice 0) { break; } if (choice 1 || choice vm-product_count) { printf(无效选择!\n); continue; } Product *selected vm-products[choice - 1]; printf(已选择: %s (%.2f元)\n, selected-name, selected-price / 100.0); float payment; printf(请输入支付金额(元): ); scanf(%f, payment); int payment_cents (int)(payment * 100 0.5); // 处理浮点精度 if (payment_cents selected-price) { printf(金额不足!\n); continue; } int change payment_cents - selected-price; printf(应找零: %.2f元\n, change / 100.0); if (change 0) { optimal_coin_change(change, vm-denominations, vm-denomination_count); } } } int main() { VendingMachine vm; init_vending_machine(vm); run_vending_machine(vm); return 0; }5. 嵌入式环境下的优化考虑在资源受限的嵌入式设备如真实的自动售货机控制器中实现找零系统时需要考虑以下优化内存使用避免动态内存分配使用静态数组执行效率优化算法减少循环次数面额存储使用更紧凑的数据结构错误处理确保系统稳定运行以下是嵌入式优化的示例实现// 嵌入式优化版本 void embedded_coin_change(int amount, const int *denominations, int size) { int counts[MAX_DENOMINATIONS] {0}; int remaining amount; // 简单贪心算法找最少硬币 for (int i 0; i size remaining 0; i) { counts[i] remaining / denominations[i]; remaining remaining % denominations[i]; } if (remaining 0) { // 输出找零方案 for (int i 0; i size; i) { if (counts[i] 0) { printf(%d分×%d , denominations[i], counts[i]); } } printf(\n); } else { printf(无法精确找零\n); } }6. 测试与验证完善的系统需要全面的测试用例来验证各种边界条件void test_coin_change() { int denominations[] {100, 50, 10, 5, 1}; int size sizeof(denominations) / sizeof(denominations[0]); // 测试用例 struct { int amount; int expected_coins; } tests[] { {15, 2}, // 105 → 2硬币 {27, 4}, // 1010511 → 但最优是101052(如果2存在) {99, 10}, // 501010101051111 {0, 0}, // 无需找零 {-5, 0} // 无效输入 }; for (int i 0; i sizeof(tests) / sizeof(tests[0]); i) { printf(测试金额: %d分\n, tests[i].amount); embedded_coin_change(tests[i].amount, denominations, size); } }通过这些扩展和改进我们完成了一个从基础习题到实际应用的完整演变。这个系统不仅解决了最初的换硬币问题还能模拟真实商业场景中的找零需求甚至考虑了嵌入式环境下的特殊要求。
