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

{

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) //采用动态规划求解