算法设计与分析上机题

算法设计与分析上机题第二单元8594有重复元素的排列问题；9718整数因子分解；11088整数划分的扩展问题；17082两个有序数序列中找第k小第三单元8596最长上升子序列；***8601最大长方体问题；10303数字三角；11077最长公共子字符串；11078不能移动的石子合并第四单元8602区间相交问题；11079可以移动的石子合并第五单元8600骑士问题；8603子集和问题；17085工作分配问题；11089多机最佳调度抽选概率：第二三单元，9选3第四五单元，6选2机选，这15题必做题中共抽5题，还要从选做题中抽1题，共呈现6题给考生吗？第二单元8594有重复元素的排列问题；#includeiostream#includestdio.h#includestdlib.husingnamespacestd;inttotal=0;intFindsame(charlist[],intk,inti){intmark=0;intj;for(j=k;ji;j++){if(list[j]==list[i]){mark=1;break;}}if(mark==1){return1;}else{return0;}}//交换元素voidSwap(char&a,char&b){chartemp;temp=a;a=b;b=temp;}//递归全排列voidPerm(charlist[],intk,intm){//产生list[k:m]的所有排列if(k==m)//开始index==结束index{inti;for(i=0;im;i++){//只剩下1个元素printf(%c,list[i]);}printf(\n);total++;}else//还有多个元素带排列，递归产生排列{inti;for(i=k;im;i++){if(Findsame(list,k,i))//判断第i个元素是否在list[k,i－1]中出现过continue;/*intmark=0;for(intj=k;ji;j++){if(list[j]==list[i]){mark=1;break;}}if(1==mark)continue;*/Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}}intmain(){intn;scanf(%d,&n);charlist[n];scanf(%s,list);Perm(list,0,n);printf(%d,total);return0;}9718整数因子分解；#includeiostreamusingnamespacestd;#includestdio.h#includestdlib.hinttotal=0;voidcount(intn){if(n==1){total++;}else{inti;for(i=2;i=n;i++){if(n%i==0){count(n/i);}}}}intmain(){intn;scanf(%d,&n);count(n);printf(%d,total);}11088整数划分的扩展问题；/*题目求：（1）正整数n划分为若干正整数之和，最大加数不超过m的划分数（2）正整数n划分为不超过m个正整数之和的划分数（3）正整数n划分为若干正奇整数之和的划分数（4）正整数n划分为互不相同正整数之和的划分数约定：整数划分无顺序，比如对7划分，认为223和322和232为同一种划分。*/#includeiostream#includestdio.h#includestdlib.husingnamespacestd;intq1(intn,intm)//问题（1）跟问题（2）的计数是相同的{if((n1)||(m1))return0;if((n==1)||(m==1))return1;if(nm)returnq1(n,n);if(n==m)returnq1(n,m-1)+1;returnq1(n,m-1)+q1(n-m,m);}intq2(intn,intm)//问题（3）跟问题（4）的计数是相同的{intg[n+1][n+1],f[n+1][n+1];//f[i][j]表示将i划分为j个奇数的划分数,//g[i][j]表示将i划分为j个偶数的划分数for(inti=0;i=n;i++)//二维数组初始化{for(intj=0;j=n;j++){f[i][j]=g[i][j]=0;}}f[0][0]=1;g[0][0]=1;for(inti=1;i=n;i++){for(intj=1;j=i;j++){g[i][j]=f[i-j][j];f[i][j]=g[i-j][j]+f[i-1][j-1];}}intres=0;for(inti=0;i=n;i++){res+=f[n][i];}returnres;}intmain(){intn,m;inttemp1,temp2;scanf(%d%d,&n,&m);temp1=q1(n,m);temp2=q2(n,m);printf(%d%d%d%d,temp1,temp1,temp2,temp2);}17082两个有序数序列中找第k小#includestdio.h#includestdlib.h#includeiostreamusingnamespacestd;#definemaxn100010inta[maxn],b[maxn],k;intf(intxbeg,intxend,intybeg,intyend){intxMid=(xend+xbeg)/2;//X序列中间位置为xMidintyMid=(yend+ybeg)/2;//序列Y中间位置为yMidinthalflen=xMid-xbeg+yMid-ybeg+2;//X左段和Y左段元素个数合计为halfLenif(ybegyend)returna[xbeg+k-1];//递归边界,X序列为空时，直接返回Y序列的第k小元素。if(xbegxend)returnb[ybeg+k-1];//递归边界,Y序列为空时，直接返回X序列的第k小元素。if(a[xMid]b[yMid]){if(khalflen)returnf(xbeg,xend,ybeg,yMid-1);k=k-(xMid-xbeg+1);returnf(xMid+1,xend,ybeg,yend);}else{if(khalflen)returnf(xbeg,xMid-1,ybeg,yend);k=k-(yMid-ybeg+1);returnf(xbeg,xend,yMid+1,yend);}}intmain(){intm,n,i;scanf(%d%d%d,&m,&n,&k);for(i=0;im;i++)scanf(%d,&a[i]);for(i=0;in;i++)scanf(%d,&b[i]);printf(%d,f(0,m-1,0,n-1));return0;}第三单元8596最长上升子序列；#includeiostream#includestdio.husingnamespacestd;//找出数组中最大值intmaxL(intf[],intn){inttemp=0;for(inti=0;in;i++){if(f[i]temp){temp=f[i];}}returntemp;}//求上升子序列长度intLOSubstr(inta[],intf[],intn){inti,j,k;f[0]=1;for(i=1;in;i++){k=0;for(j=0;ji;j++){//与i之前每一个比较if(a[j]=a[i]&&kf[j]){k=f[j];//k为当前除自己外的子序列长度}}f[i]=k+1;//加上自己}returnmaxL(f,n);}/*7173594861836595123450*/intmain(){while(true){intn;cinn;if(n==0)//退出{break;}inta[n],f[n];for(inti=0;in;i++){//读入序列scanf(%d,&a[i]);}printf(%d\n,LOSubstr(a,f,n));}printf(\n);return0;}8601最大长方体问题；#includeiostream#includestdio.h#includecstringusingnamespacestd;constintN=55;intnum[N][N][N];voidinput(intm,intn,intk){intflag=0;//检测是否全为负数inti,j,l;for(i=0;im;i++){for(j=0;jn;j++){for(l=0;lk;l++){scanf(%d,&num[i][j][l]);if(num[i][j][l]=0){flag=1;}}}}}intcheck(intm,intn,intk){intflag=0;//检测是否全为负数inti,j,l;for(i=0;im;i++){for(j=0;jn;j++){for(l=0;lk;l++){if(num[i][j][l]=0){flag=1;}}}}returnflag;}intmaxSum(inta[],intn){intsum=a[0],b=0;for(inti=0;in;i++){if(b0){b+=a[i];}elseb=a[i];if(sumb)sum=b;}returnsum;}intmaxSum2(inta[N][N],intm,intn){intsum=a[0][0];intb[N],i,j,k;for(i=0;im;i++){memset(b,0,sizeof(b));for(j=i;jm;j++){for(k=0;kn;k++){b[k]+=a[j][k];}intmax=maxSum(b,n);if(maxsum)sum=max;}}returnsum;}intmaxSum3(inta[N][N][N],intm,intn,intk){intb[N][N];inti,j,l;intsum=a[0][0][0],max=0;for(i=0;im;i++){memset(b,0,sizeof(b));for(j=i;jm;j++){for(l=0;ln;l++){for(intt=0;tk;t++)b[l][t]+=a[j][l][t];}max=maxSum2(b,n,k);if(maxsum)sum=max;}}returnsum;}intmain(){intm,n,k;scanf(%d%d%d,&m,&n,&k);if(m=1&&m=50&&n=1&&n=50&&k=1&&k=50){input(m,n,k);intsum=maxSum3(num,m,n,k);if(check(m,n,k)==1){printf(%d,sum);}else{printf(%d,0);}}return0;}10303数字三角；#includeiostream#includestdio.h#includecmath#includestring.husingnamespacestd;intmain(){intn;scanf(%d,&n);intarr[n+1][n+1];intres[n+1][n+1];memset(arr,-1,sizeof(int));memset(res,-1,sizeof(int));for(inti=1;i=n;i++){for(intj=1;j=i;j++){scanf(%d,&arr[i][j]);}}//初始化res结果数组for(inti=1;i=n;i++){res[n][i]=arr[n][i];}for(inti=n