计算机算法与设计分析实验报告

计算机组织与体系结构——实验报告

// 用 t 号L型骨牌覆盖右下角 board[tr + s - 1][tc + s - 1] = t; // 覆盖其余方格

chessBoard(tr, tc, tr+s-1, tc+s-1, s); }// 覆盖右上角子棋盘

if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s);

else {// 此棋盘中无特殊方格// 用 t 号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; // 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); }// 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中

chessBoard(tr+s, tc, dr, dc, s); else {// 用 t 号L型骨牌覆盖右上角

board[tr + s][tc + s - 1] = t;// 覆盖其余方格 chessBoard(tr+s, tc, tr+s, tc+s-1, s); }// 覆盖右下角子棋盘

if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else {// 用 t 号L型骨牌覆盖左上角

board[tr + s][tc + s] = t;// 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); } }

试验运行结果

三：二分搜索 一、实验目的与要求 1、熟悉二分搜索算法；

3

计算机组织与体系结构——实验报告

2、初步掌握分治算法；

二、实验题

1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。 三、程序代码： #include using namespace std; int main() { int const length=100; int n,x;

int a[length];

cout<<\依次输入数组的长度，数组内容，要查找的数\ cin>>n; //输入数组的长度 for(int i=0;i>a[i]; cin>>x;

void BinarySearch(int a[],int n,int x); BinarySearch(a, n, x);

return 0; }

void BinarySearch(int a[],int n,int x) //n:数组长度，i，j分别表示下标 {

int i,j,mid=0,left=0;

int right=n-1;

while(left=0) {

int mid=(left+right)/2; if(x==a[mid]) { i=j=mid; break;

}

if(x>a[mid])

left=mid+1; else

right=mid-1;

}

if ((i==j)&&(i>=0))

cout<<\所找的数据在数组中下标为：\

4

计算机组织与体系结构——实验报告

}

else { }

i=right; j=left;

cout<<\所找的数据不在数组中，其前后下标为：\

如上图所示数组的长度为5，其内容

依次为1 2 3 4 5，所要找的数据位3，他的下表正好是2，结果是正确的

如上图数组的长度为7，输入的数组是1 3 4 6 7 8 9，所要查找的数字式5，它不在数组中，其前后的下表分别为2,3 结果是正确的。 实验小结：

第一个实验自己做了出来，然而第二个实验卡了很久，对棋盘覆盖问题上课听懂了但是应用到实际上就有点问题了，最后还是在同学的帮助下完成的！后面的这个提高题也是查考同学的，虽然自己没能做出来，但是感觉还是应该去学习！

实验二 动态规划算法

一：最长公共子序列问题 一、实验目的与要求

1、熟悉最长公共子序列问题的算法； 2、初步掌握动态规划算法； 二、实验题

若给定序列X={x1,x2,?,xm}，则另一序列Z={z1,z2,?,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,?,ik}使得对于所有j=1,2,?,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 三、实验程序 #include using namespace std;

5

计算机组织与体系结构——实验报告

int fun(char *x) {

char *y=x;

while(*y++){}; return y-x-1; }

void LCSLength(char *x ,char *y,int m,int n, int **c, int **b) {

int i ,j;

for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) {if (x[i]==y[j]) {c[i][j]=c[i-1][j-1]+1; b[i][j]=1;

}

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

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

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

}

void LCS(int i ,int j, char *x ,int **b) {

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

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

else if (b[i][j]== 2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); } int main() { char x[50],y[50];

int m,n;

6

计算机组织与体系结构——实验报告

int **c =new int*[50],**b =new int*[50]; for(int i=0;i<50;i++) { c[i] =new int[50]; b[i] =new int[50]; }

//int c[50][50],b[50][50];

cout<<\请输入第一组字符串：\cin>>x;

cout<<\请输入第二组字符串：\cin>>y; m=fun(x);

n=fun(y);

LCSLength(x,y,m,n,c,b); LCS(m,n,x,b); cout<

return 0; }

四、运行结果

二：最大子段和问题 一、实验目的与要求

1、熟悉最长最大字段和问题的算法； 2、进一步掌握动态规划算法； 二、实验题

若给定n个整数组成的序列a1，a2，a3，??an，求该序列形如ai＋ai＋1＋??＋an的最大值。 三、程序清单 #include using namespace std;

int MaxSum(int n,int *a,int &besti,int &bestj) {

int sum=0; for(int i=0;i

int thissum=0;

for(int j=i;j<=n;j++)

7