《算法设计与分析实用教程》习题参考解答.doc

PAGE PAGE 33 《算法设计与分析实用教程》参考解答 （各习题的算法设计与数据测试仅供参考） 习题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——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2） 算法描述 // 两数若干次加减结果为1的数学游戏 #include stdio.h void main() {long a,b,d,n,x,y; printf( 请输入整数a,b: ); scanf(%ld,%ld,a,b); if(a%2==0 b%2==0) { printf( -1\n);return;} n=0; while(1) { n++; for(x=1;x=n;x++) { y=n+1-x;d=x*a-y*b; if(d==1 || d==-1) // 满足加减结果为1 { printf( n=%ld\n,n);return;} } } } 请输入整数a,b: 2012,19 961 请输入整数a,b: 101,2013 606 1-2 埃及分数式算法描述 分母为整数分子为“1”的分数称埃及分数，试把真分数a/b分解为若干个分母不为b的埃及分数之和。 （1） 寻找并输出小于a/b的最大埃及分数1/c； （2） 若c900000000，则退出； （3） 若c≤900000000，把差a/b-1/c整理为分数a/b，若a/b为埃及分数，则输出后结束。 （4） 若a/b不为埃及分数，则继续（1）、（2）、（3）。 试描述以上算法。 解：设 (这里int(x)表示取正数x的整数)，注意到，有 算法描述：令c=d+1，则 input (a,b) while(1) {c=int(b/a)+1; if(c900000000) 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++) m=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) {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 \n,a);break;} } 解：因