算法设计与分析复习题(6)

return num; }

28、 设计一个时间复杂性不超过O(n2)的算法，找出n个数组成的序列中最长的单

调递增序列。

比较简单，遍历一遍数组就可以了，这里为了写代码方便默认返回数组长度为1时，不存在递增序列，可以改成0更符合逻辑。

//Result为返回的序列开始指针 RLen为序列长度 increase(Array, Len, &Result, &RLen) { RLen=1; //从Array[0]开始 i记录起始位置 j用于遍历数组 i=0;j=1; while(j=Len) return; //递增序列 一直后移到其末尾 i=j-1; j++; while((jArray[j-1])) j++; //更新返回值 if((j-i)>RLen) { RLen=j-i; Result=Array+i; } i=j; j++; } }

29、 从1，2，?，n中找出所有质数，设计一个较优的算法。

刷选法: Int I,j,count=0; Aa[0]=2;

For(int i=3;i

{

For(j=1;j<=count;j++) If(!(i%a[j])) break; If (j>=count) { Count++; Aa[count]=I; } }

30、 编写一个无向图的深度优先搜索算法，并将其改为非递归算法。

void dfs(vector graph[],int beginnode) {

if(visited[beginnode]==0) { }

for(vector::iterator

it=graph[beginnode].begin();it!=graph[beginnode].end();it++)

{ }

int x=*it; if(visited[x]==0) { s.push(x); dfs(graph,x); }

cout<

//s.pop();

if(s.size()==0) return ;

int newnode=s.top(); s.pop();

dfs(graph,newnode); } 思路：

a.先输出起始结点的值，其实结点入栈。

b.t指向栈顶元素的第一个邻接结点，若t指向结点未访问过，输出t指向的结点，设置t指向的结点为已经访问过，t指向的结点入栈，转到b。若t指向的结点已经访问过，t指向栈顶元素下一个邻接结点，若t指向结点未访问过，输出t指向的结点，设置t指向的结点为已经访问过，t指向的结点入栈，转到b。若栈顶所有邻接结点都已经访问过，出栈。转到b。

void s_dfs(int n) //非递归函数 {

int stack[100];

int top=0; //stack NULL L_NODE* t=head[n]; int v;

printf(\ visit[n]=1;

stack[top++]=n; while(top!=0) {

if(t==NULL) top--;

v=stack[top-1]; //v必定访问过 t=head[v];

while(t!=NULL) {

if(visit[t->ver]==0) {

printf(\ visit[t->ver]=1;

stack[top++]=t->ver; break; }

t=t->link;

}//end while }//end while }

31、 编写一个无向图的宽度优先搜索非递归算法。

void bfs(vector graph[],int beginnode) { }

queue q; q.push(beginnode); while(q.size()!=0) {

int u=q.front(); q.pop(); cout<

for(vector::iterator it=graph[u].begin();it!=graph[u].end();it++) { }

visited[u]=1;

int x=*it; if(visited[x]==0) q.push(*it);

// cout<

32、 测试一个图是否连通图，可以用深度优先搜索算法或宽度优先搜索算法，在

什么情况下，用哪种算法更好一些？

深度优先搜索算法

33、 试求图中所有点对之间的所有路径，在此基础上再改写为找出所有点对之间

最短路径的算法。

问题描述

在一个有向图中,确认任何两个节点有没有通路;

二、算法思想

借用半环的性质,设两点之间有通路,这l(a,b)=1,否则为0,通过动态规划的方法,不断填充c[i][j][k]数组; c[i][j][k]数组表示从点i经过k个节点能否到达节点j;从而求出所有节点间是否有通路;

算法复杂度:为了求出c[i][j][k]数组,用到了三重循环,所以复杂度明显为O(N*3);

三、代码实现 #include #include #include #include #define M 100