算法设计与分析报告◎小组成员：陈壮茂，陈振凯，张建龙，莫媚，林晓丹◎报告内容：1.给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1] 中的元素的最大值和次大值.◎分析：a[0:n-1] 是说这个数组有n个元素，序号为0到n-1 n+[logn]-2就是一个算法复杂度，应该是n+logn的整数部分-2。
◎首先对数组相邻的两个进行比较，将大的放在后面，小的放在前面，然后在两个数中小的所有数选出最小，同时也在两个数中大的所有数选出最大的。
可以得出总的比较次数：(int)(n/2)+2*((int)(n/2)-1).◎代码如下：#include<iostream.h>#define N 9int k=0;int max(int num[],int n){int big[N],i;cout<<"max"<<endl;for(i=0;2*i<=n-2;i++){if(k++,num[i]>num[n-i-1])big[i]=num[i];elsebig[i]=num[n-i-1];}if(n%2!=0){big[i]=num[i];i++;}if(i==1)return big[0];elsereturn max(big,i);}int fun(int &second,int num[],int n){int big[N],small[N],i,number;第1页cout<<"fun"<<endl;for(i=0;2*i<=n-2;i++){if(k++,num[i]>num[n-i-1]){big[i]=num[i];small[i]=num[n-i-1];}else{big[i]=num[n-i-1];small[i]=num[i];}}if(n%2){big[i]=num[i];i++;}number=max(small,i);second=second>number? second:number;k++;if(i==1)return big[0];elsereturn fun(second,big,i);}void main(){int num[N],second,i,large;cout<<"请输入"<<N<<"个数"<<endl;for(i=0;i<N;i++)cin>>num[i];second=num[0]>num[1]? num[1]:num[0];k++;large=fun(second,num,N);cout<<"最大值是:"<<large<<endl<<"次大值是："<<second<<endl<<"其中比较次数为："<<k<<endl;}◎最初数据第2页◎运行过程中的数据变化与结果2.求数列的最大子段和(要求时间复杂为nlogn)◎分析：给出n个整数（亦正亦负）组成的序列a[1],a[2],a[3],…,a[n],求该序列中a[i]+a[i+1]+…+a[j]的子段和的最大值。
当最大子段和为负数时,规定此数列的最大子段和为0. ◎算法和思路: 依据上面的描述,所求的点i最大路径和c[i]应该为:Max{a[i], c[i - 1] + a[i]}int maxSubSum(int P[]){ int i;int maxsum = 0;int c = 0;for(i = 0; i < MAX; i++){if(c > 0)c += P[i];elsec = P[i];if(c > maxsum)maxsum = c;}return maxsum;}◎主函数：int main(){ int A[MAX];int i，sum;printf("Please input a array: ");for(i = 0; i < MAX; i++)scanf("%d",&A[i]);sum = maxSubSum(A);printf(" The Max subsum is: %d",sum);第3页return 0;}◎当输入数据为：8, 4, -1, 14◎运行过程：c=8+4=12(C=8+4-1)<12（和会下降，于是不能赋值给maxsum）(C=8+4-1+14)>12(和又上升了，赋值给了C值)3.设计一个O(n*n)时间的算法,找出由n个数组成的序列最长单调递增子序列.◎分析：（1）递推关系①对a(n)来说，由于它是最后一个数，所以当a(n)从开始查找时，只存在长度为1的不下降序列。
②若从a(n-1)开始查找，则存在下面两种可能性：若a(n-1)<a(n)，则存在长度为的不下降序列。
若a(n-1)>a(n) ，则存在长度为的不下降序列。
③若从a(i)开始，此时最长不下降序列应该按下列方法求出：在a(i+1),a(i+2),…,a(n)中，找出一个起始数据比a(i)大且最长的不下降序列，作为它的后续。
(2)数据结构设计用数组b[i]记录点i到得最长的不下降子序列的长度，记录点i在最长的不下降子序列的后继续数据编号。
◎算法如下：Int maxn=100;Int a[maxn],b[maxn],c[maxn];Main(){int n,I,j,max,p;input(n);for(i=1;i<=n;i=i+1){input(a[i]);b[i]=1;c[i]=0;}For(i=n-1;i>=1;i=i-1){max=0;p=0;for(j=i+1;j<=n;j=j+1)if(a[i]<a[j] and b[j]>max){max=b[j];p=j;}if(p<>0){b[i]=b[p]+1;c[i]=p;}}Max=0;p=0;For(i=1;i<=n;i++)if(b[i]>max)第4页{max=b[i];p=I;}Print(“maxlong=“,max);Print(“result is:”);While(p<>0){print(a[p]);p=c[p];}}◎经过循环，数据的变化a[1] =3; a[2]=18; a[3]=7b[1] =1; b[2]= 1; b[3]=1c[1] =0; c[2]= 0; c[3]=0◎变化结果：a[1] =3; a[2]=18; a[3]=7b[1] =2; b[2]= 1; b[3]=1c[1] =2; c[2]= 0; c[3]= 04.礼物分配问题. 两兄弟Alan 和Bob, 共同分配n个礼物. 每个礼物只能分给其中的一个人,且不能分成两个.每个礼物i 的价值为vi, 为正整数.设 a 和 b 分别表示Alan 和 Bob所收到的礼物的总价值, V=baVnii+=∑=1, 为所有礼物的总价值. 为使两兄弟高兴,我们希望尽可能地均分这些礼物, 即 |a-b| 打到最小。
◎分析：该题目要求使得所分的礼物差值最小；首先，我们知道礼物总价值为V=baVnii+=∑=1；由于要使差值最小，则a与b要最接近于1/2V；故可以设a=1/2V+t，b=1/2V-t；故|a-b|=|（1/2V+t）-（1/2V-t）|=2t;而t=a-1/2V；其中V为已知，则只要a为大于1/2V的最小数即可。
依照次数学思路，我们可以将该方法进行具体话：既是将数组降序排列（这一点很重要，可以用数学分析法进行证明），然后将数组的一个元素赋给a，如果a加上该元素后大于b，则将下一个元素赋给b,循环进行判断直至数组结束。
数学证明过程略◎代码如下：#include<iostream>using namespace std;#define MaxSize 50voidcollat(int n,int v){int a=0;int b=0;第5页int Alan[MaxSize]={0},Bob[MaxSize]={0},r=0,s=0;for(int i=n;i>0;i--){if(a>b){b=b+v*i;Bob[r]=v*i;r++;}else{a=a+v*i;Alan[s]=v*i;s++;}}cout<<"Alan分配到的礼物为："<<endl;for(int j=0;j<r;j++){cout<<Alan[j]<<" ";}cout<<endl;cout<<"Bob分配到的礼物为："<<endl;for(int k=0;k<r;k++){cout<<Bob[k]<<" ";}cout<<endl;cout<<"Alan分配到的礼物总价值为："<<a<<endl;第6页cout<<"Bob分配到的礼物总价值为："<<b<<endl;}int main(){int num,v;cout<<"请输入礼物的个数：";cin>>num;cout<<"请输入单位礼物的价值：";cin>>v;collat(num,v);return 0;}7.键盘输入一个高精度的正整数N, 去掉其中任意S个数字后剩下的数字按左右次序将组成一个新的正整数.编程对给定的N和S,寻找一种方案使得剩下的数字组成的新数最小.◎代码如下：#include<iostream>using namespace std;#define MaxSize 50#define T 10void OrderArray(int N,int S){int array[MaxSize]={0};int i=0,j,a=N,max,tag;while(N>=10){array[i]=N%10;N=N/10;i++; }array[i]=N;for(j=0;j<S;j++){for(int p=i;p>=0;p--)第7页{if(array[p]>array[p-1]){for(int s=p;s<=i;s++)array[s]=array[s+1];i--;break;}}}for(int r=i;r>=0;r--)cout<<array[r];}int main(){OrderArray(12435863,2);return 0;}8.最佳调度问题。