Brute-force算法

来自计算思维百科
跳转至: 导航搜索
Brute-force算法.png

蛮力法是一种经典的模式匹配算法,这种算法利用枚举所有的情况,或者其它大量运算又不用技巧的方式来求解问题。

基本概念

蛮力法在解决问题时,把问题所有的解都罗列出来,逐一判断是否是合适的解,这种方法特别适合利用计算机编程进行实现。

应用范围

对于所有可以把所有组合罗列出来的问题,蛮力法都适用。

使用方法及步骤

根据问题描述,把所有可能的情况全部列出来,逐一验证。

应用案例

应用1-判断一个正整数n是不是素数

解决方案:用这个数除以2到n-1之间的数,如果都不能整除就是素数,否则不是素数。这里所有可能的因子逐一去除n,就是把所有可能的情况列出来,然后逐一判断。

应用2-字符串匹配

案例:我们在百度中搜索关键字时,就是利用字符串匹配实现的。假设要在s中搜索是否存在字符串t,过程很简单,就是从s的第一个元素和t的第一个元素开始比较,如果相同则比较下一个。不相同则t返回到第一个元素,s回到上次开始位置的下一个位置,继续比较。如果出现一个和t全部相同的,就匹配成功。如果s到结尾都没有,就匹配失败。

可以体现的计算思维

它的缺点是效率低下,优点是编码复杂度低,几乎不用思考,不容易出错。体现了计算机思维的机械化特点。