东方博宜OJ 1025：兑换硬币 ← 循环结构

【题目来源】https://oj.czos.cn/p/1025【题目描述】用一张一元票换 1 分、2 分和 5 分的硬币每种至少一枚 问有几种换法【输入格式】无【输出格式】输出只有一行这意味着末尾有一个回车符号包括 1 个整数。【输入样例】无【输出样例】无【数据范围】一张一元票【算法分析】● 本题是一个经典的“换硬币”问题。我们需要用一张一元票即 100 分换成 1 分、2 分和 5 分的硬币每种至少一枚。求有多少种换法。● 设 1 分硬币数量为 a2 分硬币数量为 b5 分硬币数量为 c。则有以下方程和约束a 2b 5c 100且 a 1, b 1, c 1。● 由于 5 分硬币面值最大先从它入手枚举1c 最小为 1最大为多少由 a 2b 5c 100得 5c 100 - a - 2b当 a 和 b 都取最小值 1 时5c 最大可知 5c 100 - 1 - 2 97所以 c 19。2固定 c 后剩余金额为 remain 100 - 5c且 1 分和 2 分硬币每种至少一枚。3进一步转换设 b b - 1a a - 1则 a 2b remain - 3且 a 0b 0。4对于每个 c计算方程 a 2b remain - 3 的非负整数解的数量。这可以通过枚举 b 从 0 到 (remain - 3)/2 来实现。#include bits/stdc.h using namespace std; int main() { int cnt0; for(int c1; c19; c) { int rem100-5*c; if(rem3) continue; int trem-3; for(int b0; 2*bt; b) { int at-2*b; if(a0) cnt; } } coutcntendl; //461 return 0; }但此代码对初学者来说有些难。故给出如下适合初学者学习的代码。【算法代码】#include bits/stdc.h using namespace std; int main() { int cnt0; for(int a1; a100; a) { for(int b1; b50; b) { for(int c1; c20; c) { if(a2*b5*c100) cnt; } } } coutcntendl; return 0; }【参考文献】/