算法实验报告,二分搜索,矩阵联乘,最长公共子序列.doc

实验报告实验一：一、 实验名称二分搜索法二、 实验目的编写程序实现用二分法在一有序序列中查找一个数三、 实验内容1、 程序源代码#includeint Research(int a,int x,int n)int left=0,right=n-1,mid;if(n0&x=a0)while(leftright)mid=(left+right+1)/2;if(xamid)right=mid-1;elseleft=mid;if(x=aleft)return left;return -1;void Input()int a30,n,i,j,x;printf(输入数组长度 n :);scanf(%d,&n);printf(输入有序数组（升序）：nn);for(i=0;i=0)printf(%d 在数组中的下标为 %d!nn,x,j);elseprintf(没找到!nn);main()Input();2、 实验结果输入数组长度 n :5输入有序数组（升序）：a0:1a1:3a2:5a3:7a4:9输入要查询的数字:6没找到!Press any key to continue输入数组长度 n :4输入有序数组（升序）：a0:1a1:2a2:3a3:4输入要查询的数字:22 在数组中的下标为 1!Press any key to continue实验二一、 实验名称矩阵连乘求最小计算次数二、 实验目的编写程序用动态规划法计算矩阵连乘的最优值三、 实验内容1、 实验源代码#include #define MAX 100int main() int pMAX,i,j,k,r,t,n; int mMAXMAX; /记录从第i到第j个矩阵连乘的最少计算次数int sMAXMAX; /记录从第i到第j个矩阵连乘的断开位置printf(输入连乘矩阵的个数:);scanf(%d,&n); for(i=0;in;i+)printf(输入第%d个矩阵行数:,i+1);scanf(%d,&pi); /读入pi的值(注意：p0到pn共n+1项) printf(输入第%d个矩阵列数:,n);scanf(%d,&pn); for(i=1;i=n;i+) /初始化mii=0 mii=0; for(r=1;rn;r+) /r为i、j相差的值 for(i=1;in;i+) /i为行 j=i+r; /j为列 mij=mi+1j+pi-1*pi*pj; /给mij赋初值 sij=i; for(k=i+1;kj;k+) t=mik+mk+1j+pi-1*pk*pj; if(tmij) mij=t; /mij取最小值 sij=k; printf(最少计算次数:%dnn,m1n); 2、 实验结果输入连乘矩阵的个数:6输入第1个矩阵行数:30输入第2个矩阵行数:35输入第3个矩阵行数:15输入第4个矩阵行数:5输入第5个矩阵行数:10输入第6个矩阵行数:20输入第6个矩阵列数:25最少计算次数:15125Press any key to continue实验三：一、 实验名称求最长公共子序列二、 实验目的编写程序掌握动态规划法中关于最长公共子序列的实现实验内容三、实验内容1、 实验源代码#include #include void LCSLength(int m, int n, char *x, char *y, int (*c)20, int (*b)20)int i,j;for(i = 0; i = m; i +)ci0 = 0;for(i = 0; i = n; i +)c0i = 0;for(i = 1; i = m; i +)for(j = 1; j = cij - 1)cij = ci - 1j;bij = 2;elsecij = cij - 1;bij = 3;void LCS(int i,int j,char *x, int (*b)20)if(i = 0 | j = 0)return;if(bij = 1)LCS(i - 1, j - 1, x, b);printf(%c,xi);else if(bij = 2)LCS(i - 1, j, x, b);elseLCS(i, j - 1, x, b);int main()char X20, Y20;int b2020,c2020;int m,n;X0 = Y0 = $;printf(请输入字符串X的内容:);gets(&X1);printf(请输入字符串Y的内容:);gets(&Y1);m = strlen(X);n = strlen(Y);printf(字符串X的长度是%d,字符串Y的长度是%dn,m,n); LCSLength(m, n, X, Y, c, b);printf(最长的公共子序列是：n);LCS(