[已解决]一道题目

刘子诺 · 发表于 2022-12-19 12:42:42

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

有1元面值、5元面值、10元面值的钞票，请问有多少种找零n元的方案？

比如找10元钱一共有 4 种方法：

10张1元
1张5元，5张1元
2张5元
1张10元
输入格式
第一行，一个整数n。

输出格式
一行，一个数字。表示找零的方案数。

样例输入
10
样例输出
4
数据范围
对于100%的数据，保证1≤n≤100。

请人帮我解一下,谢谢.附上思路

最佳答案

月排行榜 / 总排行榜

tommyyu

2022-12-19 15:25:32

#include<stdio.h>
// x + 5y + 10z = n
// 5(y + 2z) + x = n
// 设 k = n % 5, l = (n - k) / 5, 即 5l + k = n
// 则 5(y + 2z) + x = 5l + k
// 5(y + 2z - l) + x = k, x = k + 5(l - y - 2z)
// 设 l - y + 2z = m, x = k + 5m, 其中 0 < m <= l
// 则可以从 0 ~ l 枚举 m, 枚举 x 的值。
// 又 l - y - 2z = m, y + 2z = l - m
// 若 l - m 为偶数，则有 ((l - m) / 2 + 1) 种解
// 若 l - m 为奇数，则有 (l - m + 1) / 2 种解
int main()
{
int sum_ = 0; // 总解法
int n;
scanf("%d", &n);
int k = n%5, l = n / 5;
for(int m = 0; m <= l; ++m) {
if((l-m) % 2 == 0) sum_ += ((l - m) / 2 + 1);
else sum_ += (l - m + 1) / 2;
}
printf("%d", sum_);
return 0;
}

复制代码

跳转到最佳答案楼层

tommyyu · 发表于 2022-12-19 15:25:32

这个最佳答案由 tommyyu 给出，感谢 tommyyu 的回答。

单击隐藏图章

#include<stdio.h>
// x + 5y + 10z = n
// 5(y + 2z) + x = n
// 设 k = n % 5, l = (n - k) / 5, 即 5l + k = n
// 则 5(y + 2z) + x = 5l + k
// 5(y + 2z - l) + x = k, x = k + 5(l - y - 2z)
// 设 l - y + 2z = m, x = k + 5m, 其中 0 < m <= l
// 则可以从 0 ~ l 枚举 m, 枚举 x 的值。
// 又 l - y - 2z = m, y + 2z = l - m
// 若 l - m 为偶数，则有 ((l - m) / 2 + 1) 种解
// 若 l - m 为奇数，则有 (l - m + 1) / 2 种解
int main()
{
int sum_ = 0; // 总解法
int n;
scanf("%d", &n);
int k = n%5, l = n / 5;
for(int m = 0; m <= l; ++m) {
if((l-m) % 2 == 0) sum_ += ((l - m) / 2 + 1);
else sum_ += (l - m + 1) / 2;
}
printf("%d", sum_);
return 0;
}

复制代码

账号		自动登录	找回密码
密码			立即注册