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--第15课时 穷举法

跟我学vb--第15课时 穷举法_IT/计算机_专业资料。跟我学vb 穷举法重点: 重点:1、穷举法的基本思想 2、利用穷举法设计程序的基本步骤和方法 穷举技巧(方案的...


穷举法详细

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


用穷举法解决问题教学设计

穷举法解决问题 一、 教材分析: 《用穷举法解决问题》是高中信息技术选修模块《算法与程序设计》第三章《程序 的实现》 第二节内容。 本章侧重于运用算法解决...


利用穷举法解决问题(说课稿)

5页 免费 c语言穷举法傻瓜教程 暂无评价 6页 免费 穷举法 69页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


用穷举法解决问题教学设计

穷举法解决问题教学设计(原创) (2008-06-02 09:26:36) 转载 标签: 分类:教育随笔教育 一、教材分析与教法: 我校选用的是教育科学出版社的《算法与程序设计...


3.2用穷举法解决问题教案

最终提出穷举算法及其基本思想: 穷举法:穷举法也叫枚举法、列举法,它是将求解对象一一列举出来,然后逐一加以分析、处理, 并验证结果是否满足给定的条件,穷举完所有...


用穷举法设计程序

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


穷举法教学设计(高中信息技术精品)

穷举法教学设计(高中信息技术精品)_其它课程_高中教育_教育专区。穷举法 【教学目标】 知识与技能: (1)了解穷举法的基本概念和用穷举法设计程序的基本过程。 (2...


穷举法、贪心法、分枝限界法

穷举法、贪心法、分枝限界法讲解人: 一、穷举法(枚举法)(一)算法思路 就是...初看起来, 这些量度标准似乎都是可取的。 但实际上, 用其中的大多数量度标准...


百元买鸡问题 穷举法 c++

百元买鸡问题 穷举法 c++_理学_高等教育_教育专区。用c++语言设计百元买鸡问题的方案。穷举法穷举法”也称“枚举法” ,即将可能出现的各种情况一一测试,判断...

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