当前位置 博文首页 > m0_51723227的博客:n元钱,使用1元 2元 5元换算的方法
除去暴力求解,本题的另一种解法
忽略最大值5,全部由1和2代替;看例子;
比如
7 =
2 2 2 1
2 2 11 1
2 11 11 1
11 11 11 1 7/2+1 = 4种(没有5的情况,/代表的c语言整数的除号,7/2有三个2,一个2又可以换成只有1的情况,所以就是3 +1 = 4种;)
5 3 (有一个5的情况,看剩下的值怎么用1和2组合,同理 3/2+1 = 2种)
一共就是4+2 = 6种;
14=
2 2 2 2 2 2 2 ( 14/2有7个2,每个2又可以换2个一,按照上面的例子就是, 14/2+1 = 8种)
5 5 4 (有两个5情况,同样不管5,只管剩下的值, 4 /2 + 1 = 3种)
5 9 (有一个5情况,同样不管5,只管剩下的值, 9/2+1 = 5种 )
一共就是 8 +3 +5 = 16种
19=
2 2 2 2 2 2 2 2 2 1 ( 19/2+1 = 10)
5 5 5 4 (4 /2 +1 = 3)
5 5 9 (9 /2 +1 = 5)
5 14 (14/2+1=8)
一共就是10+3+5+8 = 26
所以循环就是按照有0到多个5的条件来计算
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
int result = n/2+1;
for(int i = 1; i <= n/5;i++)/*n/5代表最多含有多少个5,以进行循环*/
{
int num_5 = n - i*5;/*num_5代表减去多少个数字5后剩下的数字*/
result += num_5/2+1;
}
printf("%d",result);
return 0;
}
cs