算法蛮力法

㈠ 蛮力法是什么样的算法

《算法设计与分析基础》学习 --- 蛮力法 要重温算法思想，并以《算法设计与分析基础》这本书作为教材。该书每一章介绍一种算法设计思想。今天从最简单的开始写起，打好基础。以后再逐步深入，学习更深入的算法。 蛮力法就是一种解决问题的最简单最直观的最容易理解方法，虽然它简单，而且在实际应用中因为效率的原因可能不能派上用场，但是还是不能忽略它。正如书中作者所说，在解决小规模问题的时候也不失为一个方法，而且也是更复杂算法的基础。 一、选择排序
以最简单的思路解决排序问题，对于N个元素的数组，通过N次扫描数组，每次选择出最小的元素放置到正确的位置，N趟扫描后即完成排序。 show sourceview source print? 01/* 02 蛮力法-选择排序 03 将输入数组排成非递减数组 04 05 array:待排数组 06 n:数组大小，即[0,n-1] 07*/08void SelectionSort(int array[],unsigned int n) 09{ 10 int min; 11 for(int i=0;i<n-1;i++) 12 { 13 min=i; 14 for(int j=i+1;j<n;j++) 15 { 16 if(array[j]<array[min]) 17 min = j; 18 } 19 if(i!=min) 20 { 21 int temp = array[i]; 22 array[i] = array[min]; 23 array[min] = temp; 24 } 25 } 26}//SelectionSort
这是一个最差的排序方法，对于任何输入都是 O(n*n)的时间复杂度。但是它的最大优点就是交换次数最少。 二、冒泡排序
又是一个经典的蛮力排序算法。这里我仅仅对原始的冒泡做了点点改进，如果算法已经排好序的话该算法扫描一遍便完成排序。
show sourceview source print? 01/* 02 蛮力法-冒泡排序(稍微改进版) 03 将输入数组排成非递减数组 04 05 array:待排数组 06 n:数组大小，即[0,n-1] 07*/08void BubbleSort(int array[],unsigned int n) 09{ 10 int i=n-1; 11 int last; 12 while(i>0) 13 { 14 last = 0; 15 for(int j=0;j<i;j++) 16 { 17 if(array[j]>array[j+1]) 18 { 19 int temp = array[j]; 20 array[j] = array[j+1]; 21 array[j+1] = temp; 22 23 last = j; //记录最近一次交换值的位置 24 } 25 } 26 i = last; 27 } 28}//BubbleSort
但是在最差的情况下，它还是O(n*n)的时间复杂度。 三、顺序查找和字符串的蛮力匹配
顺序查找，再简单不过的查找算法了，算是对蛮力思想的一种应用。以及字符串的蛮力匹配也是这样的。

㈡ 简要叙述蛮力法,基本常用的例子有哪些

蛮力法（brute force method，也称为穷举法或枚举法）是一种简单直接地解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法。

蛮力法特性：
（1）理论上，蛮力法可以解决可计算领域的各种问题。

（2）蛮力法经常用来解决一些较小问规模的问题。

（3）对于一些重要的问题（如排序、查找、串匹配），蛮力法可以设计一些合理的算法，这些算法具有实用价值，而且不受输入规模的限制。

（4）蛮力法可以作为某类问题时间性能的下界，来衡量同样问题的其他算法是否具有更高的效率。

查找问题中使用蛮力法。

顺序查找：

是指在查找集合中一次查找值为k的元素，若查找成功，则给出元素在查找集合中的位置；若查找失败，则给出失败信息。

【想法】：将查找集合放在一维数组中，然后从数组的一端向另一端逐个将元素与带查找值进行比较，若相等，则查找成功，给出该元素在查找中的序号；若整个数组检测完仍未找到与带差值相等的元素，则查找失败，给出失败标志0。我们在查找过程中还要注意下标是否越界的问题。

算法的实现方法一：

int SeqSearch1(int r[] ,int n, int k) //数组r[1] r[n]中存放查找集合。
{
int i = n;
while(i>0 && r[i]!k) //注意检测比较位置是否越界。
{ i--; }

return i;
}

上述算法我们每次都要去判断数组的下标是否越界，为了避免在查找过程中每一次比较前都要判断查找位置是否越界，可以设置观察哨，即将待查值放在查找方向的“尽头”处，则比较位置i至多移动到下标0处。

㈢ C语言暴力

所谓的暴力算法，就是用穷举的方法解决问题。
例如，如果让你验证一个数num是否为素数，暴力算法就是穷举2->num-1的每一个值，然后看这些值有没有num的因子。当穷举结束时就可以判断num是不是素数了。

㈣ bf算法是什么

BF算法，即暴力(Brute Force)算法。

是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。

如果一个多位数并且包含以上所有可能字符的密码，其组合方法一定多的惊人，且每增加一位数，密码组合数量会以数十倍指数成长，破译的时间也会更长，有时可能长达数十年（即便考虑电脑性能依摩尔定律的进步），甚至更久。

由于穷举法破解所消耗的时间不小于完成破解所需要的多项式时间，故从密码学角度考虑，不认为穷举法是有效的破解方法。

字典攻击

破译一个相当长度并且包含各种可能字符的密码所耗费的时间相当长，其中一个解决办法就是运用字典。所谓“字典攻击”就是使用预先制作好的清单，例如：英文单字、生日的数字组合、以及各种常被使用的密码，等等，利用一般人习惯设置过短或过于简单的密码进行破译，很大程度上缩短了破译时间。

防护手段

最重要的手段是在构建系统时要将系统设计目标定为即便受到暴力破解的攻击也难以被攻破。以下列举了一些常用的防护手段：

1、增加密码的长度与复杂度。

2、在系统中限制密码尝试的次数。

3、密码验证时，将验证结果不是立即返回而是延时若干秒后返回。

4、限制允许发起请求的客户端的范围。

5、禁止密码输入频率过高的请求。

6、将密码设置为类似安全令牌那样每隔一定时间就发生变化的形式。

7、当同一来源的密码输入出错次数超过一定阈值，立即通过邮件或短信等方式通知系统管理员。

8、人为监视系统，确认有无异常的密码试错。

9、使用双因子认证，例如用户登录账号密码时，系统同时发送短信到用户的手机，用户需输入短信内的认证码。

㈤ 动态规划算法中的状态与蛮力法中的穷举对象,有什么异同

线性规模、作用。
1、异点：动态规划算法中的状态由于是动态的，所以线性规模会表现出很大的状态，蛮力法中的穷举对象适用于解决极小规模或者复杂度线性增长，而线性规模不会有很大的状态。
2、同点：动态规划算法中的状态与蛮力法中的穷举对象共同的作用就是为了解决问题。