2025年华南理工大学计算机考研复试机试真题（附 AC 代码 + 解题思路）

2025年华南理工大学计算机考研复试机试真题

2025年华南理工大学计算机考研复试上机真题

历年华南理工大学计算机考研复试上机真题

历年华南理工大学计算机考研复试机试真题

更多学校题目开源地址：https://gitcode.com/verticallimit1/noobdream

N 诺 DreamJudge 题库：输入 “学校名称” 即可筛选该校历年机试真题，题目均在考纲范围内，按难度自动排序。还可搭配《计算机考研机试攻略》刷题，书中题目可通过题号直接在题库中查找。

凑零钱

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了 6 种钱币面值为 2、5、10、20、50、100，用来凑 15 元，可以用 5 个 2 元、1个 5 元，或者 3 个 5 元，或者 1 个 5 元、1个 10 元，等等。显然，最少需要 2 个钱币才能凑成 15 元。你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。

输入输出格式

输入描述:

第一行是待凑的钱数值 M（1 <= M<= 2000，整数），接着的一行中，第一个整数 K（1 <= K <= 10）表示币种个数，随后是 K个互不相同的钱币面值 Ki(1 <= Ki <= 1000)。输入 M=0 时结束。

输出描述:

每个测试用例输出一行，即凑成钱数值 M 最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。

输入输出样例

输入样例#:

15 6 2 5 10 20 50 100

输出样例#:

2

代码一

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int INF=0x3f3f3f3f;
4. int m, k;
5. void work(){
6. while(cin>>m&&m!=0){
7. cin>>k;
8. int a[15];
9. for(int i=1;i<=k;i++) cin>>a[i];
10. int f[2500];
11. memset(f, 0x3f, sizeof f);
12. f[0]=0;
13. for(int i=1;i<=k;i++){
14. int x=a[i];
15. for(int j=0;j<=m;j++){
16. for(int y=0;y<=j;y+=x){
17. f[j]=min(f[j], f[j-y]+y/x);
18. }
19. }
20. }
21. if(f[m]==INF) cout<<"Impossible"<<endl;
22. else cout<<f[m]<<endl;
23. }
24. }
25. int main(){
26. work();
27. return 0;
28. }

代码二

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4. #include <time.h>
5. #include <math.h>
6. #include <ctype.h>
7. int main()
8. {
9. int m;
10. while(scanf("%d",&m)!=EOF)
11. {
12. int n;
13. scanf("%d",&n);
14. int value[n];
15. for(int i=0; i<n; i++)
16. {
17. scanf("%d",&value[i]);
18. }
19. int dp[m];
20. dp[0]=0;
21. for(int i=1; i<=m; i++)
22. {
23. dp[i]=999999;
24. }
25. for(int i=0; i<n; i++)
26. {
27. for(int j=value[i]; j<=m; j++)
28. {
29. if(dp[j-value[i]]!=999999)
30. {
31. dp[j]=dp[j]<(dp[j-value[i]]+1)?dp[j]:(dp[j-value[i]]+1);
32. }
33. }
34. }
35. if(dp[m]==999999)
36. {
37. printf("Impossible\n");
38. }
39. else
40. {
41. printf("%d\n",dp[m]);
42. }
43. }
44. return 0;
45. }

代码三

1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. using namespace std;
5. int main() {
6. int m;
7. while (cin >> m && m != 0) { // 循环读取每个测试用例，直到m为0
8. int k;
9. cin >> k; // 读取币种个数
10. vector<int> coin(k);
11. for (int i = 0; i < k; ++i) {
12. cin >> coin[i];
13. }
14. vector<int> dp(m + 1, 1001); // 初始化为较大的数
15. dp[0] = 0; // 初始化边界条件
16. for (int i = 0; i < k; ++i) {
17. for (int j = coin[i]; j <= m; ++j) {
18. dp[j] = min(dp[j], dp[j - coin[i]] + 1);
19. }
20. }
21. if (dp[m] != 1001) {
22. cout << dp[m] << endl;
23. } else {
24. cout << "Impossible" << endl;
25. }
26. }
27. return 0;
28. }