解题思路:
有无限个解的条件是：
最大公约数不为1
如果不是1的话，说明是和某个数成倍数关系，所以可以得出组合的只能是那个数的倍数
有限个解的判断条件：
穷举法：
先把第一个蒸笼能放的位置列举出来，也就是第一个蒸笼能放包子的各种倍数
例如：2的话就是 2,4,6,8,10,12,14............
之后，再把下一个蒸笼能放的数列举出来，并且再和第一种的组合起来，
例如：第二个数是3的话，和3成倍数的：3,6,9,12,15,18......
再和第一种组合起来：2+3,4+3,6+3,8+3,10+3.........
5,7,9,11,13......
再和2,4,6,8,10,12，14.......组合起来就是：2,4,5,6,7,8,9,10,11,12,13,14.......
之后再以此类推
注意事项:
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <stdio.h>#define N 100000int b[N]; //定义一个全局变量int gcd(int num1, int num2) //求最大公约数{ return num2 == 0 ? num1 : gcd(num2, num1 % num2);}int fun(int a[] ,int n) //判断解是不是有无穷个{ int t = a[0]; for (int i = 1; i < n; i++) t = gcd(t, a[i]); if (t > 1) return 1; return 0; //若返回1，则说明有无穷个解}void judge(int a[], int n) //判断有多少个解{ b[0] = 1; for (int i = 1; i <= n; i++) for (int j = a[i - 1]; j < N; j++) if (b[j - a[i - 1]] == 1) b[j] = 1;//j 比 j - a[i-1] 多了个 a[ i -1 ]}int result(int b[]) //如果是有穷解的话，判断有多少个结果{ int count = 0; for (int i = 0; i < N; i++) if (b[i] != 1) count++; return count;}int main(){ int n, i, a[101]; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); if (fun(a, n)) printf("INF\n"); else { judge(a, n); printf("%d", result(b)); } return 0;} |
9.9 分
6 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复