资源描述：
《《算法设计与分析实用教程》习题参考解答.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《算法设计与分析实用教程》参考解答1-1加减得1的数学游戏西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。（1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。为了求n的最小值，令n从1开始递增，x在1—
2、—n中取值，y=n+1-x：检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。（2）算法描述//两数若干次加减结果为1的数学游戏#includevoidmain(){longa,b,d,n,x,y;printf("请输入整数a,b:");scanf("%ld,%ld",&a,&b);if(a%2==0&&b%2==0){printf("-1");return;}n=0;while(1){n++;for(x=1;x<=n;x++){y=n+1-x;d=x*a-y*b;if(d==1
3、
4、d==-1)//满足加减结果为1{printf("
5、n=%ld",n);return;}}}}请输入整数a,b:2012,19961请输入整数a,b:101,20136061161-2埃及分数式算法描述分母为整数分子为“1”的分数称埃及分数，试把真分数a/b分解为若干个分母不为b的埃及分数之和。（1）寻找并输出小于a/b的最大埃及分数1/c；（2）若c>900000000，则退出；（3）若c≤900000000，把差a/b-1/c整理为分数a/b，若a/b为埃及分数，则输出后结束。（4）若a/b不为埃及分数，则继续（1）、（2）、（3）。试描述以上算法。解：设(这里int(x)表示取正数x的整数)，注意到，有算法描述：令c=
6、d+1，则input(a,b)while(1){c=int(b/a)+1;if(c>900000000)return;else{print(1/c+);a=a*c-b;b=b*c;//a,b迭代，为选择下一个分母作准备if(a==1){print(1/b);return;}}}1-3求解时间复杂度求出以下程序段所代表算法的时间复杂度。（1）m=0;for(k=1;k<=n;k++)for(j=k;j>=1;j--)m=m+j;解：因s=1+2+…+n=n(n+1)/2时间复杂度为O(n2)。（2）m=0; for(k=1;k<=n;k++) for(j=1;j<=k/2;j++
7、)116m=m+j;解：设n=2u+1，语句m=m+1的执行频数为s=1+1+2+2+3+3+…+u+u=u(u+1)=(n−1)(n+1)/4设n=2u，语句m=m+1的执行频数为s=1+1+2+2+3+3+…+u=u2=n2/4时间复杂度为O(n2)。（3）t=1;m=0;for(k=1;k<=n;k++){t=t*k;for(j=1;j<=k*t;j++)m=m+j;}解：因s=1+2×2!+3×3!+…+n×n!=(n+1)!−1时间复杂度为O((n+1)!).（4）for(a=1;a<=n;a++){s=0;for(b=a*100−1;b>=a*100−99;b−=2
8、){for(x=0,k=1;k<=sqrt(b);k+=2)if(b%k==0){x=1;break;}s=s+x;}if(s==50)printf("%ld",a);break;}}解：因a循环n次；对每一个a,b循环50次；对每一个b,k循环次。因而k循环体的执行次数s满足算法的时间复杂度为O()。1-4时间复杂度的一个性质若p(n)是n的多项式，证明：O(log(p(n)))=O(logn)。证：设m为正整数，p(n)=a1×nm+a2×nm-1+…+am×n，取常数c>ma1+(m-1)a2+…+am,则log(p(n))=ma1×logn+(m-1)a2×logn
9、+…=(ma1+(m-1)a2+…)×logn
