算法分析与设计程序设计题

第三章习题5.编程打印形如以下规律的”X”方阵。1112112212111112121211123321123211233211222112221111(1)甘include<iostream>usingnamespacestd;intmain()(inti=0,j,n;for(i=0;i<7;i++)(for(j=0;j〈7;j++){211111111n=((abs(3-j)-abs(3-i))<=0)+(abs(3~i)<=2)+(abs(3~i)<=1&&abs(3-j)<=2)+(i==3&&abs(3-j)<=1);printf(〃%d〃,n);}printfCXn");}}(2)/*Note：YourchoiceisCIDE*/ttinclude〃Stdio.h〃ttinclude"Conio.h〃intmain(void)(inti;/*层数*/intj;/*i层内每边中行或列的下标*/intm;inta[100][100];int!1；/*方阵的阶*/charch;start:printf(〃\nPleaseenterthenumberofrow：〃)；scanf(〃%d〃,&n);/*逐层摆放数据*/if(n%2==0)for(m=0;m<n/2;m++)for(i=m;i<n-m;i++)for(j=m;j<n-m;j++)a[i];))else(for(m=0;m<(n+1)/2;m++)for(i=m;i<n-m;i++)for(j=m;j<n-m;j++){a[i])}for(i=0;i<n;i++){printf(〃\n〃)；/*打完一行后换行*/printf(〃\n〃)；/*每行之间有一个空行*/for(j=0;j<n;j++)printf(z，%d〃，a[i][j]);)/*可根据用户的需求打印出多个方阵*/printf(^XnPress'Y'tocontinueorothertoexit!\n〃)；ch=getche();if(ch='Y')gotostart;elsereturn(0);getch()；}11.有52张牌，使它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下，正面朝下的翻成正面朝上；第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，以此类推，直到翻的牌超过104张为止。统计最后有几张牌正面朝上，以及它们的位置号。算法设计：定义有100个元素的a数组，它的每个下标变量a[i]视为一张牌，1表示其编号。a[i]=0表示第i张牌正面朝±,a[i]=l表示第i张牌正面朝下。通过算术运算a[i]=l-a[i],模拟翻牌的操作。算法分析：翻牌的主要操作是a[i]=l-a[i]：第一次翻的牌是：2,4,6,8,10……第二次翻的牌是：3,6,9,12,15……第u次翻的牌是：u,2u,3u,4u,设置条件语句while(i*k<=52&&m<=104),使语句在条件内循环执行。问题分析：该问题与狱吏转动狱锁属同类问题。⑴#iiiclude<iostieam>usingnamespacestd;voidmain(){inta[100],i,k,p=0,m=0,u=2;fbr(i=l;i<=52;i++)a[i]=0;//全部正面朝上for(i=u;i<=52;i++)//第u张牌开始(k=l;while(i*k<=52&&m<=104)//i*k为牌编号(a[i*k]=l-a[i*k];k++;m++；}u++;cout«HTherightsideupcardsfbr(i=l;i<=52;i++)if(a[i]=O)(P++;//张数增加}cout«endl;cout«nThenumberofrightsideupcardsis=M«p«endl:}⑵分析：第1次翻的是1,21,31,41,……张牌，是起点为1,公差为1的等差数列。#iiiclude<iostieam>usingnamespacestd;voidmain(){mta[100],i,k=0.p=0,m=0.u=2;fbr(i=l;i<=52;i++)a[i]=0;//全部正面朝上for(i=u;i<=52;i++)//第u张牌开始(fbi(m=0;m<=!04;m++)(fbr(k=i;k<=52;k=k+i)(a[i]=l-a[i]})u++;}cout«HTherightsideupcardsaie:,,«M\nM;fbr(i=l;i<=52;i++)if(a[i]=O)(P++;//张数增加1cout«endl;cout«nThenumberofrightsideupcardsis=M«p«endl;}17.求这样的两个数据：五位数=2X四位数，9个数字互不相同。法分析：四位数的2倍是一个五位数，所以，这个五位数的范围应该在10000-20000之间，并确定这两个数值，通过N%10来拆分这两个数，并存到数组中，如果分解后的数存在就让数组加1,来判断这两个数是否符合条件，符合条件的输出打印，不符合的舍掉。#mclude<iostieam>usingnamespacestd;voidjudgement(iiitxjnty)mta[10];mtm=x;for(mti=0:i<=9;i++)//初始化a[i]=0；while(x)//取出每个位，并统计这个数出现的次数(a[x%10]++；x/=10;)while(y)(a[y%10]++；y/=10;)mtsign=0;for(i=0;i<=9;i++)//g看所有数字出现的次数。if(a[i]>l)//查看到大于1则说明有重复的数字(sign=l;break;)if(sign==0)cout«,r五位数：，vmvv”四位数：”vvm』2v<endl;}intfor(mtn=10000;n<20000;n++)if(n%2=0)judgement(n,iv2);)return0;}第二种方法：#iiicludeHstdafx.hH#iiiclude<iostreain>usingnamespacestd;//求这样的两个数:五位数=2*四位数,9个数字互不相同mtaigc.char*argv[]){intnuni5,num4;fdr(inti=0;i<10;i++)(if(i=l){continue;}fbr(intj=0J<10j++)(程索Qif(j=l||j==i)(contmue、;}for(intk=0;k<10;k++)(if(k=1j|k==i||k=^j)(continue;}fbr(intl=0;l<10;l++)(if(1=1|l==i|l==j|l=k)(continue;)for(intm=0;m<10;m++)(if(m==1||m=i||m==j|m=k||m==l)(contmue;}for(mtn=0;n<10;n-H-)(if(n=11|n=i||n=j||n=k||n==l|ln==m){continue;}fbr(into=0;o<10;o++)(if(o=l|o==i|o==j|o==k||o==l||o==m|o==n)(continue;}for(mtp=0;p<10;p++)(if(p==11|p=i|IpHI|p==k||p=l||p==m||p=n||p=o)(contmue;)num5=10000+1000*i+100*j+10*k+l;num4=1000*m+100*n+l0*o+p;if(nuni5==2*num4)(cout«num5«H=2*H«num4«endl;i-SJ2m.hae)()EBSAE・.2u。。、、(DpnIousW..2P审①pnTJus。祁嫩J^M&S■(zlsgG二)舔*昭聚佃朴舔STM以。<-8岳祁OO。。。XOOO。幽度蜜麟・胃oUJmAo))三f』(S〕B*(〔己B+3史2+h〕3*02)c〔ui〕2(3〕b+u〕3*2+〔切史001)M£p斧pw毛w、、)XUEd(Qhh2洋(osxooswu)))二(gr2*(。。品(oos^u)))二(coROI*(02*(ooswu)))一-(zr2*(osxooswu))))刘(Qhh2/(00淇(。。01专)))二(gr。<(。。品(oos^u)))二(cor2/(02*(00s*u)))一-(zr2/(0sx00swu))))刘(Qhh。0<(。。01专))-一(grO2/OO2WU))--(coHH。0<(000号)--&hh00<(002%u)))右(QR000<u)一一(gH000<u)一一^Hnooo<3--(yoooI/u))J-H二占B*(〔己B+〔MB*OI+m*os)Hu二日++9〉UIOHlu)JOJ)(N++9〉上3H±)35)q++-寸〉。OH『)39)(•<-<++彳〉『-OH-h)3j二ZLocodH口BwE4.UI习题4.一个实数列共有N项，己知:2+d键盘输入N、an、d。、n,输出&分析：根据公式ai=(ai-l-ai+l)/2+d变形得，ai+l=ai-l-2ai+2d,因此该数列的通项公式为：ai=ai-2-2ai-l+2d,己知al,如果能求出a2,这样就可以根据公式递推求出amai=ai-2-2ai-l+2d①=ai-2-2(ai-3-2ai-2+2d)+2d=-2ai-3+5(ai-4-2ai-3+2d)-2d=5ai-4-12ai-3+8d一直迭代下去，直到最后，可以建立ai和al与a2的关系式。设ai=Pia2+Qid+Rial,我们来寻求Pi,Qi,Ri的变化规律。ai=ai-2-2ai-l+2d・.・ai=Pi-2a2+Qi-2d+Ri-2a1-2(Pi-la2十Qi-ld十Ri-lal)+2d=(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-l)a1TOC\o"1-5"\h\z・.・Pi=Pi-2-2Pi-l②Qi=Qi-2-2Qi-l+2③Ri=Ri-2-2Ri-l④显然，P1=OQ1=OR1=1(i=l)P2=1Q2=OR2=O(i=2)将初值Pl、QI、R1和P2、Q2、R2代入②③④可以求出Pn、Qn>Riian=Pna2+Qnd十Rnala2=(an-Qnd+Riia1)/Pn然后根据公式①递推求出am,问题解决。但仔细分析，上述算法有一个明显的缺陷：在求由于在求a2要运用除法，因此会存在实数误差，这个误差在以后递推求an的过程乂不断的扩大。在实际中，当n超过30时，求出的an就明显偏离正确值。显然，这种算法虽简单但不可靠。为了减少误差，我们可设计如下算法：,/ai=Pia2+Qid十Rial=Pi-la3+Qi-ld+Ri-la2=Pi-2a4+Qi-2d+Ri-2a3=Pi-2士kak十Qi-2士kd+Ri-2+kak-1an=Pn-k+2ak+Qn-k+2d+Rii-k+2ak-1ak=(an-Qn-k+2d+Rii-k+2ak-1)/Pn-k+2⑤根据公式⑤，可以顺推a2、a3、...、an。虽然仍然存在实数误差，但由于Pn-k十2递减，因此最后得出的an要比直接利用公式①精确得多。程序如下:#incIude<stdio.h>#incIude<stdIib.h>intmain(){intN=0;doubIed=0.0;doubleA[60]={0.0};intm=0;printf("输入NdA1ANm:\n");scanf("%d%lf”，&N,&d);scanf(M%lf%lf%d",&A[0],&A[N-1],&m);for(inti=0;i<10000;i++){for(intj=1;j<N-1;j++){A[j]=(A[j-1]-A[j+1])/2+d;}}/*输出*/for(intk=0;k<N;k++){printf("A%d=%8.2lf”，k+1,A[k]);if(k+1=m)printf("\t\t//!!!”)；printf("\n")；}return0;}10.利用分治法求一组数据的和。在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。二分法当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的O#incIude<stdio.h>main(){inta[10]={1,3,5,7,9,10,8,6,4,2};inti,maxi二0,max2二0,min1二0,min2二0;for(i二0;i<10;i++){if(a[max1]<a[i])max1=i;if(a[min1]>a[i])min1=i;Iif(max1=0)max2=1;if(mini~0)min2=1;for(i=0;i<10;i++){if(i~max1||i~min1)continue;if(a[max2]<a[i])max2=i;if(a[min2]>a[i])min2=i;Iprintf("max1=%d\nmax2=%d\nmin1=%d\nmin2=%d\n",a[maxi],a[max2],a[mini],a[min2]);I16.N块银币中有一块不合格，己知不合格的银币比正常银币重，现用一天平，请利用它找不合格的银币，并旦用天平的次数最少。方法一：#iiiclude<iostieam>#iiiclude<cniath>usingnamespacestd;hit{hitn;wliile(cm»n){if(n<=0)break;intresult=(int)ceil(log((doiible)n)/log(3.0));cout«MTmies:M«result«endl;}return0;}方法二：#iiiclude<stdlib.h>#iiiclude<stdio.h>hit(mtN;mtt=0;scanf(”％d”,&N);N=N/3;t++;wlule(N)(N=N/3;t++;)pnntf(”％diT,t);system(nPAUSEM);return0;}方法三：/*在最坏情况下求使用天平的最少次数*/#iiiclude<stdlib.h>#iiiclude<stdio.h>hithitt=0,m=l;scanf(”％d”,&N);while(nr<N){m=m*3;t++;)system(HPAUSEn);retuin0;2求3个数的最小公倍数算法1分析：最小公倍数的定义以及用短除法求这3个数的最小公倍数,甚至想到了最大公约数与最小公倍数的换算公式……o其实，与问题相关的每一个经验和思路，都可能是解决这个问题的一种方法，下面就给出用这4种思路进行算法设计的过程。给出三个数x,y,z,求这三个数的最小公倍数c,其中c是每一个数的倍数，且是他们三个的最小的公倍数3个数据最小公倍数的定义为“3个数的公倍数中最小的一个”。直接用最小公倍数的定义进行算法设计，其实就是用蛮力法进行算法设计。按定义将其中一个数逐步从小到大扩大1，2,3,4,5,......自然数的倍数，直到它的某一倍数正好也是其他两个数据的倍数，也就是说，能被其他两个数据整除，这就找到了问题的解。为了提高求解的效率，先选出3个数的最大值，然后对这个最大值从1开始，扩大自然数的倍数，直到这个枳能被全部3个数整除为止，这个枳就是它们的最小公倍数了。Least_conunon_multiplelQIntxl,x2,x3,xO;Print(Hinput3number:n);Input(xLx2,x3);xO=max(xl,x2,x3);1=1;While(l)fj=xO*i;ifljmodxl=0andjmodx2=0andjmodx3=0)break;1=1+1;}print(xl,x2,x3,”Least_common_multiplelis”,j);}niax(z)fif(x>yandx>z)return(x);elseif(y>xandy>z)retuni(y);elsereturn(z);}}11F(n)=£l=ni=l按照算法设计1,只需一重循环就能解决问题算法的时间复杂性为O(n)。算法2分析：先看求解两个数最小公倍数的方法。记两个正整数a、b的最小公倍数是d,最大公约数为Co则最小公倍数d=a*b/co则求解三个数的最小公倍数方法为：先求两个数x、y的最小公倍数，记为s,再求s、z的最小公倍数，这样就求出3个数的最小公倍数了。^include<iostream.h>voidmaiii()intnl4i2,n3;inta,b,c;cm»nl»ii2»n3;a=nl;b=ii2;c=113;while(a!=b)/*利用展转相加法求出nl,n2的最小公倍数，存11)中*/(if(a<b)a+=nl;elseb+=ii2;}wlule(a!=c)/*利用展转相加法求出a,n3的最小公倍数，存a,c中*/{if(a<c)a+=b;elsec+=n3;}cout«c;}jF(n)=£i=l按照算法设计2,只需一重循环就能解决问题算法的时间复杂性为O(n)°函数least_conunon_multipleO的功能就是求几个数的最小公倍数，使用辗转相乘法实现的。算法3设计:用短除法求三个己知数的最小公倍数的过程就是求它们的因数之积，这个因数可能是三个数共有的、两个数共有或一个数独有的三种情况。在手工完成这个问题时，我们的大脑可以判断三个数含有哪些因数，及属于哪种情况。用算法实现就只能利用尝试法了。尝试的范困应该是2―三个数中最大数之间的因数。3)再看例子2,4,8中2是的因数，为避免因数重复计算，一定要用2整除这三个数得到1,2,4。注意到2仍是(1,2,4)的因数，所以在尝试某数是否是三个数的因数时,不是用条件语句if,而是要用循环语句while,以保证将三个数中