蛮力法

来自计算思维百科
跳转至: 导航搜索
蛮力法.png

蛮力法(Exhaustive)也称穷举法,是一种简单、直接地解决问题的方法。

基本概念

蛮力法是指列出问题所有可能的解并逐一测试是否符合要求,找出正确的解。蛮力法是一种比较耗时的算法,但是计算机的出现使得蛮力法有了用武之地。

巧妙和高效的算法很少来自于蛮力法,但基于以下因素,它仍是一种重要的算法设计策略。

1.蛮力法是一种几乎什么问题都能解决的一般性方法;

2.即使效率低下,仍可用蛮力法解决一些小规模的问题实例;

3.如果待解决的问题实例不多,而蛮力法可用一种可以接受的深度对问题求解,那么花时间去设计一个更高效的算法是得不偿失的。

应用范围

蛮力法可用于密码的破译、线路的选择,还能解决中国古代著名趣题、进行逻辑推理判定,求解百钱百鸡、五家共井、谁做的好事、四大胡等问题。排序中的冒泡排序、选择排序也是穷举法。

使用方法及步骤

步骤一:逐一列出问题所有的可能解;

步骤二:对每个解进行判断,看是否符合问题要求;

步骤三:符合则为问题的解,否则进行下一次判断。

应用案例

应用1-打开密码锁

案例:有一个三位数的密码锁,如何打开它?不能用锤子等暴力方法砸开。

 

解决步骤:

步骤一:三位全由数字组成的密码,每一位都在0-9这10个数字中,所以总共有10*10*10种可能性,列出所有数字组合000、001、002、003…;

步骤二:用每一个去尝试开锁;

步骤三:若能够打开,则问题解决,否则进行下一个组合的尝试。

应用2-谁做的好事

案例:某四位同学中有一个做了好事 , 不留名 , 表扬信来了,校长问是谁做的好事 .

A 说 : 不是我

B 说 : 是 C

C 说 : 是 D

D 说 : 他说的不对 !

问:四位同学中肯定有一个人说谎了,那么是谁做的好事?

 

解决步骤:

步骤一:列出所有可能的情况。

A说谎、B说谎、C说谎、D 说谎;

步骤二:对每种情况判断是否符合要求。

如果A说谎,根据A说的,那么就是A做的,但是C和D就都说错了,所以不符合,排除;

如果B说谎,那么根据C说的,就是D做的,但是D说不是他做的,所以也不符合,排除;

如果C说谎,那么根据B说的就是C做的,没有出现矛盾的情况,符合条件,所以好事就是C同学做的。

可以体现的计算思维

蛮力法给出问题所有可能的解,并逐一进行检验是否可行,这种方法简单,但是效率很低,只能解决一些小规模问题,但是非常适合用计算机来实现。蛮力法体现了计算思维的机械化特点。