暴力法

暴力法,又叫蠻力法,算法的一種。

暴力法,又叫蠻力法,算法的一種。
英文:

brute force

廣義的暴力法

利用枚舉所有的情況,或者其它大量運算又不用技巧的方式,來求解問題的方法。
廣義的暴力法在解決問題,特別是數學和計算機編程問題方面套用廣泛,有著巨大的作用。它的缺點是效率低下,優點是編碼複雜度低,幾乎不用思考,不容易出錯。
例如:判斷一個正整數n是不是素數。
用這個數除以2到n-1之間的數,如果都不能整除就是素數,否則不是素數。這種方法是暴力法。而利用其它方法,如Rabin-Miller等方法判定就不是暴力法。

狹義的暴力法

這是一種簡單的串匹配算法,用來判斷一個短串t是不是一個長串s的子串。
過程很簡單,就是從s的第一個元素和t的第一個元素開始比較,如果相同則比較下一個。不相同則t返回到第一個元素,s回到上次開始位置的下一個位置,繼續比較。如果出現一個和t全部相同的,就匹配成功。如果s到結尾都沒有,就匹配失敗。
過程:
1.i指向s[]的第一個元素,j指向t[]的第一個元素。
2.如果s[i]等於t[j],進行第3步;否則進行5步。
3.i和j都向後移動一位。
4.如果到達t[]的結尾,匹配成功,返回子串位置;否則進行第2步。
5.i向後移動一位,j回到開頭元素。
6.如果到達s[]的結尾,返回失敗;否則進行第2步。
C語言代碼:
int bruteforce(char s[],char t[])
{
int i,j;
for(i=0;s[i]!='\0';i++)
{
j=0;
while(s[i+j]==t[j])
{
j++;
if(t[j]=='\0') //到達t[]的結尾,返回成功匹配的位置
return i;
}
}
return -1; //返回失敗
}

相關詞條

相關搜尋

熱門詞條

聯絡我們