算法设计与分析（期末复习版4）
一、蛮力法概述
1.设计思想
蛮力法又称穷举法或暴力法，基本思路是把问题所有可能解或全部可能状态全部尝试最终找到问题求解。
从算法实现角度看，蛮力法计算可以分为两类，一类是直接采用穷举法进行计算；另一类则是通过穷举中应用递归解决办法。相比而言，前者更加简单，而后者需要结合递归更加复杂。
2.优劣性
该算法逻辑清晰易于实现，可以解决一些小规模问题 ；缺点是设计的大多数算法效率不高，主要适用于小规模问题
3.适用情况
1）搜索所有的解空间：问题的解存在于规模不大的解空间中，一般是为了找出特定的解，把所有的解都找出来判断是否满足所需结果
2）搜索所有路径：不同的路径对应不同的解，需要找出特定解，为此需要遍历把所有的路径都搜索一遍，计算出所有路径对应的解
3）直接计算：基于问题的概念和描述直接计算
4）模拟和仿真：按照求解问题的要求直接模拟和仿真即可
二、蛮力法基本应用
1.穷举思路的一般格式
for(循环变量x所有可能的值)
{
...
if(x满足指定条件)
输出x;
...
}
下面我们给出例题
例1.1
编写一个程序，输出2~1000的所有完全数，所谓完全数是指该数各因子（除了本身）以外之和正好等于本身。例如
6=1+2+3；
28=1+4+7+2+14；
下面我们给出源代码（c语言版本）
# include <stdio.h>
int solve1()
{
int i,j,s;
for(j=2;j<=1000;j++) //循环从2~1000逐个进行判断
{
s=0;
for(i=1;i<j;i++)
{
if(j%i==0) //判断是否是因数
s+=i;
}
if(s==j)
printf("%d\n",j);
}
}
int main()
{
solve1();
}
例1.2
编写这样一个程序，求这样的4位数，该4位数的千位上的数字和百位上的数字擦掉了，知道十位上的数字是1，个位上数字为2，又知道这个数如果减去7就能被7整除，减去8就能被8整除，减去9就能被9整除
下面我们给出源代码
#include <stdio.h>
int main() {
int a, b, s; // a为千位数字，b为百位数字，s为四位数
for (a = 1; a <= 9; a++) { // 千位数字从1到9
for (b = 0; b <= 9; b++) { // 百位数字从0到9
s = a * 1000 + b * 100 + 10 + 2; // 构造四位数，十位是1，个位是2
if ((s - 7) % 7 == 0 && (s - 8) % 8 == 0 && (s - 9) % 9 == 0) {
printf("%d\n", s); // 如果满足条件，打印这个数
}
}
}
return 0;
}
以上方法需要每个进行判断，但是根据数学我们可知，一个数m除了自己以外的因数都在1~m/2区间内，因此可以减少算法运行的时间规模，代码如下：
# include <stdio.h>
int solve1()
{
int i,j,s;
for(j=2;j<=1000;j++) //循环从2~1000逐个进行判断
{
s=0;
for(i=1;i<j;i++)
{
if(j%i==0) //判断是否是因数
s+=i;
}
if(s==j)
printf("%d\n",j);
}
}
int main()
{
solve1();
}
2.简单选择排序和冒泡排序
简单选择排序
简单选择排序就是开始找序列中第一个元素作为最小元素记下其位置，设其位置为最小位置，将该元素的序列作为有序区，将序列分为无序区和有序区，通过穷举法将无序区中最小元素找出来，咋若比最开始的元素小则交换位置，不断减小无序区，增大有序区的过程
下面我们展示代码
# include <stdio.h>
void disp(int a[],int n) //打印序列
{
int i;
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
int swap(int *a,int *b) //交换算法，注意是传地址而不是传变量
{
int temp=*a;
*a=*b;
*b=temp;
}
void SelectSort(int a[],int n) //简单选择排序算法
{
int k;
int i,j;
i=0;
for(i=0;i<n-1;i++) //进行n-1趟排序
{
k=i; //k用来记录每趟无序区中最小元素的位置
for(j=i+1;j<n;j++) //在a[i+1...n-1]中采用穷举法找最小元素a[k]
{
if(a[j]<a[k])
k=j;
}
if(k!=i)
swap(&a[i],&a[k]);
}
}
int main()
{
int n=10;
int a[]={2,5,1,7,10,6,9,4,3,8};
printf("排序前序列为："); disp(a,n);
SelectSort(a,n);
printf("排序后序列为："); disp(a,n);
}
冒泡排序
冒泡排序也将元素分为无序区和有序区，有序区元素均小于无序区，针对无序区的每个位置i从无序区通过交换方式将第i小的元素放在该位置，交换过程采用直接穷举法，从尾部开始，当相邻两个元素逆序时两者交换，当没有元素交换时说明排序完成
下面我们展示代码
# include <stdio.h>
void disp(int a[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void swap(int *x,int *y) //交换两个变量的地址
{
int temp=*x;
*x=*y;
*y=temp;
}
void BabbleSort(int a[],int n)
{
bool exchange=false; //设置布尔变量用作指示器指示是否排序完成没有发生交换
int i,j;
int tmp;
for(i=0;i<n-1;i++) //进行n-1次循环
{
for(j=n-1;j>=i;j--)
{
if(a[j]<a[j-1])
swap(&a[j],&a[j-1]);
exchange=true; //发生交换，指示器变化
}
if(exchange==false) //没有发生交换，可以结束循环
return ;
}
}
int main()
{
int n=10;
int a[]={2,5,1,7,10,6,9,4,3,8};
printf("排序前序列为："); disp(a,n);
BabbleSort(a,n);
printf("排序后序列为："); disp(a,n);
}
3.字符串匹配
问题描述：字符串s和t，若t是s的子串，则返回t在s中的位置（t首字符在s中的对应下标），否则返回-1
下面我们给出BF算法的核心代码
# include <stdio.h>
int BF(string s,string t)
{
int i,j;
while(i<s.length()&j<t.length())
{
if(s[i]==t[j])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(j==t.length())
return i-j;
else
return -1;
}
4.求解最大连续子序列和的问题
给定一个含有n个整数的序列，求出其中最大连续子序列的和
# include <stdio.h>
int maxSum(int a[],int n)
{
int i,j,k;
int maxSum=0,thisSum;
for(i=0;i<n;i++)
{
for(j=1;j<n;j++)
{
thisSum=0;
for(k=i;k<j;k++)
thisSum+=a[k];
if(thisSum>maxSum)
maxSum=thisSum;
}
}
return maxSum;
}
int main()
{
int a[]={-2,11,-4,13,-5,-2};
int n=sizeof(a)/sizeof(a[0]);
int b[]={-6,2,4,-7,5,3,2,-1,6,-9,10,-2};
int m=sizeof(b)/sizeof(b[0]);
printf("排序的最大子序列和为：%ld\n",maxSum(a,n));
printf("排序的最大子序列和为：%ld\n",maxSum(b,m));
}
三、图的深度优先和广度优先遍历
1.图的存储结构
图的遍历时图算法的设计基础，根据搜索方式的不同分为深度优先遍历（DFS）和广度优先遍历(BFS)，这两种遍历应用十分广泛，但是本质上都是基于蛮力法算法。
无论多复杂的图都是由边和顶点组成的，图的存储结构除了存储顶点信息之外还要存储顶点与顶点之间的关系，即边。采用形式化定义图G有两个集合V和E组成，记为V(G,E)，其中V是顶点的有限集合，E是连接V中两个不同顶点的边的有限集合。
图分为无向图和有向图两种类型，再根据图中的边是否带有权值又分为带权图和不带权图 。
图的存储方式常见的有两种，邻接矩阵存储和邻接表存储
1）邻接矩阵存储方法
邻接矩阵是表示顶点之间相邻关系的矩阵，设V(G,E)是含有n(n>0)个顶点的图，各顶点的编号为0~(n-1)，则G的邻接矩阵A是n阶方阵
# define MAXV<最大顶点个数>
typedef struct
{
int no;//顶点编号
char data[MAXN]; //顶点其他信息
} VertexType;
typedef struct
{
int deges[MAXN][MAXN]; //邻接矩阵的边数组
int n,e; //顶点数，边数
VertexType vex[MAXN]; //存放顶点信息
}MGraph;
2）邻接表存储方法
图的邻接表存储方法是一种链式存储结构，图中的每个顶点都建立一个单链表，第i个单链表中的结点表示依附于顶点i的边，每个单链表上附设一个表头结点，将所有表头结点构成一个表头结点数组
typedef struct ANode
{
int adjvex;//该边的终点编号
int weight;//该边的权值
struct ANode *nextarc; //指向下一条边的指针
} AreNode;//边的结点类型
typedef struct Vnode
{
char data[MAXL]; //顶点的其他信息
ArcNode *firstarc; //指向第一条边
}VNode; //邻接表头结点类型
typedef struct AsjList[MAXV] //AsjList是邻接表类型
typedef struct
{
AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
}ALGraph;
2.深度优先遍历（DFS)
图的遍历概念：从给定图中任意一个顶点出发，按照某种搜索方式沿着图的边访问图中所有结点，使得每个节点都只被访问一次，这个过程被称为图的遍历
图的深度优先遍历和广度优先遍历对有向图和无向图都适用。
深度优先遍历的过程是从图中某个顶点v开始，访问顶点v之后将visit[ v ]置为一表示已访问，再选择一个与顶点v相邻并且未被访问的结点w作为初始结点，再从w出发进行深度优先遍历直到所有的图中顶点都被访问过为止。
下面我们给出核心算法代码
void DFS(MGraph g,int n) //运用邻接矩阵的DFS算法
{
int w;
printf("%3d",v); //输出被访问的顶点编号
visit[v]=1; //置已访问标记
for(w=0;w<g.n;w++) //找顶点v的所有相邻结点
if(g.edges[v][w]!=0 && g.edges[v][w]!=INF &&visit[w]=0) //INF表示无穷，即不相邻
DFS(g,w);
}
void DFS(ALGraph *G,int v) //邻接表的DFS算法
{
ArcNode *p;
printf("%3d",v); //输出被访问的结点
visit[v]=1; //表示已访问
p=G->adjlist[v].firstarc;
while(p!=NULL)
{
if(visit[p->adjves]==0) //若p->adjvex顶点未被访问，递归访问它
DFS(G,p->adjvex);
p=p->nextarc;//p指向下一个邻接点
}
}
3.广度优先遍历
图的广度优先遍历搜索过程是首先访问初始顶点v,然后访问顶点v的所有未被访问过的邻接点v1,v2…vt，然后再按照v1,v2…vt的次序访问每一个结点的所有未被访问的邻接点，直到图中所有结点都被访问过为止 。
下面我们给出核心代码
void BFS_AM(AMGragh G , int v){ //邻接矩阵的广度优先遍历
int u , w;
queue<int>Q; //创建一个队列存放int 类型
cout << G.Vex[v] << "\t";
visited[v] = true;
Q.push(v); //将顶点v入队
while(!Q.empty()){ //若队列不为空
u = Q.front(); //则取出队头元素并赋值给u
Q.pop(); //将队头元素出队
for(w = 0 ; w < G.vexnum ; w++){ //依次检查u的所有邻接点
if(G.Edge[u][w] && !visited[w]){ //u、w邻接并且w未被访问
cout << G.Vex[w] << "\t";
visited[w] = true;
Q.push(w);
}
}
}
}
void BFS_AL(ALGragh G , int v){ //邻接表的广度优先遍历
int u , w;
AdjNode *p;
queue<int>Q; //创建一个队列存放int类型
cout << G.Vex[v].data = "\t";
visited[v] = true;
Q.push(v); //将源点v入队
while(!Q.empty()){ //若队列不空
u = Q.front(); //则取出队头元素赋值给u
Q.pop(); //将队头元素出队
p = G.Vex[u].first;
while(p){ //依次检查 u 的所有邻接点
w = p->v; //w 为 u 的邻接点
if(!visited[w]){ //w 未被访问
cout << G.Vex[w].data << "\t";
visited[w] = true;
Q.push(w);
}
p = p->next;
}
}
}
下面是一个关于迷宫的问题讨论
有如下一个迷宫，设计一个程序求指定入口到出口的一条迷宫路径
OXXXXXXX
OOOOOXXX
XOXXOOOX
XOXXOXXO
XOXXXXXX
XOXXOOOX
XOOOOXOO
XXXXXXXO
代码如下
#include <stdio.h>
#define MAXN 10 // 最大迷宫大小
int n = 8; // 实际迷宫大小
char Maze[MAXN][MAXN] =
{
{'O','X','X','X','X','X','X','X'},
{'O','O','O','O','O','X','X','X'},
{'X','O','X','X','O','O','O','X'},
{'X','O','X','X','O','X','X','O'},
{'X','O','X','X','X','X','X','X'},
{'X','O','X','X','O','O','O','X'},
{'X','O','O','O','O','X','O','O'},
{'X','X','X','X','X','X','X','O'}
};
int H[4] = {0, 1, 0, -1}; // 水平偏移量
int V[4] = {1, 0, -1, 0}; //垂直偏移量
void display() // 输出迷宫
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
printf("%c ", Maze[i][j]);
printf("\n");
}
}
void DFS(int x, int y, int visited[MAXN][MAXN])
{
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || Maze[x][y] == 'X') // 检查边界和是否是障碍
return;
if (x == n - 1 && y == n - 1) // 找到出口
{
display();
return;
}
visited[x][y] = 1; // 标记当前位置为已访问
Maze[x][y] = ' '; // 标记路径
DFS(x + V[0], y + H[0], visited); // 向右
DFS(x + V[1], y + H[1], visited); // 向下
DFS(x + V[2], y + H[2], visited); // 向左
DFS(x + V[3], y + H[3], visited); // 向上
Maze[x][y] = 'O'; // 回溯，恢复路径标记
visited[x][y] = 0; // 回溯，恢复访问标记
}
int main()
{
int visited[MAXN][MAXN] = {0}; // 初始化访问数组
int startX = 0, startY = 0; // 起点坐标
printf("一条迷宫路径：\n");
display(); // 显示初始迷宫状态
printf("\n");
DFS(startX, startY, visited); // 开始深度优先搜索
return 0;
}