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

第3章 程序控制结构
枚举法(穷举法)
“笨人之法”: 把所有可能的情况一一测试,筛选出符合 条件的各种结果进行输出。
分析: 这是个不定方程——三元一次方程组问题 (三个变量,两个方程)
x+y+z=100 5x+3y+z/3=100
设公鸡为x只,母鸡为y只,小鸡为z只。

第3章 程序控制结构

百元买百鸡问题分析 x+y+z=100 5x+3y+z/3=100
三重循环

第3章 程序控制结构

void main()

{

int x,y,z;

for (x=0;x<=100;x++)

for (y=0;y<=100;y++)

for (z=0;z<=100;z++)

?

{

if (x+y+z==100 && 5*x+3*y+z/3==100 )

printf("x=%d,y=%d,z=%d\n",x,y,z);

} }

结果:x=0,y=25,z=75 x=4,y=18,z=78

x=8,y=11,z=81

x=12,y=4,z=84

【讨论】为什么多了几组解?

第3章 程序控制结构

百元买百鸡问题分析

void main()

{

结果:x=0,y=25,z=75

int x,y,z;

x=4,y=18,z=78

for (x=0;x<=100;x++)

x=8,y=11,z=81

for (y=0;y<=100;y++)

x=12,y=4,z=84

for (z=0;z<=100;z++)

{

if (z%3==0 &&x+y+z==100 && 5*x+3*y+z/3==100 )

printf("x=%d,y=%d,z=%d\n",x,y,z);

}

}

【讨论】 此为“最笨”之法——要进行101×101×101= 1030301次 (100多万次)运算。

第3章 程序控制结构

优化

void main() {
int x,y,z; for (x=0;x<=100;x++)

取x<=20,y<=33 只进行 21×34= 714 次运算(第 1种运算的6.9e-4)

for (y=0;y<=100;y++)

{

z=100-x-y;

if (z%3==0 && 5*x+3*y+z/3==100 )

printf("cocks=%d,hens=%d,chickens=%d\n",x,y,z);

}

}

【讨论】
令z=100-x-y 1%)

只进行101×101= 10201 次运算(前者的

第3章 程序控制结构

第3章 程序控制结构

继续优化

void main() {
int x,y,z;

取x<=14,y<=25 只进行 15×26= 390 次运算

for (x=0;x<=14;x++)

for (y=0;y<=25;y++)

if (7*x+4*y==100 )

{

z=100-x-y;

printf("cocks=%d,hens=%d,chickens=%d\n",x,y,z);

}

}

第3章 程序控制结构
课堂讨论:谁做的好事?
有四位同学中的一位做了好事,不留名,表扬信来了 之后,校长问这四位是谁做的好事。
A说:不是我。 B说:是C。 C说:是D。 D说:C胡说。 已知三个人说的是真话,一个人说的是假话。现在要根据 这些信息,找出做了好事的人。

第3章 程序控制结构

编程思路:

如何找到该人,一定是“先假设该人是做好事者,然

后到每句话中去测试看有几句是真话”。“有三句是真话就 确定是该人,否则换下一人再试”。

比如,先假定是A同学,让 thisman='A';

代入到四句话中

A说:thisman!=‘A’; ‘A’!=‘A’

假,值为0。

B说:thisman==‘C’; ‘A’==‘C’

假,值为0。

C说:thisman==‘D’; ‘A’==‘D’

假,值为0。

D说:thisman!=‘D’; ‘A’!=‘D’

真,值为1。

显然,不是'A'做的好事(四个关系表达式值的和为1)

第3章 程序控制结构

再试B同学,让thisman=‘B’;

代入到四句话中

A说:thisman!=‘A’; ‘B’!=‘A’

真,值为1。

B说:thisman==‘C’; ‘B’==‘C’

假,值为0。

C说:thisman==‘D’; ‘B’==‘D’

假,值为0。

D说:thisman!=‘D’; ‘B’!=‘D’

真,值为1。

显然,不是'B'所为(四个关系表达式值的和为2)

第3章 程序控制结构

再试C同学,让thisman=‘C’;

代入到四句话中

A说:thisman!=‘A’; ‘C’!=‘A’

真,值为1。

B说:thisman==‘C’; ‘C’==‘C’

真,值为1。

C说:thisman==‘D’; ‘C’==‘D’

假,值为0。

D说:thisman!=‘D’; ‘C’!=‘D’

真,值为1。

显然,就是‘C’做了好事(四个关系表达式值之和为3)

这时,我们可以理出头绪,要用枚举法,一个人一个人地去 试,四句话中有三句为真,该人即所求。

第3章 程序控制结构

#include<stdio.h>

void main( )

{

char thisman;

int sa,sb,sc,sd,cond;

for (thisman='A'; thisman<='D'; thisman++)

{

sa=(thisman != 'A');

sb=(thisman == 'C');

sc=(thisman == 'D');

sd=(thisman != 'D');

cond=sa+sb+sc+sd;

if (cond==3) printf("做好事的人是:%c\n", thisman);

}

}

第3章 程序控制结构
利用穷举法求解趣味智力题
(韩信点兵) 韩信有一队兵,他想知道有多少人,便让士兵排队报 数。按从1至5报数,最末一个士兵报的数为1;按从1 至6报数,最末一个士兵报的数为5;按从1至7报数, 最末一个士兵报的数为4;最后再按从1至11报数,最 末一个士兵报的数为10。你知道韩信至少有多少兵吗?
设兵数为x,则x应满足: x%5 == 1 && x%6 == 5 && x%7 == 4 && x%11 == 10 穷举法对x从1开始试验


相关文档

C语言算法100个经典例题
C语言经典例题100
C语言穷举-习题参考
C语言经典例题100例
C语言经典例题
C语言经典例子
C语言经典习题100例
c语言经典100例题
经典C语言程序设计实例讲解例子
jingxinwu.net
90858.net
xaairways.com
tuchengsm.com
gaizaoahe.com
eonnetwork.net
ceqiong.net
bestwu.net
学霸百科
新词新语
电脑版 | 学霸百科