计算机算法设计与分析.doc

一、实验内容及运行结果：2-3、设a0:n-1是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。/* *算法分析 */ 这个问题是二分查找的变形。普通的二分查找返回待查找元素的下标。这里需要返回两个下标。需要特别注意的一点是当待查找元素比第一个元素还小时，无法返回比其更小的元素下标。当待查找元素比最大元素大时，亦然。这种情况需要特殊处理一下，以防出错。程序如下：#include stdio.h#define N 10int Search(int *date,int n,int number);int Find(int *date,int n,int number);void main(void)int dateN;int number;int n;int i;printf(请输入10个数值:n);for(i = 0;i N;i+)scanf(%d,date+i);printf(请输入任意一个数:t);scanf(%d,&number);n = Search(date,N,number);if(n = -1)Find(date,N,number);elseprintf(你想要找的值下标为%d,在数组中第%d位,n,n+1);/二分搜索查找int Search(int *date,int n,int number)int left = 0;int right = n - 1;int mid;while(left = right)mid = (left + right)/2;if(number = datemid)return mid;else if(number datemid)left = mid + 1;return -1;int Find(int *date,int n,int number)int k = 0;int i;if(number daten - 1)printf(你想要找到的值大于数组中的最大值，比它小的数在数组中的下标是%dn,n - 1);elsefor(i = 1;i number)printf(你要找的数不在数组中，比它小的值的下标是%d，比它大的值的下标是%dn,i - 1,i);return;运行结果：3-1、设计一个O（n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。/* *算法分析 */ 题目要求在O(n*n)的时间内找出n个数组成的序列的最长单调递增子序列,需要用到排序算法，查找最长公共子序列的算法。将数组a复制到数组x,先用排序算法将数组x排序，在调用查找最长公共子序列的算法求出数组a和数组x中的最长公共子序列，因为数组x是单调递增的，所以由此求出来的最长公共子序列就是题设所求的最长单调递增子序列。程序如下：#include #define N 30void printOut(int i);void Paixu(int n);int pN,aN;void main()int i,n;printf(请输入个数:t);scanf(%d,&n);printf(请输入数组:n);for(i=0;in;i+)scanf(%d,&ai);Paixu(n);void Paixu(int n)int mN;int i,k,max;m0=1;p0=-1;for(i=1;in;i+)max=0;pi=-1;for(k=0;kmax&akai)pi=k;max=mk; mi=max+1;i=0;for(k=1;kmi)i=k; printf(子序列为:n);printOut(i);printf(n长度为=%dn,mi);void printOut(int i)if(pi=bk，即ai大于长度为K的序列中的最后一个元素，这样就可以使序列的长度增加1，即K=K+1,然后现在的bk=ai；2. 如果aibk，那么就在b1.bk中找到最大的j,使得bjai,然后因为bjai，所以ai大于长度为j的序列的最后一个元素，那么就可以更新长度为j+1的序列的最后一个元素，即bj+1=ai。程序如下：#include#includeusing namespace std; #define N 10 void LCSL(int m,int n,int *x,int *y,int *c,int *b);void LCS(int i,int j,int *x,int *b);void QuickSort(int a,int p,int r);int Partition(int a,int p,int t);void Swap(int &x,int &y); void LCSL(int m,int n,int *x,int *y,int cN,int bN)c00=0;int i,j;for(i=1;i=m;i+)ci0=0;for(i=1;i=n;i+)c0i=0;for(i=1;i=m;i+) for(j=1;j=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; coutcmmendl;/根据bij的内容打印a,x数组的最长公共子序列void LCS(int i,int j,int *x,int bN) if(i=0|j=0) return;if(bij=1) LCS(i-1,j-1,x,b); for(int y=1;yi;y+) if(xy=xi) return; coutxi ; else if(bij=2)LCS(i-1,j,x,b);else LCS(i,j-1,x,b);void QuickSort(int a,int p,int r)if(px);while(ij)&a+i=j)break;Swap(ai,aj);ap=aj;aj=x;return j; void Swap(int &x,int &y)int t;t=x;x=y;y=t;void main(void) int *a,*x;a=new intN;x=new intN;int bNN;int cNN;cout请输入十个数：endl;for(int i=1;iai; xi=ai;QuickSor