题目描述
假设一堆由1分、2分、5分组成的n个硬币总面值为m分，求一共有多少种可能的组合方式（某种面值的硬币可以数量可以为0）。
输入格式
输入数据第一行有一个正整数T，表示有T组测试数据。接下来的T行，每行有两个数n，m，n和m的含义同上。
输出
对于每组测试数据，请输出可能的组合方式数，每组输出占一行。
样例输入
2
3 5
4 8
样例输出
1
2
本题的思路类似于鸡兔同笼问题，所以不难想到使用几个for循环对可能值进行穷举，下面是我写的一个算法，在穷举上略有优化。
1
#include <stdio.h>
2
int
main(
void
)
3
{
4
int
n,m;
5
int
time;
6
7
scanf(
"
%d
"
,&
time);
8
while
(time--
)
9
{
10
11
int
count=
0
;
12
scanf(
"
%d %d
"
,&n,&
m);
13
int
i,j,k,total;
14
15
for
(i=
0
;i<=(m/
5
);i++
)
16
{
17
18
for
(j=
0
;j<=(m/
2
);j++
)
19
{
20
k=n-j-
i;
21
total=k*
1
+j*
2
+i*
5
;
22
if
(total==
m)
23
count++
;
24
}
25
26
}
27
printf(
"
%d\n
"
,count);
28
}
29
return
0
;
30
}
提交后仍有错误，暂未发现在何处。下面是官方的算法，较之又有一些优化。
1
#include<stdio.h>
2
3
int
main()
4
{
5
int
t,n,m,c1,c2,c5,k;
6
scanf(
"
%d
"
,&
t);
7
while
(t--
)
8
{
9
scanf(
"
%d%d
"
,&n,&
m);
10
k=
0
;
11
for
(c5=
0
;
5
*c5<=m;c5++
)
12
for
(c2=
0
;
2
*c2+
5
*c5<=m;c2++
)
13
{
14
c1=m-
5
*c5-
2
*
c2;
15
if
(c1+c2+c5==
n)
16
k++
;
17
}
18
printf(
"
%d\n
"
,k);
19
}
20
return
0
;
21
}
另外值得一提的是，本题与 1023——坑爹的黑店 在算法上有异曲同工之妙。
另：之后又根据官方修改，仍是不过。奇怪。
1
#include <stdio.h>
2
int
main(
void
)
3
{
4
int
n,m;
5
int
time;
6
7
scanf(
"
%d
"
,&
time);
8
while
(time--
)
9
{
10
11
int
count=
0
;
12
scanf(
"
%d %d
"
,&n,&
m);
13
int
i,j,k,total;
14
15
for
(i=
0
;
5
*i<=m;i++
)
16
{
17
18
for
(j=
0
;
2
*j<=m;j++
)
19
{
20
k=n-j-
i;
21
total=k*
1
+j*
2
+i*
5
;
22
if
(total==
m)
23
count++
;
24
}
25
26
}
27
printf(
"
%d\n
"
,count);
28
}
29
return
0
;
30
}
最后终于发现问题，关于k=n-i-j;因为对于i,j的初始没有限制，所以k可能是负值的情况没有排除。
下面代码AC
1
#include <stdio.h>
2
int
main(
void
)
3
{
4
int
n,m;
5
int
time;
6
7
scanf(
"
%d
"
,&
time);
8
while
(time--
)
9
{
10
11
int
count=
0
;
12
scanf(
"
%d %d
"
,&n,&
m);
13
int
i,j,k,total;
14
15
for
(i=
0
;
5
*i<=m;i++
)
16
{
17
18
for
(j=
0
;
2
*j<=m;j++
)
19
{
20
k=n-j-
i;
21
total=k*
1
+j*
2
+i*
5
;
22
if
(total==m&&k>=
0
)
23
{
24
25
count++
;
26
}
27
28
}
29
30
}
31
printf(
"
%d\n
"
,count);
32
}
33
return
0
;
34
}
