算法与分析平时作业

平时作业1、给定下述二分搜索算法，请判断算法正确性，指犯错误算法产生原因。a)intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}答：正确b)intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m+1;elsel=m-1;}return-1;}答：错误，if(x<a[m])r=m-1;elsel=m+1;c)intBinarySearch(Typea[],constType&x,intl,intr){while(r>l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}答：错误，while(r>=l){2、O(1)空间子数组环卫算法：设a[0:n-1]是一个n维数组，k（1≤k≤n-1）是一个非负整数。试设计一个算法将子数组a[0:k-1]与a[k+1:n-1]换位。要求算法在最坏情况下耗时O(n)，且只用O(1)辅助空间。答：算法分析：当v[k]左边子数组长度等于右边子数组长度时，直接将两个子数组对应元素交换即可当左边子数组长度小于右边子数组长度时，将左边子数组与右边子数组右边等长子数组对换，再对结果递归调用对换函数当右边子数组长度小于左边子数组长度时，将右边子数组与左边子数组左边等长子数组对换，再对结果递归调用对换函数经过分析，可知只需要利用保留元素对换时交换空间即可，空间复杂度为O(1)，子数组对换时时间复杂度不会超出O(n)#include<stdio.h>#include<stdlib.h>#include<vector>#include<iostream>usingnamespacestd;//对应交换vleft_low-left_high和right_low-right_highvoidSwap(vector<int>&v,intleft_low,intleft_high,intright_low,intright_high){inttemp;while(left_low<=left_high){temp=v[left_low];v[left_low]=v[right_low];v[right_low]=temp;++left_low;++right_low;}return;}//分治算法，每次选最小子数组对应交换voidExchange(vector<int>&v,intk,intlow,inthigh){if(low<high){if((k-low+1)==(high-k)){//v[k]左右两个子数组长度相等，直接交换Swap(v,low,k,k+1,high);}elseif((k-low+1)<(high-k)){//v[k]左边子数组长度小于右边子数组，将左边子数组交换到右边子数组右边Swap(v,low,k,low+high-k,high);Exchange(v,k,low,low+high-k-1);}else{//v[k]右边子数组换到左边子数组前部分Swap(v,low,high+low-k-1,k+1,high);Exchange(v,k,high+low-k,high);}}return;}intmain(){vector<int>v;intn,k;while(scanf("%d%d",&n,&k)==2){v.resize(n);for(inti=0;i<n;++i){scanf("%d",&v[i]);}printf("Beforeexchangesubarray:\n");for(intj=0;j<n;++j){printf("%d",v[j]);}printf("\n");Exchange(v,k,0,n-1);printf("Afterexchangesubarray:\n");for(intk=0;k<n;++k){printf("%d",v[k]);}printf("\n");}return0;}3、定义：给定一个自然数n，由n开始依次产生半数集set(n)中元素以下：1）；2）在n左边加上一个自然数，但该自然数不能超出最近添加数二分之一；3）按此规则进行处理，直至不能再添加新自然数为止。比如。其中共有6个元素。半数集问题：对于给定n，求半数集set(n)中元素个数。答：#include<iostream.h>usingnamespacestd;inta[1001];intcomp(intn){inti;for(i=2;i<=n;i++){if(i%2==0)a[i]=a[i/2]+a[i-1];elsea[i]=a[i-1];}returna[n];}intmain(){intn;cout<<"请输入一个小于1000自然数：n=";cin>>n;for(inti=0;i<=n;i++)a[i]=i;if(n<=0||n>1000)cout<<endl<<"输入错误，请注意输入值n范围."<<endl;else{cout<<endl<<"半数集set("<<n<<")中元素个数为：";cout<<comp(n)<<endl;}return0;}4、设计一个算法，找出由n个数组成序列最长单调递增子序列长度。答：#include<iostream.h>

#define

m

10

//快速排序

void

QuickSort(int

R[],int

s,int

t)

{

int

i=s,j=t;

int

tmp;

if(s<t)

{

tmp=R[s];

while(i!=j)

{

while(j>i&&R[j]>=tmp)

j--;

R[i]=R[j];

while(i<j&&R[i]<=tmp)

i++;

R[j]=R[i];

}

R[i]=tmp;

QuickSort(R,s,i-1);

QuickSort(R,i+1,t);

}

}

//找出最长公共子序列

void

LCSLength(int

x[],int

y[],int

n,int

c[m][m],int

b[m][m])

{

int

i,j;

for(i=0;i<n;i++)

{

c[0][i]=0;

c[i][0]=0;

}

for(i=0;i<n;i++)

for(j=0;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,int

*x,int

b[m][m])

{

if(i<0||j<0)

return;

if(b[i][j]==1)

{

LCS(i-1,j-1,x,b);

cout<<x[i]<<"

";

}

else

if(b[i][j]==2)

LCS(i-1,j,x,b);

else

LCS(i,j-1,x,b);

}

void

main()

{

int

x[m],y[m],d;

cout<<"请输入元素个数"<<endl;

cin>>d;

cout<<"请输入元素"<<endl;

for(int

i=0;i<d;i++)

{

cin>>x[i];

y[i]=x[i];

}

int

c[m][m]={0},b[m][m]={0};

QuickSort(x,0,d-1);

LCSLength(x,y,d,c,b);

cout<<"最长单调递增子序列为："<<endl;

LCS(d-1,d-1,x,b);

}5、会场安排问题：假设要在足够多会场里安排一批活动，并希望使用尽可能少会场。设计一个有效贪心算法进行安排。对于给定n个待安排活动，计算使用最少会场个数。每个活动i都有一个开始时间和结束时间，分别表示为b(i)，f(i)。答：#include<iostream>

using

namespace

std;

#define

M

50

//最大活动数struct

Active

{

int

b;//开始时间int

f;//结束时间int

no;//预安排会场号}a[M];

//两元素交换位置void

swap(Active

&a,Active

&b)

{

Active

t;

t=a;

a=b;

b=t;

}

void

main()

{

int

k;

int

i,j;

cout<<"输入待安排活动数:"<<endl;

cin>>k;

cout<<"输入待安排活动开始时间和结束时间:"<<endl;

//输入活动时间for(i=1;i<=k;i++)

{

cin>>a[i].b>>a[i].f;

a[i].no=0;

}

//活动时间排序for(i=1;i<=k;i++)

{

for(j=i;j<=k;j++)

{

if(a[i].b>a[j].b)

swap(a[i],a[j]);

if(a[i].b==a[j].b)

{

if(a[i].f>a[j].f)

swap(a[i],a[j]);

}

}

}

int

sum=1;//使用会场数初始化int

n;

a[1].no=sum;

for(i=2;i<=k;i++)

{

for(n=1;n<i;n++)

{

if(a[n].no!=0&&a[n].f<=a[i].b)

{

a[i].no=a[n].no;

a[n].no=0;//已经安排过活动就不再比较break;

}

}

if(n==i)

{

sum+=1;

a[i].no=sum;

}

}

cout<<"输出最少会场数:\n"<<sum<<endl;

system("pause");

}6、最优分解问题：设n是一个正整数。现要求将n分解为若干个互不相同自然数和，使得这些自然数乘积最大。设计一个算法，得到最优分解方案。分析：我们知道假如a+b=常数，则|a-b|越小，a*b越大。贪心策略：将n分成从2开始连续自然数和。假如最终剩下一个数，将此数在后项优先方式下均匀地分给前面各项。答：voiddicomp(intn,int[]a){intk=1;if(n<3){a[1]=0;return;}if(n<5){a[k]=1;a[++k]=n-1;return;}a[1]=2;n-=2;while(n>a[k]){k++;a[k]=a[k-1]+1;n-=a[k];}if(n==a[k]){a[k]++;n--;}for(inti=0;i<n;i++)a[k-i]++;}7、子集和问题：设是n个正整数集合，c是一个正整数。那么是否存在S一个子集S1，使得子集中元素之和等于c，即。答：#include<stdio.h>

int

n,c;

int

a[100];

int

current[100];

//存放当前选择情况

int

best[100];

//存放最终选择子集合，best[i]=1，表示包含，反之即不包含。int

d=1;

//判断有没有满足情况

int

d2=0;

//是否已经选出子集和

void

Back(int

m,int

count);

int

main()

{

int

i,j;

scanf("%d

%d",&n,&c);

for(i=0;i<n;i++)

{

scanf("%d",&a[i]);

current[i]=best[i]=0;

}

Back(0,0);

if(d)

printf("no

solution\n");

for(j=0;j<n;j++)

//输出满足情况子集和

{

if(best[j]==1)

printf("%d\t\t",a[j]);

}

}

void

Back(int

m,int

count)

{ int

k;

if(m>n)return;

if(count==c)

{

d=0;

//有满足子集和if(d2)

return

0;

for(k=0;k<=m;k++)

best[k]=current[k];

d2=1;

return

0;

}

else

{

current[m]=1;

//选入子集和count+=a[m];

Back(m+1,count);

current[m]=0;

//不选入子集和

count=count-a[m];

Back(m+1,count);

}

}

8、设序列是序列和最长公共子序列。请说明最长公共子序列具备最优子结构性质。设c[i][j]统计序列i和最长公共子序列长度。由最长公共子序列问题最优子结构性质建立子问题最优值c[i][j]递归关系。写出寻找最长公共子序列算法。答：最长公共子序列问题具备最优子结构性质：1、若xm=yn，则zk=xm=yn，且Z[k-1]是X[m-1]和Y[n-1]最长公共子序列2、若xm!=yn，且zk!=xm,则Z是X[m-1]和Y最长公共子序列3、若xm!=yn,且zk!=yn,则Z是Y[n-1]和X最长公共子序列由性质导出子问题递归结构：当i=0,j=0时,c[i][j]=0当i,j>0xi=yi时,c[i][j]=c[i-1][j-1]+1当i,j>0xi!=yi时,c[i][j]=max{c[i][j-1],c[i-1][j]}publicclassLSC{privateint[][]c,b;privateintm,n;privatechar[]A,B;publicLSC(char[]A,char[]B){this.A=A;this.B=B;m=A.length;n=B.length;c=newint[m+1][n+1];b=newint[m+1][n+1];for(int

i=0;i<n+1;i++)

{

c[0][i]=0;

}

for(int

j=0;j<m+1;j++)

{

c[j][0]=0;

}

}

publicLSC(){}publicintLSCLength(){for(inti=1;i<m+1;i++){for(intj=1;j<n+1;j++){/**假如A[i-1]和Ｂ[j-1]是相等话*/if(A[i-1]==B[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]='0';}/**情况１*/elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]='1';}/**情况２*/else{c[i][j]=c[i][j-1];b[i][j]='2';}}}returnc[m][n];}publicvoidprint(inti,intj){ if(i<=0||j<=0){return;}elseif(b[i][j]=='0'){print(i-1,j-1);System.out.print(A[i-1]);}elseif(b[i][j]=='1'){print(i-1,j);}else{print(i,j-1);}}publicintLSCLength2(inti,intj){if(i<0||j<0){return0;}else{if(A[i]==B[j]){return1+LSCLength2(i-1,j-1);}else{inta1=LSCLength2(i,j-1);inta2=LSCLength2(i-1,j);returna1>a2?a1:a2;}}}publicstaticvoidmain(String[]args){char[]A={'g','f','d','a','s','d','a','c'};char[]B={'g','c','f','a','t','0','c','c'};LSClsc=newLSC(A,B);System.out.println(lsc.LSCLength2(7,7));}}9、记矩阵连乘积。确定计算A[1:n]最优计算次序，使得所需数乘次数最少。1、说明矩阵连乘计算次序问题最优解包含着其子问题最优解，即最优子结构性质。2、该问题具备子问题重合性质。3、说明采取动态规划方法能够处理该问题。4、设计该算法，分析算法复杂性。答：计算A[i:j]最优次序所包含计算矩阵子链A[i:k]和A[k+1:j]次序也是最优。设计算A[i:j]，1≤i≤j≤n，所需要最少数乘次数m[i,j]，则原问题最优值为m[1,n]当i=j时，A[i:j]=Ai，无需计算，所以，m[i,j]=0，i=1,2,…,n当i<j时，利用最优子结构性质计算m[i,j].设A[i:j]最优次序在Ak和Ak＋1之间断开，则其中Ai维数为pi-1×pjk位置只有j-i种可能,{i,i+1,…,j-1}，其中使计算量最小那个位置为最优解，数乘次数m[i,j]最小值为问题最优值能够递归地定义m[i,j]为：将最优值m[ij]对应断开位置记为s[ij]，则可递归由s[ij]结构出对应最优解对于1≤i≤j≤n不一样有序对(i,j)对应于不一样子问题。所以，不一样子问题个数最多只有由此可见，在递归计算时，许多子问题被重复计算数次。这也是该问题可用动态规划算法求解又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上方式进行计算。在计算过程中，保留已处理子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而防止大量重复计算最终得到多项式时间算法matrixChain已经统计了结构最优解所需全部信息。从s[1][n]可知，计算A[1:n]最优加括号方式为(A[1:s[1][n]])(A[s[1][n]+1:n])计算A[1:s[1][n]]最优加括号方式为(A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][n]])10、考虑分数背包问题，定义以下：给出n个大小为s1,s2,…,sn,价值为v1,v2,…,vn物品，并设背包容量为C,要找到非负实数x1,x2,…,xn,使和在约束下最大。写出求解问题贪心算法，估量算法时间复杂性。答：从问题某一初始解出发；while

能朝给定