Video在线视频

大家好

这一节讲

算法设计方法之枚举

先看一些生活中的事例

大家知道

旅行箱现在多半都配了密码锁

外出旅行时

为了安全起见

人们都会用密码锁锁住旅行箱

令人尴尬的是

有时候人们会忘记密码

这可怎么办呢

最笨也许最可行的办法就是

从000到999挨个儿试

肯定能找出密码来

不过

这是一件很不爽的苦差事

但确实能解决问题

再看一个有趣的事例

早年漫步街头

发现有人在街边

设了这么一个“赌局”

一中年男子在地上摆一张白纸

一支笔

旁边还有一份“游戏规则”

规则明确指出

谁要是一口气不间断地

在白纸上从1写到300

而没有半点错漏

则给你20块钱

如果有一点错漏

则给设局之人5块

这么简单的“游戏”

谁都认为自己能赢

于是 不少人上前一试“身手”

结果出人意料

竟然输多赢少

设局之人暗自高兴不已

为什么这么简单的事情

“输多赢少”呢

原来人很容易疲劳

虽然写几个数字

是很简单的事情

但不断重复这些简单的事情

容易使人疲劳

人一疲劳就容易出错

这或许是人类自身的不足之一

正因为如此

一些睡眠有问题的人

比如神经衰弱

心事重重

喝了浓咖啡等等

睡不着的时候就开始数数

或者想象着在草地上数羊

数着数着也许就睡着了

非常有意思的是

计算机跟人不一样

与人相比

它的最大特点恐怕就是

计算速度非常快

太快

在这一点上

人类已经被远远甩在了后面

而且永远也别想赶上它

另外 它还不怕麻烦

不嫌累

不会疲劳

除非出现硬件故障或掉电

枚举法正是利用了

计算机的这一特点

甚至把这一特点发挥到了极致

我们知道

银行卡的密码通常是6位数字

也就是说

任何一张银行卡的密码

都在000000到999999

这个范围之内

理论上

如果一个一个去试探

只要有足够的耐心和时间

肯定可以试探出来

只是没有哪一家银行的柜员机

允许你这样做

即便允许你这样去试探

恐怕也要把人累得要死

但是如果利用计算机来做这件事

恐怕要不了1分钟

就可以“搞定”

这种破解方法

也称为暴力破解法

有时候也叫做蛮力法

枚举法也叫穷举法

它的基本思想是

首先依据题目的部分条件

确定答案的大致范围

然后在此范围内

对所有可能的情况逐一验证

直到全部情况验证完为止

如果某个情况

使验证符合题目的条件

则为本题的一个答案

如果全部情况验证完

均不符合题目的条件

则问题无解

以枚举思想设计算法

能解决许多问题

所以应用非常广泛

比如“百鸡问题”

“白鸡问题”说的是

公鸡每只五元

母鸡每只三元

小鸡三只一元

花100块钱买100只鸡

要求每种鸡至少买一只

试问有多少种不同的买法

“百鸡问题”是一个

不定方程的问题

我们不妨设xyz分别表示

公鸡

母鸡

小鸡 买多少只

公鸡每只五块

母鸡每只三块

小鸡三只一块

对于一百块钱买一百鸡的问题

我们可以写出下面的代数方程

也就是

x 加 y 加 z 等于 100

另外一个方程是

5x加3y加z除以3等于100

除此以外

你再也找不出别的方程了

那么两个方程怎么解三个未知数

这是典型的不定方程组

这类问题用枚举法来写算法

就很方便

它的基本思想是

把xyz可能的取值

一一列举

如果有解

解必在其中

如果不止一个解

也能全部找出来

枚举法的特点是算法思想

很简单

对求解那些可确定解的范围

并且一时又找不到

其他更好的方法的时候

就可以用它

这就是“百鸡问题”的枚举算法

这个算法其实很简单

它是一个两重循环

外循环 x从1循环到20

表示公鸡至少要买一只

顶多也就是买20只

内循环 y从1循环到33

表示母鸡至少要买一只

顶多也就是买33只

一旦x和y确定了

z可以用100减去x

减去y计算

那么只要

5x加3y加z除以3等于100

满足这么一个条件

就能找到一组解

这个循环

循环下去

就可以把所有可能的解找出来

那么我们再来看第二个例子

求自然数M和N的最大公约数

类似这样的题

用枚举法来求解也是很简单的

我们可以先找出

M与N之间较小的那个数

把它设为T

则M和N的公约数的取值范围

就可以确定了

这个范围就是从1到T

最大公约数

自然也在这个区间里面

接下来我们从大到小去枚举

找到的第一个公约数

就是我们要找的解

这就是求最大公约数的算法

这个算法非常简单

首先是一个条件语句

if M大于等于N

T取N的值

否则T取M的值

然后就是一个while循环

这个循环当M和T不能整除

或者N和T不能整除的时候

就循环

执行循环体

循环体就是使T减一

然后继续循环

这样找到的

第一个满足条件的T

就是我们所需要的解

可见枚举法并不高明

但效果却很好

它充分体现了

“扬长避短”的“计算思维”

因为 一计算机的计算速度

远胜于人

它能轻易地从1枚举到n

二 重复做类似的事情

人很容易疲劳出错

机器不会这样

好 这一节就到这

谢谢大家