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

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

ID:58560340

大小:382.51 KB

页数:18页

时间:2020-09-06

C语言穷举法经典例题.ppt_第1页
C语言穷举法经典例题.ppt_第2页
C语言穷举法经典例题.ppt_第3页
C语言穷举法经典例题.ppt_第4页
C语言穷举法经典例题.ppt_第5页
资源描述:

《C语言穷举法经典例题.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、枚举法(穷举法)“笨人之法”:把所有可能的情况一一测试,筛选出符合条件的各种结果进行输出。分析:这是个不定方程——三元一次方程组问题(三个变量,两个方程)x+y+z=1005x+3y+z/3=100设公鸡为x只,母鸡为y只,小鸡为z只。百元买百鸡问题分析x+y+z=1005x+3y+z/3=100三重循环voidmain(){intx,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,

2、z=%d",x,y,z);}}结果:x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84【讨论】为什么多了几组解??百元买百鸡问题分析voidmain(){intx,y,z;for(x=0;x<=100;x++)for(y=0;y<=100;y++)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",x,y,z);}}结果:x=0,y=25,z=75x=4,y=18,z=78x=8,

3、y=11,z=81x=12,y=4,z=84【讨论】此为“最笨”之法——要进行101×101×101=1030301次(100多万次)运算。优化voidmain(){intx,y,z;for(x=0;x<=100;x++)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",x,y,z);}}【讨论】令z=100-x-y只进行101×101=10201次运算(前者的1%)取x<=20,y<=33只进行21×34=71

4、4次运算(第1种运算的6.9e-4)继续优化voidmain(){intx,y,z;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",x,y,z);}}取x<=14,y<=25只进行15×26=390次运算课堂讨论:谁做的好事?有四位同学中的一位做了好事,不留名,表扬信来了之后,校长问这四位是谁做的好事。A说:不是我。B说:是C。C说:是D。D说:C胡说。已知三个人说的是真话,一个人说的是假话。现在要根

5、据这些信息,找出做了好事的人。编程思路:如何找到该人,一定是“先假设该人是做好事者,然后到每句话中去测试看有几句是真话”。“有三句是真话就确定是该人,否则换下一人再试”。比如,先假定是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)再试B同学,让thisman=‘B’;

6、代入到四句话中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)再试C同学,让thisman=‘C’;代入到四句话中A说:thisman!=‘A’;‘C’!=‘A’真,值为1。B说:thisman==‘C’;‘C’==‘C’真,值为1。C说:thisman==‘D’;‘C’==‘D’假,值为0。D说:thisman!=‘D

7、’;‘C’!=‘D’真,值为1。显然,就是‘C’做了好事(四个关系表达式值之和为3)这时,我们可以理出头绪,要用枚举法,一个人一个人地去试,四句话中有三句为真,该人即所求。#includevoidmain(){charthisman;intsa,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(con

8、d==3)printf("做好事的人是:%c",thisman

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。