C程序设计笔记---枚举算法策略

枚举法,又称穷举法,个人理解就是程序运行状态是可以别遍历的,遍历算法执行每一个状态,最终会找到一个最优的可行解。

举个栗子,今天中午我和同事商量去哪吃饭的问题,我们都不确定去哪一家,于是我就一家一家的数,臊子面,黄焖鸡米饭,牛肉拉面,鸡汤面......当我说到羊肉泡馍时,我同事眼前一亮,说,走羊肉泡馍走起。。。典型的穷举法,有么有?


世纪难题,今天中午吃什么?

再如计算100以内的所有奇数,就可以采用枚举法。


求奇数

那么,适用于穷举法求解的问题必须满足哪些条件呢?

(1)、可 预先确定每个解的元素N的个数;

(2)、解元素S1、S2....Sn的可能址为一个连续的值域;

应用穷举法的场合有: 求不定方程、排列组合、暴力破解算法;

由此可见穷举法的特点是什么呢?

1、穷举法的特点:

(1)、可供选择的答案或元素的范围是有限的,如今天中午吃什么的问题,我们可供选择的店就那么多家,并不是无限的;

(2)、可能做了很多无用功、浪费了宝贵的时间,所以导致效率比较低;

(3)、可供选择的答案或元素是同一类事物,我们选择去吃饭的地方都是餐馆;

(4)、得到的结果肯定是正确的;

(5)、通常会涉及到求极值(如最大,最小,等)。

所以最终得到的结论是:并不是所有的问题都可以使用穷举法来求解,只有问题的答案个数不是太多时,并且在可以接受的时间内得到结果时才可以使用穷举法。 

2、穷举法的优点: 

(1)、算法简单,比较直观,易于理解;

(2)、最后一定会得到一个结果。

(3)、从全局观点使用穷举法,计算量容易过大,如果在局部地方使用穷举法,计算的效率会显著提高。

3、穷举法的缺点:

(1)、由于穷举法的特点,将可供选择的元素逐一的进行筛选,也就造成了程序在运行的时间比较长;

(2)、当可供选择的答案过大时,可能导致返回结果的时间太长或者其他问题;

4、穷举法的基本思路:

(1)、确定穷举对象,穷举范围和判定条件;

(2)、逐一枚举可能的解,验证是否时问题的解。

5、求解方法和步骤:

(1)、确定可选择的范围内的所有解的集合;

(2)、抽象出答案包含的参数,确定每个参数的数据范围;

(3)、对解的每个参数的数据范围进行循环遍历;

(4)、对每次的循环,根据题意给定的范围判断是否为解;

(5)、优化程序、以便缩小搜索范围,提高程序的效率。

6、穷举法的列举方式:

(1)顺序列举: 是指答案范围内的各种情况很容易与自然数对应甚至就是自然数,可以按自然数的变化顺序去列举。

(2)排列列举: 有时答案的数据形式是一组数的排列,列举出所有答案所在范围内的排列,为排列列举。

(3)组合列举: 当答案的数据形式为一些元素的组合时,往往需要用组合列举。组合是无序的。

举例:百钱百鸡问题用穷举法来求解:

百钱买百鸡

这个数学问题的数学方程可列出如下:

Cock+Hen+Chick=100

Cock*5+Hen*3+Chick/3=100

显然这是个不定方程,适用于穷举法求解。依次取Cock值域中的一个值,然后求其他两个数,满足条件就是解。那么该如何用程序语言来完成呢。

百钱买百鸡 代码块

最终终端打印的结果为:

打印结果

前面已经提到,由于穷举法的特点,当问题的可选范围变大时,循环嵌套的层数越多,计算效率就相对的变低了,此时作为程序员就要对算法做出优化;

如:上面的计算百钱买百鸡的代码中,循环体执行了21*34*101 = 72114次,那么近过分析,从数学的角度来考虑这个问题:根据题意,5x+3y=z/3=100,     x+y+z=100可以消去一个未知数z,最终得到:7x+4y=100,   x+y+z=100,于是只要枚举公鸡x(最多只有14只),最终就可以求出y和z,可用程序表示:


百钱买百鸡 代码块

优化后的代码,只循环了14次,此时的效率明显提升了,由于电脑的运行速度相当快,其实我并没有什么明显的感觉,但是这个问题被无限放大,比如循环次数达到了千万次时优化就会有很明显的效果了,那么总结一下如何做出优化:

7、优化策略:

(1)、减少循环次数;

(2)、合理选择循环的变量;

(3)、注意枚举的顺序;

(4)、减少判断每种情况的时间。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,937评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,503评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,712评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,668评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,677评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,601评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,975评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,637评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,881评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,387评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,971评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2 342

推荐阅读更多精彩内容