解题思路:

有无限个解的条件是:

        最大公约数不为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 100000
 
int 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;
}


点赞(0)
 

9.9 分

6 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论