C语言穷举法经典例题_图文.ppt

scanf(“%d,%d”,&n,&k);
for(i=1;i<=n;i++)
scanf(“%d”,&a[i]);
for(i=0;i>=n;i++) b[i]=1;
cmin=1000000;
while(b[0]==1)
{
for(i=1;i<=k;i++)
____s_[i_]_=_0_; ________;
4
例2．除法运算（NOIP1995初中组复赛第一题） 设有下列的除法算式：
请根据上述算式中的信息求出被除数和除数。 分析：设除数为x，被除数为y，由算式信息可知：10<=x<=99， 1000<=y<=9999，且8*x<=99，9*x>=100。因此，我们可选择枚举除 数，而被除数则可按公式y=809*x+1计算得出。
8
int link[6,2]={{1,2},{1,4},{2,5},{4,7},{5,8},{7,8}};
int b[9];
main()
{
b[1]=2;b[3]=8;b[6]=1;b[8]=7;
try;
b[1]=7;b[2]=1;b[6]=8;b[8]=2;
try;
}
void print;
{
printf(“%4d\n”,b[1]);
printf(“%d”,d[i]);
}
13
穷举法的基本思想: 穷举也叫枚举，它的基本思想是先依据题目的部分条件来确定答案
的大致范围（可能解），然后在此范围内用其余的条件对所有可能解进 行一一验证，删去那些不符合条件的解，剩下符合条件的解就是整个问 题的解

四、穷举法 实例二：有形如：ax +bx +cx+d=0 这样的一个一 应用 元三次方程。给出该方程中各项的系数 (a，b，c，
3 2
d 均为实数)，并约定该方程存在三个不同实根 (根的范围在-100至100之间)，且根与根之差的绝 对值>=1。要求由小到大依次在同一行输出这三 个实根(根与根之间留有空格)，并精确到小数点 后2位。 提示：记方程f(x)=0，若存在2个数x1和x2，且 x1<x2，f(x1)*(x2)<0，则在(x1，x2)之间一定有 一个 根。 样例 输入：1 -5 -4 20 输出：-2.00 2.00 5.00
穷举法
穷举法
一、引 入 实例一：输入绳子的长度 n，将该绳子分成三段，
每段的长度为正整数，输出由该三段绳子组成的 三角形个数。 算法分析：没有公式直接求出三角形的个数,所以程 序只能采用穷举法,一一验证范围内的数是否能构成 三角形,若是则累计。
穷举法
一、引 入 s:=0;
for a:=1 to n-2 do for b:=a to n-2 do for c:=b to n-2 do if (a+b>c) and (b+c>a) and (c+a>b) and (a+b+c=n) then s:=s+1;
四、穷举法 本题是2001 年全国信息学奥林匹克竞赛高中组复 应用 赛第一题，如果考虑解方程的话则比较麻烦。我
们可以换个角度思考问题，在-100到100之间找 三个满足方程的实数，由于穷举时必须用整型变 量，题目又要求保留两位小数，我们只需将循环 变量扩大100倍即可顺利穷举，最后只要将所求 结果再缩小100倍即可。

break;if ( t == x ) /*是否通过循环条件出口*/printf("%d is prime\n", x );elseprintf("%d isn’t prime\n", x ); /* break出口*/}对于上面的程序，需要说明下面两点。

（1）在程序中，利用%求余运算来判断整除关系。

（2）在程序中，一旦发现x整除以某个整数，就说明x一定不是素数，因此，利用break语句立即结束循环。

这样一来，结束循环结构就有两种可能，一种是正常结束，表明x是素数；另一种是提前结束，表明x不是素数。

这两种状态可以通过t是否等于x来辨别。

下面是两组测试数据的运行结果：假设用户输入：28程序将显示：28 isn’t prime假设用户输入：37程序将显示：37 is prime3.2.3 穷举法应用实例2：百钱买百鸡【例3-3】百钱买百鸡。

“百钱买百鸡”是我国古代数学家张丘建提出的一个著名的数学问题。

假设某人有钱百枚，希望买一百只鸡；不同的鸡价格不同，公鸡5枚钱一只，母鸡3枚钱一只，而小鸡3只1枚钱。

试问：如果用百枚钱买百只鸡，可以包含几只公鸡、几只母鸡和几只小鸡。

〖问题分析〗从题目要求可知：公鸡、母鸡和小鸡的数量是有限的，都不会超过100。

通过对不同数量的公鸡、母鸡和小鸡进行组合，可以计算出购买这些鸡所用的花费，但这个题目要求找出那些花费正好为100枚钱且鸡的总数也为100只的情况。

因此，可以采用穷举法，将不同的公鸡、母鸡和小鸡的数量枚举一遍，找出那些符合题目要求的解。

〖算法描述〗为了穷举不同数量的公鸡、母鸡和小鸡，需要设置3个变量x、y和z，分别保存公鸡、母鸡和小鸡的数量。

解决这个问题的基本步骤如下。

（1）公鸡数量置0，并保存在x中，重复执行（2）。

（2）母鸡数量置0，并保存在y中，重复执行（3）。

（3）小鸡数量置0，并保存在z中，重复执行（4）。

（4）如果x+y+z==100并且花费一百枚，则打印输出x，y，z。

穷举法1.密码箱问题#include<stdio.h>main(){int i,key;printf("请设定旅行箱的密码(000-999)："); scanf("%d",&key);printf("\n你的旅行箱密码是：");for(i=0;i<=999;i++)if(i==key)if(i<10)printf("%d\n",i);else if(i<100)printf("%d\n",i);else printf("%d\n",i);}2.百钱买百鸡问题#include<stdio.h>main(){int i , j , k;/*准备输出格式*/printf("\t公鸡\t母鸡\t小鸡\n");for(i=0;i<=20;i++)for(j=0;j<=33;j++){k=100-i-j;if(k%3==0 && i*5+j*3+k/3==100) printf("\t%d\t%d\t%d\n",i ,j ,k); }}例 2 ：36 块砖，36 人搬。

男搬 4 ，女搬 3 ，两个小儿抬一砖。

要求一次全搬完。

问需男、女、小儿各若干（必须都有）？请同学们先分析第一步：问题所涉及的情况；analysis：都男的搬，需9人；都女的搬，需12人，都小孩搬，需72人；小孩书需要是2的整数倍；解：#include<stdio.h>main(){int i,j,k;for(i=0;i<=9;i++)for(j=0;j<=12;j++){k=36-i-j;//消去参数需放在最后一个for循环里面if(k%2==0&&i*4+j*3+k*0.5==36)printf("%d\t%d\t%d\n",i,j,k);}作业：换零钞问题：一张100元，换成20，10，5，1面值的零钞，每种至少一张，共有哪些换法，总计多少种换法？都换20：5张；----i都换10:10张；----j都换5:20张；----k都换1:100张----tt=100-i-j-k;解：#include<stdio.h>main()int i,j,k,t;for(i=1;i<=5;i++)for(j=1;j<=10;j++)for(k=1;k<=20;k++){t=100-i*20-j*10-k*5;if(i*20+j*10+k*5+t==100&&t>0)printf("%d\t%d\t%d\t%d\n",i,j,k,t);}}2.从1到100的自然数中，每次取出两个数，要使它们的和大于100，共有哪些取法，总计多少种取法？#include<stdio.h>main(){static int count=0;int i,j;for(i=1;i<=100;i++)for(j=1;j<=100;j++){if((i+j)>100&&j!=i){count++;printf("i=%d\tj=%d\n",i,j);}}printf("循环次数为%d\n",count);}。