计算机算法分析与设计(第四版)习题算法分析部分详解(实验1)

实验参考代码VC++6.0测试通过//算法实验1.1~1.5；任选一道实验、写实验报告，当堂1分；实验报告4分//算法实现题1-1统计数字问题#includeiostream#includecmathusingnamespacestd;intmain(){intcount[10];inti,j,k,L;intn,len,m;while(scanf(%d,&n)!=EOF){m=n;L=ceil(log10(n+1));for(i=0;i10;i++)count[i]=0;for(j=0;jL;j++){len=ceil(log10(m+1));k=m/pow(10.0,len-1);//从高位到低位取各个位数的值for(i=0;i10;i++)//小K*len的数数值0-9出现的次数count[i]+=k*(len-1)*pow(10.0,len-2);//K*n*f(n-1)for(i=0;ik;i++)count[i]+=pow(10.0,len-1);//在高位小于数值K的数出现的次数count[k]+=m-k*pow(10.0,len-1)+1;//在高位数值K的数出现的次数m=m-k*pow(10.0,len-1);//去掉已计算的高位}for(i=0;iL;i++)//去掉前导0；count[0]-=pow(10.0,i);//分别考虑0在高位的情况有到少种for(i=0;i10;i++)printf(%d\n,count[i]);}return0;}//算法实现题1-2字典序问题实验参考代码VC++6.0测试通过#includestdio.h#includestring.hunsignedlongdp[27][11],sum[17],ans;//本代码实现，字符串长度不超过10，可解charstr[11];voidmain(){inti,j,k,len,start;memset(dp,0,sizeof(dp));//为数组分配空间，并初始化为0memset(sum,0,sizeof(sum));for(i=1;i27;i++)dp[i][1]=1;for(j=2;j=10;j++){for(i=27-j;i=1;i--)//dp[i][j]以第i个字母开头的长度为j的单词个数{dp[i][j]+=dp[i+1][j];dp[i][j]+=dp[i+1][j-1];}}for(i=1;i=10;i++)//长度为i是的总个数{for(j=1;j=26;j++){sum[i]+=dp[j][i];}}scanf(%s,str);len=strlen(str);for(i=1;ilen;i++)//如果当前单词的长度为len，计算长度为1到len-1的单词总数ans+=sum[i];start=1;for(j=len;j=1;j--){for(i=start,k=1;k=str[len-j]-('a'+start-1);k++,i++)//考虑打头为1~i-1长度为j的字符串个数ans+=dp[i][j];start=str[len-j]-'a'+2;//打头字符在字典序中下一个字符位置}for(i=0;ilen-1;i++){if(str[i]=str[i+1])ans=-1;}printf(%u\n,ans+1);}实验参考代码VC++6.0测试通过算法实现题1-3最多约数问题方法一：#includeiostreamusingnamespacestd;bool*back;inta,b;intmax=0,maxn;voidmain(){cinab;if(ab){couta=b:errorendl;return;}back=newbool[b+1];for(inti=a;i=b;i++){intcount=0;for(intj=0;j=b;j++)back[j]=false;for(intk=1;k=(i/2+1);k++){if(i%k==0){back[k]=true;back[i/k]=true;}}for(j=0;j=i;j++)if(back[j]){count++;}if(countmax){max=count;maxn=i;}}coutmaxendlmaxnendl;}方法二：#includeiostreamusingnamespacestd;#definemaxMaxconstlongMAXP=100000;实验参考代码VC++6.0测试通过longprim[MAXP];longmax,numb,PCOUNT;//max存放最多约数个数，numb存放约数个数最多的数voidprimes();//用筛选法产生质数存于prim数组中voidsearch(longfrom,longtot,longnum,longlow,longup);intmain(){primes();longl,u;cinlu;if((l==1)&&(u==1)){max=1;numb=1;}else{max=2;numb=l;search(1,1,1,l,u);}coutmaxendlnumbendl;system(pause);return0;}voidprimes(){boolget[MAXP+1];longi;for(i=2;i=MAXP;i++)get[i]=true;for(i=2;i=MAXP;i++)if(get[i]){longj=i+i;while(j=MAXP){get[j]=false;j+=i;}}longii,j;for(ii=2,j=0;ii=MAXP;ii++)if(get[ii])prim[++j]=ii;实验参考代码VC++6.0测试通过PCOUNT=j;}//区间[low,up]上，tot为当前约数最多个数，num为约数个数最多的数，//from表示现在是第几个质数。voidsearch(longfrom,longtot,longnum,longlow,longup){if(num=1)if((totmax)||((tot==max)&&(numnumb))){max=tot;numb=num;}if((low==up)&&(lownum))search(from,tot*2,num*low,1,1);for(longi=from;i=PCOUNT;i++){if(prim[i]up)return;else{longj=prim[i],x=low-1,y=up,n=num,t=tot,m=1;while(true){m++;t+=tot;x/=j;y/=j;if(x==y)break;n*=j;search(i+1,t,n,x+1,y);}m=1m;if(totmax/m)return;}}}实验参考代码VC++6.0测试通过//算法实现题1-4金币列阵问题#includefstream#includeiostreamusingnamespacestd;constintsize=100;intk,n,m,ccount,best;intb0[size+1][size+1],b1[size+1][size+1],b[size+1][size+1];boolfound;voidprint(){for(inti=1;i=n;i++){for(intj=1;j=m;j++)coutb1[i][j];coutendl;}}voidtrans1(intx)//行翻转{for(inti=1;i=m;i++)b1[x][i]=b1[x][i]^1;ccount++;}voidtrans2(intx,inty)//列交换{for(inti=1;i=n;i++)swap(b1[i][x],b1[i][y]);if(x!=y)ccount++;}boolsame(intx,inty){for(inti=1;i=n;i++)if(b0[i][x]!=b1[i][y])returnfalse;returntrue;}voidacpy(inta[size+1][size+1],intb[size+1][size+1]){for(inti=1;i=n;i++)for(intj=1;j=m;j++)a[i][j]=b[i][j];}voidanswer(){实验参考代码VC++6.0测试通过intx,y,j,p;cink;for(inti=1;i=k;i++){cinnm;//n行m列//原状态b0for(x=1;x=n;x++)for(y=1;y=m;y++)cinb0[x][y];//目标状态b1for(x=1;x=n;x++)for(inty=1;y=m;y++)cinb1[x][y];acpy(b,b1);//b1复制到bbest=m+n+1;for(j=1;j=m;j++){acpy(b1,b);ccount=0;trans2(1,j);//列变换intp;for(p=1;p=n;p++)if(b0[p][1]!=b1[p][1])trans1(p);//行变换for(p=1;p=m;p++)//找列相等的（b1的q列和b0的p列相等）{found=false;for(intq=p;q=m;q++)if(same(p,q)){trans2(p,q);found=true;break;}if(!found)break;}if(found&&ccountbest)best=ccount;}if(bestm+n+1)coutbestendl;elsecout-1endl;实验参考代码VC++6.0测试通过}}intmain(){answer();return0;}实验参考代码VC++6.0测试通过//算法实现题1-5最大间隙问题#includeiostreamusingnamespacestd;constintMAX=200001;doublenum[MAX];boolrun(){intn;if(scanf(%d,&n)==EOF)returnfalse;//ctrl+z回车退出inti;doublemax=0.0,min=INT_MAX;//大值初始化为最小，小值初始化为最大for(i=0;in;i++){scanf(%lf,&num[i]);if(num[i]max)max=num[i];if(num[i]min)min=num[i];}int*cnt=newint[n];double*low=newdouble[n];double*high=newdouble[n];for(i=0;in;i++)//初始化桶{cnt[i]=0;low[i]=max;high[i]=min;}doubleave=(max-min)/(n-1);for(i=0;in;i++){inttmp=(int)((num[i]-min)/ave);cnt[tmp]++;//增加桶元素if(num[i]high[tmp])high[tmp]=num[i];//修改桶边界if(num[i]low[tmp])low[tmp]=num[i];}doublet=high[0],res=0.0;for(i=1;in;i++){if(cnt[i]0)//桶中有数字才进行检查，无数字跳过{实验参考代码VC++6.0测试通过doubletmp=low[i]-t;if(tmpres)res=tmp;t=high[i];}}coutresendl;returntrue;}intmain(){while(run());return0;}附：实验（设计）报告参考格式设计一多段图问题的动态规划算法与实现班级学号姓名成绩分一、设计目的1.掌握有向网的成本邻接矩阵表示法；2.掌握多段图问题的动态