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

【题目来源】
https://oj.czos.cn/p/1025

【题目描述】
用一张一元票换 1 分、2 分和 5 分的硬币，每种至少一枚， 问有几种换法？

【输入格式】
无

【输出格式】
输出只有一行（这意味着末尾有一个回车符号），包括 1 个整数。

【输入样例】
无

【输出样例】
无

【数据范围】
一张一元票

【算法分析】
● 本题是一个经典的“换硬币”问题。我们需要用一张一元票（即 100 分）换成 1 分、2 分和 5 分的硬币，每种至少一枚。求有多少种换法。
● 设 1 分硬币数量为 a，2 分硬币数量为 b，5 分硬币数量为 c。则有以下方程和约束：a + 2b + 5c = 100，且 a >= 1, b >= 1, c >= 1。
● 由于 5 分硬币面值最大，先从它入手枚举：
（1）c 最小为 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 - 1，a' = a - 1，则 a' + 2b' = remain - 3，且 a' >= 0，b' >= 0。
（4）对于每个 c，计算方程 a' + 2b' = remain - 3 的非负整数解的数量。这可以通过枚举 b' 从 0 到 (remain - 3)/2 来实现。

#include <bits/stdc++.h> using namespace std; int main() { int cnt=0; for(int c=1; c<=19; c++) { int rem=100-5*c; if(rem<3) continue; int t=rem-3; for(int b=0; 2*b<=t; b++) { int a=t-2*b; if(a>=0) cnt++; } } cout<<cnt<<endl; //461 return 0; }

但此代码，对初学者来说有些难。故给出如下适合初学者学习的代码。

【算法代码】

#include <bits/stdc++.h> using namespace std; int main() { int cnt=0; for(int a=1; a<=100; a++) { for(int b=1; b<=50; b++) { for(int c=1; c<=20; c++) { if(a+2*b+5*c==100) cnt++; } } } cout<<cnt<<endl; return 0; }

【参考文献】
/