《算法设计与分析实用教程》参考解答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,19961请输入整数a,b: 101,20136061-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 ab d = (这里int(x)表示取正数x 的整数)，注意到1+<<d ab d ，有)1()1(11+-+++=d b bd a d ba算法描述：令c=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(n 2)。

（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=u 2=n 2/4时间复杂度为O(n 2)。

（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;} }解：因a 循环n 次；对每一个a,b 循环50次；对每一个b,k2次。

因而k 循环体的执行次数s 满足250(1250250s L L ＜＜＜算法的时间复杂度为O(n n )。

1-4 时间复杂度的一个性质若p(n)是n 的多项式，证明：O(log(p(n)))=O(logn)。

证：设m 为正整数，p(n)=a1×n m +a2×n m-1+…+am ×n ， 取常数c>ma1+(m-1)a2+…+am, 则log(p(n))=ma1×logn+(m-1)a2×logn+…=(ma1+(m-1)a2+…)×logn <clogn因而有O(log(p(n)))=O(logn)。

1-5 统计n!中数字“0”的个数修改1.3.2计算n!的算法，统计并输出n!中数字“0”的个数及其尾部连续“0”的个数（n<10000）。

解：计算n!完成后，在j（1——m）循环过if(a[j]==0) p++;统计n!中数字“0”的个数p。

应用q=1; while(a[q]==0) q++;统计尾部连续“0”的个数q-1。

// 统计n!中0的个数及尾部连续0的个数（n<10000）#include<stdio.h>#include<math.h>void main(){ int g,j,k,m,n,p,q,t,a[40000];double s;printf(" 请输入正整数n(n<10000): ");scanf("%d",&n); // 输入ns=0;for(k=2;k<=n;k++)s+=log10(k); // 对数累加确定n!的位数mm=(int)s+1;for(k=1;k<=m;k++)a[k]=0; // 数组清零a[1]=1;g=0;for(k=2;k<=n;k++)for(j=1;j<=m;j++){ t=a[j]*k+g; // 数组累乘并进位a[j]=t%10;g=t/10;}p=0;for(j=m;j>=1;j--)if(a[j]==0) p++; // p统计n!中0的个数q=1;while(a[q]==0) q++; // q尾部连续0的个数printf(" p=%d,q=%d\n",p,q-1); // 输出结果}数据测试：请输入正整数n(n<10000): 1000p=472,q=249请输入正整数n(n<10000): 2013p=1032,q=5011-6 构建斜折对称方阵图1-4是一个7阶斜折对称方阵，试观察斜折对称方阵的构造特点，总结归纳其构造规律，设计并输出n（奇数）阶斜折对称方阵。

图1-4 7阶斜折对称方阵（1）构造规律与赋值要点对n阶方阵中的每一个元素都必须赋值，但不可能逐行逐列地一个个赋值，有必要分析方阵的构造特点，分块或分片实施。

斜折对称方阵的构造特点：两对角线上均为“0”，依两对角线把方阵分为4个区域，每一区域表现为同数字依附两对角线折叠对称，至上下左右正中元素为n/2。

同样设置2维a[n][n]数组存储方阵中元素，行号为i，列号为j，a[i][j]为第i行第j 列元素。

令m=(n+1)/2, 按m把方阵分成的4个小矩形区如图1-5所示。

图1-5 按m分成的4个小矩形注意到方阵的主对角线（从左上至右下）上元素为：i=j，则左上区与右下区依主对角线赋值：a[i][j]=abs(i-j);注意到方阵的次对角线（从右上至左下）上元素为：i+j＝n+1，则右上区与左下区依次对角线赋值：a[i][j]=abs(i+j-n-1);(2) 程序设计// 斜折对称方阵#include <math.h>#include <stdio.h>void main(){int i,j,m,n,a[30][30];printf(" 请确定方阵阶数(奇数)n: "); scanf("%d",&n);if(n%2==0){ printf(" 请输入奇数！");return;}m=(n+1)/2;for(i=1;i<=n;i++)for(j=1;j<=n;j++){ if(i<=m && j<=m || i>m && j>m)a[i][j]=abs(i-j); // 方阵左上部与右下部元素赋值if(i<=m && j>m || i>m && j<=m)a[i][j]=abs(i+j-n-1); // 方阵右上部与左下部元素赋值}printf(" %d阶对称方阵为:\n",n);for(i=1;i<=n;i++){ for(j=1;j<=n;j++) // 输出对称方阵printf("%3d",a[i][j]);printf("\n");}}1-7 构建横竖折对称方阵试观察图1-6所示的横竖折对称方阵的构造特点，总结归纳其构造规律，设计并输出n （奇数）阶横竖折对称方阵。

图1-6 7阶横竖折对称方阵（1）构造规律与赋值要点观察横竖折对称方阵的构造特点，方阵横向与纵向正中有一对称轴。

两对称轴所分4个小矩形区域表现为同数字横竖折递减，至4顶角元素为1。

设阶数n（奇数）从键盘输入，对称轴为m=(n+1)/2。

设置2维a数组存储方阵中元素，行号为i，列号为j，a[i][j]为第i行第j列元素。

可知主对角线（从左上至右下）有：i=j；次对角线（从右上至左下）有：i+j=n+1。

按两条对角线把方阵分成上部、左部、右部与下部4个区,如图1-7所示。

图1-7 对角线分成的4个区对角线上元素可归纳到上、下部，即上、下部区域带等号即可。

上、下部按列号j的函数m-abs(m-j)赋值：if(i+j<=n+1 && i<=j || i+j>=n+1 && i>=j)a[i][j]=m-abs(m-j);左、右部按行号i的函数m-abs(m-i)赋值：if(i+j<n+1 && i>j || i+j>n+1 && i<j)a[i][j]=m-abs(m-i);（2）算法描述// 横竖折对称方阵#include <stdio.h> // 调用2个头文件#include <math.h>void main(){int i,j,m,n,a[30][30]; // 定义数据结构printf(" 请确定方阵阶数(奇数)n: "); scanf("%d",&n);if(n%2==0){printf(" 请输入奇数！");return;}m=(n+1)/2;for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(i+j<=n+1 && i<=j || i+j>=n+1 && i>=j)a[i][j]=m-abs(m-j); // 方阵上、下部元素赋值if(i+j<n+1 && i>j || i+j>n+1 && i<j)a[i][j]=m-abs(m-i); // 方阵左、右部元素赋值}printf(" %d阶对称方阵为:\n",n);for(i=1;i<=n;i++){ for(j=1;j<=n;j++) // 输出对称方阵printf("%3d",a[i][j]);printf("\n");}}1-8 应用定义求最大公约与最小公倍数应用定义求n个正整数的最大公约数与最小公倍数, 给出算法设计。