枚举

- 日理万妓 2021-12-16 15:34 354阅读 0赞

枚举（穷举，暴力求解）

一.基本思想

对问题变量可能解集合的每一个元素，根据问题给出的检验条件判定哪些是成立的，使条件成立的元素即是问题的解。

二.例题

1.假币问题：

问题描述：

赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。

输入数据：

输入第一行有一个数字n，表示有n组测试用例。  
　　对于每组测试用例：  
　　输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用\`\`up'', \`\`down'', 或 \`\`even''表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。

输出要求：

输出输出哪一个标号的银币是假币，并说明它比真币轻还是重(heavy or light)。

样例输入：

1
    ABCD EFGH even 
    ABCI EFJK up 
    ABIJ EFGH even

样例输出：

K is the counterfeit coin and it is light.

#include <stdio.h>
    #include <stdlib.h>
    char left[3][7],right[3][7],result[3][7];
    int state[12];
    
    //判断在假设条件下是否满足条件
    int isRight()
    {
        int leftSum,rightSum,i,j;
        for(i=0;i<3;i++)
        {
            leftSum=0,rightSum=0;
            for(j=0;j<6&&left[i][j]!=0;j++)
            {
                leftSum += state[left[i][j]-'A'];
                rightSum += state[right[i][j]-'A'];
            }
            if(leftSum>rightSum && result[i][0]!='u')  //左边更重但不为up
                return 0;
            if(leftSum==rightSum && result[i][0]!='e')  //两边相等但不为equal
                return 0;
            if(leftSum<rightSum && result[i][0]!='d')  //右边更重但不为down
                return 0;
        }
        return 5;
    }
    
    int main()
    {
        int n,x,y,k;
        scanf("%d",&n);
        for(x=0;x<n;x++)
        {
            for(y=0;y<3;y++)
            {
                scanf("%s %s %s",left[y],right[y],result[y]);
            }
            memset(state,0,sizeof(state));
            for(k=0;k<12;k++)
            {
                state[k] = 1;  //假设第i枚硬币是较重硬币
                if(isRight())
                    break;
                state[k] = -1;  //假设第i枚硬币是较轻硬币
                if(isRight())
                    break;
                state[k] = 0;  //假设第i枚硬币是真币
            }
            if(state[k] > 0)
                printf("%c is the counterfeit coin and it is heavy.\n",k+'A');
            if(state[k] < 0)
                printf("%c is the counterfeit coin and it is light.\n",k+'A');
        }
        return 0;
    }

2.生理周期

问题描述：

人生来就有三个生理周期，分别为体力周期、感情周期和智力周期，它们的周期长度分别为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，在智力周期的高峰，人会思维敏捷，注意力容易高度集中。因为三个周期的长度不同，所以通常三个周期的高峰不会落在同一天。对于每个人，想知道何时三个高峰落在同一天。对于每个周期，会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。给定一个从当年第一天开始的天数，你的任务是输出从给定时间开始（不包括给定时间），下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同一天的时间是12，则输出2（注意这里不是3）。

输入要求：

输入包含多组数据，每一组数据由四个整数组成，数据以-1 -1 -1 -1 结束。  
       对于四个整数p, e, i和d，p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d是给定的时间，可能小于p, e或i。所有给定时间是非负的并且小于或等于365，所求的时间小于或等于21252。

输出要求：

从给定时间起，下一次三个高峰同一天的时间（距离给定时间的天数）。

样例输入：

0 0 0 0
    0 0 0 100
    5 20 34 325
    4 5 6 7
    283 102 23 320
    203 301 203 40
    -1 -1 -1 -1

样例输出：

Case 1: the next triple peak occurs in 21252 days.
    Case 2: the next triple peak occurs in 21152 days.
    Case 3: the next triple peak occurs in 19575 days.
    Case 4: the next triple peak occurs in 16994 days.
    Case 5: the next triple peak occurs in 8910 days.
    Case 6: the next triple peak occurs in 10789 days.

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        int d,p,e,i,p1,e1,i1,j=0,k,m;
        scanf("%d %d %d %d",&p,&e,&i,&d);
        while(d!=-1 && p!=-1 && e!=-1 && i!=-1)
        {
            j++;
            p1 = p%23;
            e1 = e%28;
            i1 = i%33;
            for(m=i+1;;m++) //找到第一个智力高峰
            {
                if(m%33 == i1)
                {
                    break;
                }
            }
            for(k=m;k<=21252;k+=33) //在智力高峰上找到第一个情感高峰
            {
                if(k%28==e1)
                {
                    break;
                }
            }
            for(m=k;m<=21252;m+=33*28) //在前两者的公共高峰上找到第一个体力高峰
            {
                if(m%23==p1)
                {
                    printf("Case %d:the next triple peak occers in %d days\n",j,m-d);
                    break;
                }
            }
            scanf("%d %d %d %d",&p,&e,&i,&d);
        }
    
        return 0;
    }

3.完美立方

描述：

形如a3= b3 + c3 + d3的等式被称为完美立方等式。例如123= 63 + 83 + 103 。编写一个程序，对任给的正整数N (N≤100)，寻找所有的四元组(a, b, c, d)，使得a3 = b3 + c3 + d3，其中a,b,c,d 大于 1, 小于等于N，且b<=c<=d。

输入数据：

一个正整数N (N≤100)。

输出格式为：

Cube = a, Triple = (b,c,d)

请按照a的值，从小到大依次输出，当两个完美立方等式中a的值相同，则b值小的优先输出，仍相同则c值小的优先输出，再相同则d值小的先输出。

样例输入

样例输出

Cube = 6, Triple = (3,4,5)
    Cube = 12, Triple = (6,8,10)
    Cube = 18, Triple = (2,12,16)
    Cube = 18, Triple = (9,12,15)
    Cube = 19, Triple = (3,10,18)
    Cube = 20, Triple = (7,14,17)
    Cube = 24, Triple = (12,16,20)

#include <stdio.h>
    #include <stdlib.h>
    int cube[100];
    
    int main()
    {
        int n,i,a,b,c,d;
        scanf("%d",&n);
        for(i=2;i<=n;i++)
        {
            cube[i] = i*i*i;
        }
        for(a=6;a<=n;a++) //通过计算，6以前没有满足条件的b，c，d
        {
            for(b=2;b<a;b++)  //通过确定b，c，d的初始值，来使它们非降序排列，并且小的先输出。
            {
                for(c=b;c<a;c++)
                {
                    for(d=c;d<a;d++)
                    {
                        if(cube[a] == cube[b]+cube[c]+cube[d])
                        {
                            printf("Cube = %d,Triple = (%d,%d,%d)\n",a,b,c,d);
                        }
                    }
                }
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/ljlzl/p/10865351.html