渴望学到知识的菜鸟


私信TA

用户名:ldhskd

访问量:29794

签 名:

这小伙子人行,能处!

等  级
排  名 117
经  验 7608
参赛次数 1
文章发表 48
年  龄 18
在职情况 学生
学  校
专  业

  自我简介:

TA的其他文章

解题思路:

有无限个解的条件是:

        最大公约数不为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.......

                    之后再以此类推


    
注意事项:

参考代码:

#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.0分

7 人评分

  评论区