算法實驗報告,二分搜索,矩陣聯(lián)乘,最長公共子序列.doc

實驗報告實驗一：一、 實驗名稱二分搜索法二、 實驗?zāi)康木帉懗绦驅(qū)崿F(xiàn)用二分法在一有序序列中查找一個數(shù)三、 實驗內(nèi)容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(輸入數(shù)組長度 n :);scanf(%d,&n);printf(輸入有序數(shù)組（升序）：nn);for(i=0;i=0)printf(%d 在數(shù)組中的下標(biāo)為 %d!nn,x,j);elseprintf(沒找到!nn);main()Input();2、 實驗結(jié)果輸入數(shù)組長度 n :5輸入有序數(shù)組（升序）：a0:1a1:3a2:5a3:7a4:9輸入要查詢的數(shù)字:6沒找到!Press any key to continue輸入數(shù)組長度 n :4輸入有序數(shù)組（升序）：a0:1a1:2a2:3a3:4輸入要查詢的數(shù)字:22 在數(shù)組中的下標(biāo)為 1!Press any key to continue實驗二一、 實驗名稱矩陣連乘求最小計算次數(shù)二、 實驗?zāi)康木帉懗绦蛴脛討B(tài)規(guī)劃法計算矩陣連乘的最優(yōu)值三、 實驗內(nèi)容1、 實驗源代碼#include #define MAX 100int main() int pMAX,i,j,k,r,t,n; int mMAXMAX; /記錄從第i到第j個矩陣連乘的最少計算次數(shù)int sMAXMAX; /記錄從第i到第j個矩陣連乘的斷開位置printf(輸入連乘矩陣的個數(shù):);scanf(%d,&n); for(i=0;in;i+)printf(輸入第%d個矩陣行數(shù):,i+1);scanf(%d,&pi); /讀入pi的值(注意：p0到pn共n+1項) printf(輸入第%d個矩陣列數(shù):,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(最少計算次數(shù):%dnn,m1n); 2、 實驗結(jié)果輸入連乘矩陣的個數(shù):6輸入第1個矩陣行數(shù):30輸入第2個矩陣行數(shù):35輸入第3個矩陣行數(shù):15輸入第4個矩陣行數(shù):5輸入第5個矩陣行數(shù):10輸入第6個矩陣行數(shù):20輸入第6個矩陣列數(shù):25最少計算次數(shù):15125Press any key to continue實驗三：一、 實驗名稱求最長公共子序列二、 實驗?zāi)康木帉懗绦蛘莆談討B(tài)規(guī)劃法中關(guān)于最長公共子序列的實現(xiàn)實驗內(nèi)容三、實驗內(nèi)容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的內(nèi)容:);gets(&X1);printf(請輸入字符串Y的內(nèi)容:);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(