tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 其它课程 >>

穷举法初


穷举法初涉
—————————————— 主要内容: 1、 穷举法的涵义 2、 穷举法举例 3、 书本习题 4、 穷举法应用 ——————————————

1、穷举法:把所有可能的情况一一测试,筛选出符合条件要求的结果,并输出。 2、穷举法举例
例 1: 要求输出 1 到 100 之间能给 7 整除的所有整数。 如何来求呢,我们先把程序写

出来。

#include "stdio.h" main() { int i,n=0;/*i 代表 1 到 100 之间的数,n 用来计算能给 7 整除的个数*/ for(i=1;i<=100;i++) {if(i%7==0){printf("%4d",i);n++;} if(n%8==0)printf("\n");/*每一行输出 8 个数*/ } }
以上就是一个穷举法应用的例子。 穷举法的要领: (1)确定范围; (2)验证条件 如上题的范围是 1~100 之间的整数;验证的条件是 i%7==0 例 2: 百元买百鸡:用一百元钱买一百只鸡。已知公鸡 5 元/只,母鸡 3 元/只,小鸡 1 元/3 只。 分析: 这是个不定方程——三元一次方程组问题(三个变量,两个方程)

x+y+z=100 5x+3y+z/3=100
设公鸡为 x 只,母鸡为 y 只,小鸡为 z 只。

main() 结果:x=0,y=25,z=75 { x=4,y=18,z=78 int x,y,z; x=8,y=11,z=81 for (x=0;x<=100;x++) x=12,y=4,z=84 for (y=0;y<=100;y++) for (z=0;z<=100;z++) { if (x+y+z==100 && 5*x+3*y+z/3.0==100 ) printf("cocks=%d,hens=%d,chickens=%d\n",x,y,z); } }

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

main() { 取x<=19,y<=33 int x,y,z; for (x=0;x<=100;x++) 只进行20×34= 680 次运算 for (y=0;y<=100;y++) { (第1种运算的6.7%) z=100-x-y; if (5*x+3*y+z/3.0==100 ) printf(“cocks=%d,hens=%d,chickens=%d\n",x,y,z); } }

【讨论】 令 z=100-x-y

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

3、书本上的习题:
两个乒乓球队进行比赛, 各出三人。甲队为 A、B、C 三人,乙队为 X、Y、Z 三 人。已抽签决定比赛名单。有人向队员打听比赛的名单,A 说他不和 X 比,C 说他不和 X、Z 比。请编程序找出三赛手的名单。 分析: ① X 既不与 A 比,又不与 C 比,必然与 B 比; ② C 既不与 X 比,又不与 Z 比,必然与 Y 比; ③ A 只能与 Z 比. 以上为逻辑推理得到结论,而用计算机处理此问题,必须对所有组合一一检验, 看是否符合条件。 #include <stdio.h> int main() { char _A, _B, _C; /* 分别表示 A,B,C 的对手 */ for(_A = 'X'; _A <= 'Z'; _A++) for(_B = 'X'; _B <= 'Z'; _B++) for(_C = 'X'; _C <= 'Z'; _C++) if(_A != _B && _A != _C && _B != _C && _A != 'X' && _C != 'X' && _C != 'Z') printf("A--%c\tB--%c\tC--%c\n", _A, _B, _C);

return 0; } 运行结果: ============================== A--Z B--X C--Y ==============================
★ 这里为了在运行时能直接打印出字符'X'、'Y'、'Z', 用了字符变量_A,_B,_C 。另外为了

减少循环次数,可由外层到内层去除不符合的组合。书中例子如下: #include <stdio.h> int { char i, j, k; /* 分别表示 A,B,C 的对手 */ for(i = 'X'; i <= 'Z'; i++) for(j = 'X'; j <= 'Z'; j++) if (i != j) for(k = 'X'; k <= 'Z'; k++) if (i != k && j != k) if(i != 'X' && k != 'X' && k != 'Z') printf("A--%c\tB--%c\tC--%c\n", i, j, k); return 0; } 运行结果同上。 ★ 考查两个程序循环次数的差异,做如下验证: #include <stdio.h> int { char _A, _B, _C, count = 0; for(_A = 'X'; _A <= 'Z'; _A++) for(_B = 'X'; _B <= 'Z'; _B++) for(_C = 'X'; _C <= 'Z'; _C++) count++; printf("count=%d\n", count); return 0; } 运行结果: ====================== count=27 ====================== main() main()

#include <stdio.h> int { char i, j, k, count = 0; for(i = 'X'; i <= 'Z'; i++) for(j = 'X'; j <= 'Z'; j++) if (i != j) for(k = 'X'; k <= 'Z'; k++) if (i != k && j != k) count++; printf("count=%d\n", count); return 0; } 运行结果: ====================== count=6 ====================== ★ 可见后者循环次数比前者少的多。 main()

4、穷举法应用


推荐相关:

穷举法

穷举法_学科竞赛_小学教育_教育专区。循环结构的嵌套应用举例 —穷举法(VB)教材: 《Visual Basic 程序设计》高教版 内容:用穷举法解决问题 教师:株洲市中等职业学...


穷举法详细

第三讲 穷举法一、穷举法的基本概念 穷举方法是基于计算机特点而进行解题的思维...穷举法习题课 7页 免费 穷举法初 暂无评价 5页 免费 “穷举法与问题解决...


穷举法

穷举法_学科竞赛_小学教育_教育专区。计数法导学案 课题:穷举法 审核: 课型:新授 使用时间: 执笔: 一、学习目标 1、 字典排列法 2、 累加法 二、重点难点 ...


用穷举法解决问题

穷举法解决问题_其它课程_高中教育_教育专区。用穷举法解决问题 一、 教材分析: 《用穷举法解决问题》是高中信息技术选修模块《算法与程序设计》第三章《程序的...


1穷举法

暂无评价 2页 免费 基础算法(一)穷举法 1页 1下载券喜欢此文档的还喜欢 ...1​穷​举​法 暂无评价|0人阅读|0次下载|举报文档 1​穷​举​...


穷举法

穷举法:列举出所有可能的情况,逐个判断有哪些符合问 题所要求的条件,从而得到问题的答案。 穷举法也称枚举法 穷举法的思路:列举一切与命题相关的情况,然后根据问 ...


第20学时:用穷举法解决问题_20120402081459515

70页 免费 穷举法 17页 免费 现场目视化及班组看板设计 25页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


用穷举法设计程序

穷举法设计程序_数学_自然科学_专业资料。《穷举法解决问题》教学设计 《用穷举法设计程序》一、教学目标 1、知识与技能 ⑴了解穷举法的基本概念及用穷举法设计...


穷举法

穷举法_学科竞赛_小学教育_教育专区。用穷举法解决问题教学设计 【教材分析】 本节课选自教科版《算法与程序设计》选修第三章的第二节。本节课讲的是现实生活中...


第20学时:用穷举法解决问题_20120402084439546

穷举法解决问题 14页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 第20学时:用穷举法解决问题_2012040208443954...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com