算法设计与分析复习题

算法设计与分析复习题

1、一个算法应有哪些主要特征？

有限性、确定性、输入、输出、可行性

2、分治法（Divide and Conquer）与动态规划（Dynamic Programming）有什么不同？ 分治法是将一个问题划分成一系列独立的子问题，分别处理后将结果组合以得到原问题的答案。动态规划同样将一个问题划分成一系列子问题进行处理，但当子问题不是互相独立而是互有联系时，动态规划不会重复计算子问题间联系的问题，是更高效的解决办法。

3、试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。 贪心算法的思想是通过选择局部最优以求得最优解，但某些最优解问题无法由局部最优推出，如0-1 knapsack problem（背包问题，一个能装20斤的背包装入一定商品，要求价值最高） 4、编写一个递归算法求解Hanoi 塔问题。 #include void move(char x,char y) {

printf(\}

void hanoi(int n,char x,char y,char z) { if(n==1) move(x,z); else { } } int main()

hanoi(n-1,x,z,y); move(x,z); hanoi(n-1,y,x,z);

{ int n;

printf(\ scanf(\ hanoi(n,'A','B','C'); return 0; }

5、求解方程f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。 X^2=X+1 解得

X1=(1+√5)/2,，X2=(1-√5)/2。 则F(n)=C1*X1^n + C2*X2^n。 ∵F⑴=F⑵=1。 ∴C1*X1 + C2*X2。 C1*X1^2 + C2*X2^2。 解得C1=√5/5，C2=-√5/5。

∴F(n)=（√5/5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}（√5表示根号5）。 6、求解方程T(n)=2T(n/2)+1，T(1)=1，设n=2k。 T(n)=2n-1;(不确定)

7、求解方程T(n)=aT(n/b)+n，T(1)=1，设n=2k。

8、编写一个Quick Sorting 算法，并分析时间复杂性。 #include

#define M 100000 using namespace std;

int partition(double a[],int p,int r); void quicksort(double a[],int p,int r); int main()

{

double a[M]; srand(time(0)); printf(\ for (int i=0;i

quicksort(a,0,M-1);

if(i==0) printf(\else

printf(\}

a[i]=rand()-5000; a[i]+=rand()/10000.0; if(i==0) printf(\else

printf(\

cout<

return 0; }

void quicksort(double a[],int p,int r)

{

int q; if(p

int partition(double a[],int p,int r) {

double x=a[r]; int i=p-1;

for (int j=p;j<=r-1;j++) { }

double temp=a[i+1]; //将作为基准的最后一个数交换到合适位置

a[i+1]=a[r]; a[r]=temp;

double temp=a[i]; //将比最后一个数大的数交换到后面去 a[i]=a[j]; a[j]=temp; }

if (a[j]<=x) {i++; { }

q=partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r);

return i+1; }

最坏时间复杂度为O(n^2)（每次选中的中间元素为序列的最小或最大元T(n)=T(n-1)+T(0)+O(n)）

最好时间复杂度为O(nlogn)（每次选中的中间元素为序列的正中元素T(n)<=2T(n/2)+O(n)）

平均时间复杂度为O(nlogn)（不会分析??）

9、利用Quick Sorting的原理，编写一个查找第k小元素的算法。 double quicksortk(double a[],int p,int r,int k) {

int q;

q=partition(a,p,r); if((q+1)==k) { }

else if ((q+1)>k)

return quicksortk(a,p,q-1,k); else

return quicksortk(a,q+1,r,k); }

10、 编写一个Heap Sorting算法，并分析时间复杂性。

int heapsize=0; int alength=M-1;

cout<<\return a[q];

int left(int i) { return 2*i; }

int right(int i) {

return 2*i+1; }

.//返回左节点

//返回右节点;

int iparent(int i) { return i/2; }

void heapify(double a[],int i) {

int l=left(i); int r=right(i); int largest;

if(l<=heapsize &&a[l]>a[i])

largest=l; else largest=i;

if(r<=heapsize&&a[r]>a[largest])

largest=r;

if (largest!=i) { }

double temp=a[i]; a[i]=a[largest]; a[largest]=temp; heapify(a,largest);

}

void build_heap(double a[]) {

heapsize=alength;

for (int i=alength/2;i>=1;i--) heapify(a,i); };

void heapsort(double a[]) {

build_heap(a); int k=0;

cout<=2;i--) { } } int main() {

printf(\k++; if(k==0) cout<

//建立大头堆

//调整大头堆

double a[M]; srand(time(0)); printf(\ for (int i=1;i

heapsort(a);

a[i]=rand()-5000; a[i]+=rand()/10000.0; if(i==0) printf(\else

printf(\

return 0; }

时间复杂度为O(nlogn)，heapify()的时间复杂度为O(logn)

11、 证明O(nlogn)是“比较”排序算法时间复杂性的下界。

这个首先要明确一点，只用到比较的排序算法最低时间复杂度是O(nlogn)，而像桶排这样的只需要O(R)(R为桶的大小)

为了证明只用到比较的排序算法最低时间复杂度是O(nlogn)，首先要引入决策树。 首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。

先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。 具有L片树叶的二叉树的深度至少是logL。

所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。 而

log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1 >=logn+log(n-1)+log(n-2)+...+log(n/2) >=(n/2)log(n/2) >=(n/2)logn-n/2 =O(nlogn)

所以只用到比较的排序算法最低时间复杂度是O(nlogn)。

12、 编写一个Radix算法对n个相同长度的整数排序。

#include #include #define M 10 using namespace std; queue m; queue r[10];

int radixsort(queue m,int n) {

for(int i=0;i

while(m.size()!=0)

{

int temp=m.front(); m.pop(); if(i==0)

r[temp].push(temp); else

r[temp/(i*10)].push(temp);*/ int temp2=1; for(int k=0;k

temp2*=10;

/* }

}

r[temp/(temp2)].push(temp);

for(int j=0;j<10;j++) { }

while(r[j].size()!=0) { }

int temp=r[j].front(); r[j].pop(); m.push(temp);

cout<

{ }

int temp=m.front(); m.pop();

cout<

return 0;

}

int main() { int a[M]; //

srand(time(0));

printf(\ for (int i=0;i

radixsort(m,5); a[i]=(int)rand()-5000;

a[i]=(a[i]+120000)0000; m.push(a[i]); if(i==0) printf(\else

printf(\

return 0; }

13、 编写一个算法，可以检测一个字符串是否回文（如：afaddafa，abwba等）。

int fun(char *A,int n){ int i ,j; i=0,j=n-1; while(i<=j){

if(A[i]!=A[j])break; i++;j--;

}

if(i<=j)return 0; else return 1; }

14、 如果是检测一个字符串中是否包含一个回文子串，应如何编写算法。如果是

找最大的回文子串呢？

int judge(char *A,int n0, int n1){ int i,j; i=n0;j=n1; while(i<=j){

if(A[i]!=A[j])break; i++;j--; }

if(i<=j)return 0; else return 1; }

int fun(char *A,int n){ int i,j,k;

for(i=1,i<=n-1;i--){ for(j=0;j

if(judge(&A,j,j+i)==1){output(&A,j,j+i);return 1;} } } return 0; }

如果找最大回文则需更改为； int fun(char *A,int n){ int i,j,k;

for(i=n-1;i>=1;i--){ for(j=0;j<=n-i-1;j++){

if(fun(&A,j,i+j)==1){output(&A,j,i+j);return 1;} } } return 0; }

此时最先找到的即为最大回文。

15、 设n个不同的整数排好序后存在数组T[1：n]中。若存在一个下标i，使得T[i]=i，

设计一个有效的算法找到该下标。要求时间复杂性是O(logn)。

因为整数数组已排好序，可以从数组的正中元素开始寻找T[i]，当T[(n+1)/2]>(n+1)/2时，要求的i一定在T[1:(n+1)/2-1]中，当T[(n+1)/2]<(n+1)/2时，要求的i一定在T[(n+1)/2+1:n]中，递归地使用此方法。 //初始Left=1 Right=n int find_i(T, Left, Right) {

if(Left>Right) return -1; (Left+Right)/2

if(T[(Left+Right)/2]>(Left+Right)/2) return find_i(T, (Left+Right)/2+1, Right); if(T[(Left+Right)/2]<(Left+Right)/2) return find_i(T, Left, (Left+Right)/2-1); else return (Left+Right)/2; }

16、 编写一个采用KMP的算法查找T的子串P，并判断匹配失败的字符是否在P

中，以此确定可滑动的最大距离。

int next[100]; int lenthT,lenthP; void get_next(char *P){ int i,j; i=1;j=0; next[1]=0; while(i<=lenthP){

} }

if(j==0||P[i]==P[j]){ }

else j=next[j];

++i;++j;

if(P[i]!=P[j]) next[i]=j; else next[i]=next[j];

int KMP(char *T,char *P){ int i,j; i=1;j=1; get_next(P);

while(i<=lenthT&&j<=lenthP){ }

if(j>lenthP)return i-lenthP; else return 0; }

17、 编写一个算法找出

if(j==0||T[i]==P[j]){++i;++j;} else j=next[j];

2个正文中的最长公共子序列，若要找

出3个正文中的最长公共子序列，应如何编写算法。

算法思想

X= Y=

的LCS为Z=

(1)若xm=yn,则zk=xm=yn,则z是xm-1和yn-1的LCS; (2)若xm!=yn,且zk!=xm,则z是xm-1和y的LCS; (3)若xm!=yn,且zk!=yn,则z是xm和yn-1的LCS 采用动态规划的思想,

?0 if i?0 or j?0 len(i,j)???len(i?1,j?1)?1 if i,j ?0 and ai?bj?max(len(i?1,j),len(i,j?1)) if i,j ?0 and ai?bj?

通过公共字串的长度以及公共字串的起始地址求出公共字串; 时间复杂度为O(mn); #include #include #define MAXLEN 100

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])

{

int i, j;

for(i = 0; i <= m; i++) c[i][0] = 0; for(j = 1; j <= n; j++) c[0][j] = 0; for(i = 1; i<= m; i++) {

for(j = 1; j <= n; j++) {

if(x[i-1] == y[j-1]) {

c[i][j] = c[i-1][j-1] + 1; b[i][j] = 0; }

else if(c[i-1][j] >= c[i][j-1]) {

c[i][j] = c[i-1][j]; b[i][j] = 1; } else

{

c[i][j] = c[i][j-1]; b[i][j] = -1; } } } }

void PrintLCS(int b[][MAXLEN], char *x, int i, int j) {

if(i == 0 || j == 0) return; if(b[i][j] == 0) {

PrintLCS(b, x, i-1, j-1); printf(\ }

else if(b[i][j] == 1) PrintLCS(b, x, i-1, j); else

PrintLCS(b, x, i, j-1); }

int main(int argc, char **argv) {

char x[MAXLEN] = {\ char y[MAXLEN] = {\ int b[MAXLEN][MAXLEN]; int c[MAXLEN][MAXLEN]; int m, n;

m = strlen(x); n = strlen(y);

LCSLength(x, y, m, n, c, b); PrintLCS(b, x, m, n);

return 0; }

算法实现

#include #include

#include using namespace std; int main() { char x[100]; char y[100]; scanf(\ scanf(\// cin>>y;

int m=strlen(x); int n=strlen(y); int len[100][100]; int z[100][100]; for (int i=0;i

{

len[i][j]=0; z[i][j]=0;

} */

if(x[i]==y[j])

{

//字母相同

}

}

}

if(i==0||j==0) {

len[i][j]=1; } else

len[i][j]=len[i-1][j-1]+1; z[i][j]=i;

// continue; else { }

cout<<\cout<<\

if(len[i-1][j]>len[i][j-1]) {

len[i][j]=len[i-1][j]; z[i][j]=z[i-1][j]; } else { }

len[i][j]=len[i][j-1]; z[i][j]=z[i][j-1];

//printf(\最长公共子序列为%s\//printf(\最长公共子序列为%s\printf(\最长公共子序列长度:%d\\n\

for(int i=0,b=z[m-1][n-1]-len[m-1][n-1]+1;i

18、 编写一个求解8后问题的算法，并作出时间复杂性分析。

#include #include

#include using namespace std; #define N 10 int m,n; int col[N+1]; int vis[3][N*2];

void search(int cur) {

if(cur==m) { } else

for(int i=0;i

if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n])//满足不相互攻击的条件 { //vis[0] 行 vis[1] /对角线 vis[2] \\对角线

col[cur]=i;

vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=1; search(cur+1);

// 搜索下一个皇后位置

cout<<\成功找出方案:\for(int i=0;i

cout<<\第\行放在第\列\cout<

} }

}

vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=0;//回溯,重置状态

int main() {

for(int i=0;i<3;i++) for(int j=0;j<2*N;j++) vis[i][j]=0; scanf(\ m=n; n--; search(0); }

19、 试分析回溯法与分支定界法的异同之处。

(0)分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树种满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或者是在满足约束条件的解种找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

（1）回溯法只通过约束条件来限制搜索，而分支定界不仅 通过约束条件，而且还通过目标函数来限制搜索。

（2）回溯法是应用的深度优先搜索策略，而分支定界采用的 是广度优先搜索策略

20、 采用分支定界法编写一个求解货郎担问题的算法，并作出算法时间复杂性分

析。

21、 假设有k种不同面值的硬币（以元为单位，每种的个数不限）。编写一个用最

少的硬币数找出n元钱的算法，并分析算法的时间复杂性。

int dynamic_coin(int a[],int money,int n) //采用动态规划求解

{

int sum[money+1]; sum[0]=0;

for (int i=1;i<=money;i++) sum[i]=-1;

for (int i=1;i<=money;i++) {

for(int j=0;j

if(i-a[j]>=0) {

if(sum[i-a[j]]==-1) // continue; if(sum[i]==-1)

sum[i]=sum[i-a[j]]+1; else

sum[i]=(sum[i]>sum[i-a[j]]+1)?sum[i-a[j]]+1:sum[i];

//最优解为本身或者sum[i-a[j]]+1 } }

if(sum[money]==-1) return -1; else

return sum[money]; }

}

22、 考虑一个“模糊”的算法查找T的子串P，先快速找到与P相似的子串，再

进一步确认之。

int new_get_index(char *T,char *P) {

int a,b,c;

a=0;b=strlen(p);c=(a+b)/2; int k=0; while(){

if(P[a]!=T[k+a]||P[b]!=T[k+b]||P[c]!=T[k+c]){k++;continue;} for(int j=0;j

} }

23、 设计一个算法确定K个矩阵相乘的最优次序，并分析该算法的时间复杂性。

int dynamic_cross(int i,int j,int m[M][M],int p[M][3]) { if(i==j) { }

for(int k=i;k

m[i][k]=dynamic_cross(i,k,m,p); m[k+1][j]=dynamic_cross(k+1,j,m,p);

int sum=m[i][k]+m[k+1][j]+p[i][0]*p[k][1]*p[j][1]; if(sum

if(j==b)return k;

}

m[i][j]=sum;

return m[i][j]; }

24、 设计一个算法从数A[1：n]中同时找出最大元素和最小元素，只需要不超过

1．5n－2次比较。

void divid(int abegin,int aend,double & maxd,double & mind,double a[]) {

if(aend-abegin<=1) //规模足够小的时候，直接2个数比较 { }

int mid=(abegin+aend)/2; //二分处理 divid(abegin,mid,maxd,mind,a); divid(mid+1,aend,maxd,mind,a);

if(a[abegin]

if(a[aend]

mind=a[aend]; if(a[abegin]>maxd)

if(a[aend]>maxd) maxd=a[aend]; if(a[abegin]

maxd=a[abegin]; }

return ; //关键 一定要退出了 因为已经是递归出口

}

25、 用分治法一个算法从数A[1：n]中同时找出最大元素，分析算法的时间复杂

性，并思考为什么是这样的结果。

采用分治法 T（n）=2T（n/2）+2 T（2）=1 解这递归方程 得 T（n）=1.5n-2 得到优化。

26、 在一个数组中出现次数最多的元素称为“众数”，编写一个找出众数的算法，

并分析算法时间复杂性。

先排序，然后遍历一遍寻找最长的相同元素序列。算法默认出现2次及2次以上才为众数。快排时间复杂度为O(nlogn)，遍历一遍复杂度为O(n)，故算法总时间复杂度为O(nlogn) int number(Array, Len) { //快排

QSort(Array, Len); max=1;num=-1; i=0;j=1 while(i

//遍历 找最长的相同元素序列 while((jmax) { max=j-i; num=Array[i]; } i=j; j=i+1 }

return num; }

27、 设计一个使用Hash法的算法在数组中找出“众数”，并分析时间复杂性。

Hash的方法很关键，不知道有什么简单的方法??这里假设数组中数据范围为0~max，max为数组中最大元素，先找到max，确定了Hash的范围，再使用一对一Hash(direct addressing)。时间复杂性为O(n)（查找最大元时间复杂度为O(n)，遍历一遍数组为O(n)，Hash的时间复杂度为O(1)，故算法时间复杂度为O(n)，当然这里使用的方法受限制极强，不是通用的解答，时间复杂度也不可能有这么好，但是代码容易编写与理解）

//Hash函数 有点假 hash(Brray, i) { Brray[i]++; } //返回-1则未找到众数 默认出现2次及2次以上才为众数 int number(Array, Len) { //找到最大数 max=find_max(Array, Len); //新建一个数组 Brray=new int[max+1]; //初始化其中数据为0 for(i=0;inax) { nax=Brray[i]; num=i; } } //删除Brray数组 delete[] Brray; //返回找到的众数

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

using namespace std;

int l[M][M]; int c[M][M][M]; int link[M][M]; int main() { int n;

cout<<\输入图的节点数:\ cin>>n; int line;

cout<<\输入有向边的数量:\ cin>>line;

vector graph[20];

memset(l,0,sizeof(l));

for(int i=0;i

int a,b;

cout<<\输入相连的两个节点(a->b):\cin>>a; cin>>b; if (a>=n||b>=n) { }

graph[a].push_back(b); l[a][b]=1;

cout<<\输入节点出错:\return 0;

}

for (int i=0;i

for (int k=1;k

for (int i=0;i

for(int j=0;j

link[i][j]=c[i][j][n-1];

for (int i=0;i

for(int j=0;j

c[i][j][k]=c[i][j][k-1]+c[i][k][k-1]*c[k][j][k-1]; if(c[i][j][k]>=1) c[i][j][k]=1; }

for(int j=0;j

// cout<

if(link[i][j]>=1)

cout<<\节点\到节点\有通路\

memset(visited,0,sizeof(visited)); { } return 0;*/ }

四、算法结果

34、 二叉检索树的主要问题是树高，编写一个控制检索树树高的算法。

void OBST(int n) { int i,j,r,l; double t;

for(i=1;i<=n+1;i++) { }

for( l=1;l<=n;l++) {

for ( i=1;i<=n-l+1;i++) c[i][i-1]=q[i-1]; w[i][i-1]=q[i-1];

cout<<\节点\邻接节点:\

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

cout<

cout<<*it;

for(int i=0;i

}

{ }

j=i+l-1; c[i][j]=9999999;

w[i][j]=w[i][j-1]+p[j]+q[j]; for( r=i;r<=j;r++) { }

t=c[i][r-1]+c[r+1][j]+w[i][j]; if(t

c[i][j]=t; root[i][j]=r;

return; }

35、 试写一个在2—3树的插入节点的算法；以及在2—3树的删除节点的算法。 36、 采用深度优先算法找出一个无向图的所有双向连通分支。 37、 编写一个算法，找出一个有向图的所有强连同分支。

38、 为什么查找连通分支的算法总是采用深度优先算法，采用宽度优先算法可以

吗？为什么？ 39、 编写找出一个网络的最大流的算法。

#include #include

using namespace std;

const int maxN=201;

static int edge[maxN][maxN]; bool visited[maxN]; int father[maxN]; int N, M; //边数,顶点数 int ans; //结果 void Ford_Fulkerson( ) {

while(1) {

//一次大循环,找到一条可能的增广路径 queue q;

memset(visited, 0, sizeof(visited)); memset(father, -1, sizeof(father)); int now; visited[0] = true; q.push(0);

while(!q.empty())//广度优先 {

now = q.front(); q.pop();

if(now == M-1) break; for(int i = 0; i < M; i++) {

//每次父亲节点都要更新,权值减为0的边就不算了. if(edge[now][i] && !visited[i]) {

father[i] = now;

visited[i] = true; q.push(i); } } }

//可能的增广路不存在了 if(!visited[M-1]) break; int u, min = 0xFFFF;

for(u = M-1; u; u = father[u])//找出权值最小的边 {

if(edge[father[u]][u] < min) min = edge[father[u]][u]; }

//减去最小权值

for(u = M-1; u; u = father[u]) {

//前向弧减去

edge[father[u]][u] -= min; //后向弧加上

//存在圆环,这句话关键 edge[u][father[u]] += min; }

//当前增广路径增加的流 ans += min; } }

int main() {

int s, e, w;

while(cin >> N >> M) {

ans = 0;

memset(edge, 0, sizeof(edge)); for(int i = 0; i

cin >> s >> e >> w; edge[s-1][e-1] += w; }

Ford_Fulkerson(); cout << ans << endl; } return 0; }

40、 采用最大流算法编写一个二分图的最大匹配算法。 41、 什么是“可证难解性”问题，试举出两个例子。

“可证难解性”问题是不可判定的难解问题和可判定的难解问题的总称，比如货郎担问题，子图同构问题。 42、 P类、NP类、NPC。

P类可以找到一个能在多项式的时间里解决它的算法 用确定型图灵机可以在多项式时间内求解的问题 NP问题是指可以在多项式的时间里验证一个解的问题

? NP类：用非确定型图灵机可以在多项式时间内求解的问题。

NPC 如果任何NP问题都能通过一个多项式算法转换为某个NP问题，那么这个NP问题就称为NPC问题。

43、 一个问题的“难度”是该问题固有的，试举例说明。

一个问题难解性是问题固有的性质，多项式算法是划分问题的类的标准。如果一个问题是不可用的多项式算法求解的，则该问题是难解的。 如停机问题、平铺问题。 44、 简述DTM、NDTM的工作过程。

DTM的执行过程如下:

1.开始时，将?*中的字符串ω放在从1到?ω?的方格中，其它地方放空格符，控制器处在q0状态。

2.读写头扫描第一个方格中的符号a0，转移函数 σ(q0,a0)= (q1,a1,△)根据事先设计好的σ函数表 将当前状态改变为q1 在当前格中将a0改写为a1

根据△=R,S, L确定读写头向右(R),向左(L) ，或不动(S) (一般为σ(qi,ai) = (qi+1,ai+1,△))

3.直至当前状态q为qy 或qn,计算停止， 若q= qy,答案是“肯定”,DTM接受ω； 若q= qn,答案是“否定”,DTM拒绝ω。 4.每个步骤即为一步计算。

非确定型单带图另机（NDTM），其结构与DTM基本相同，只是多了一个猜想模块和一个只写头。 NDTM形式地定义为（Q，?，Γ，σ，?，q0 ，Qf）

45、 为什么说，只要两个不同的编码系统是多项式相关的，就不影响算法复杂性

的多项式性。

某问题在e1编码下的算法时间复杂性是多项式T(n)。在e2编码下，算法不变，算法时间复杂性T(P(n))，也是一个多项式。 46、 简述SAT问题和COOK定理。

SAT问题：给定一组布尔变量V和一组由V组成的字句集合C，判定是否存在一组满足C中所有子句的真值赋值。（布尔表达式可满足性问题） 布尔表达式的可满足性问题SAT是NP完全的。

? Cook证明了在NP类中有一个被称为“可满足性问题”具有如下性质：

NP类中的所有其他问题都可以多项式归约到这个问题。

47、 如何证明一个问题是NPC的。已知TSP是NPC的，试证明Hamilton问题也

是NPC的。

先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性，则NPC问题定义的第二条也得以满足；至于第一个NPC问题是怎么来的，下文将介绍），这样就可以说它是NPC问题了 同样地，我们可以说，Hamilton回路可以约化为TSP问题(Travelling Salesman Problem，旅行商问题)：在Hamilton回路问题中，两点相连即这两点距离为

0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。

48、 当前计算机的速度越来越高，为什么还要研究时间复杂性更低的算法？

问题的复杂过程和规模的线性增长导致时耗的增长和空间需求的增长对低效的算法来说是超线性的，绝非计算机的速度和容量的线性增长得来的时耗减少和存储空间的扩大所能抵消的。

本文来源：https://www.bwwdw.com/article/tl1.html