題目描述
假設一堆由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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
