【精选】算法设计与分析（第四章蛮力法）

命运之光

发布于 2024-03-20 13:53:59

4830

文章被收录于专栏：我在本科期间写的文章我在本科期间写的文章

前言

总结算法设计与分析课程期末必记知识点。

第四章蛮力法

1、蛮力法概念

蛮力法基本思路是对问题的所有可能状态一一测试，直到找到解或将全部可能状态都测试为止。

2、蛮力法的优缺点

优点

逻辑清晰，编写程序简洁。
可以用来解决广域领域的问题。
对于一些重要的问题，它可以产生一些合理的算法。
可以解决一些小规模的问题。
可以作为其他高效算法的衡量标准。

缺点

效率不高。
不适用于大规模问题。

3、蛮力法设计算法分为两类

一类是采用基本穷举思路，另一类是在穷举中应用递归。

4、BF算法——字符串匹配

int BF(string s, string t)	//字符串匹配
{
	int i = 0, j = 0;
	while (i < s.length() && j < t.length())
	{
		if (s[i] == t[j])		//比较的两个字符相同时
		{
			i++;
			j++;
		}
		else                    //比较的两个字符不相同时
		{
			i = i - j + 1;		//i回退到原来i的下一个位置
			j = 0;				//j从0开始
		}
	}
	if (j == t.length())			//t的字符比较完毕
		return i - j;				//t是s的子串，返回位置
	else
		return -1;					//返回-1
}

5、求a的最大连续子序列和

#include<stdio.h>
int maxSubSum3(int a[], int n)	//求a的最大连续子序列和
{
	int i, maxSum = 0, thisSum = 0;
	for (i = 0; i < n; i++)
	{
		thisSum += a[i];
		if (thisSum < 0)			//若当前子序列和为负数，则重新开始下一个子序列
			thisSum = 0;
		if (maxSum < thisSum)		//比较求最大连续子序列和
			maxSum = thisSum;
	}
	return maxSum;
}