《计算机常用算法与程序设计案例教程》习题解答

《计算机常用算法与程序设计案例教程》

习题解答提要

习题1

1-1 分数分解算法描述

把真分数a/b分解为若干个分母为整数分子为“1”的埃及分数之和： （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）。 试描述以上算法。

解：设d?int(b) (这里int(x)表示取正数x的整数)，注意到d?b?d?1，有

aa a?1?a(d?1)?bbd?1b(d?1)

算法描述：令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-2 求出以下程序段所代表算法的时间复杂度 （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

2

时间复杂度为O(n)。

（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的执行频数为

22

s=1+1+2+2+3+3+…+u=u=n/4

2

时间复杂度为O(n)。

（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(\}

解：因a循环n次；对每一个a,b循环50次；对每一个b,k循环b/2次。因而k循环体的执行次数s满足

s＜25(99?199??100n?1)＜250(1?2??n)4n?3＜250?n＜250nn6

时间复杂度为O(nn)。

1-3 若p(n)是n的多项式，证明：O(log(p(n)))=O(logn)。

mm-1

证：设m为正整数，p(n)=a1×n+a2×n+…+am×n， 取常数c>ma1+(m-1)a2+…+am, 则

log(p(n))=ma1×logn+(m-1)a2×logn+…=(ma1+(m-1)a2+…)×logn

因而有O(log(p(n)))=O(logn)。

1-4 构建对称方阵

观察图1-5所示的7阶对称方阵：

图1-5 7阶对称方阵

试构造并输出以上n阶对称方阵。

解：这是一道培养与锻炼我们的观察能力与归纳能力的案例，一个一个元素枚举赋值显然行不通，必须全局着眼，分区域归纳其构造特点，分区域枚举赋值。 （1） 设计要点

设方阵中元素的行号为i，列号为j。

可知主对角线：i=j；次对角线：i+j=n+1。两对角线赋值“0”。

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

图1-6 对角线分成的4个区

上部按行号i赋值；下部按行号函数n+1-i赋值。 左部按列号j赋值；右部按列号函数n+1-j赋值。 （2） 程序实现

#include void main()

{int i,j,n,a[30][30];

printf(\请确定方阵阶数n: \ scanf(\

for(i=1;i<=n;i++) for(j=1;j<=n;j++)

{if(i==j || i+j==n+1)

a[i][j]=0; // 方阵对角线元素赋值 if(i+j

a[i][j]=i; // 方阵上部元素赋值 if(i+jj)

a[i][j]=j; // 方阵左部元素赋值 if(i+j>n+1 && i>j)

a[i][j]=n+1-i; // 方阵下部元素赋值 if(i+j>n+1 && i

a[i][j]=n+1-j; // 方阵右部元素赋值 }

printf(\阶对称方阵为:\\n\ for(i=1;i<=n;i++)

{ for(j=1;j<=n;j++) // 输出对称方阵 printf(\ printf(\ } }

1-5 据例1-2的算法，写出求解n个“1”组成的整数能被2011整除的程序。 修改程序，求出 n至少为多大时，n个“1”组成的整数能被2013整除？ 解：程序为

#include void main() { int a,c,p,n; p=2011;

c=1111;n=4; // 变量c与n赋初值 while(c!=0) // 循环模拟整数竖式除法 { a=c*10+1; c=a%p;

n=n+1; // 每试商一位n增1 }

printf(\由 %d 个1组成的整数能被 %d 整除。\\n\}

习题2

2-1 解不等式

设n为正整数，解不等式

2010?1?111?????2011 1?1/21?1/2?1/31?1/2???1/n解：上下限一般为键盘输入的a,b。

// 解不等式: a<1+1/(1+1/2)+...+1/(1+1/2+...+1/n) #include void main()

{ long a,b,c,d,i; double ts,s;

printf(\请输入a,b: \ scanf(\ i=0;ts=0;s=0; while(s

ts=ts+(double)1/i; s=s+1/ts; } c=i;

while(s

ts=ts+(double)1/i; s=s+1/ts;

} d=i-1;

printf(\满足不等式的正整数n为: %ld≤n≤%ld \\n\}

2-2 韩信点兵

韩信在点兵的时候，为了知道有多少个兵，同时又能保住军事机密，便让士兵排队报数。 按从1至5报数,记下最末一个士兵报的数为1； 再按从1至6报数,记下最末一个士兵报的数为5； 再按1至7报数,记下最末一个报的数为4； 最后按1至11报数,最末一个士兵报的数为10。

你知道韩信至少有多少兵?

1. 求解要点

设兵数为x，则x满足下述的同余方程组:

x=5y+1 即 x=1 (mod 5) x=6z+5 x=5 (mod 6) x=7u+4 x=4 (mod 7) x=11v+10 x=10 (mod 11)

其中y,z,u,v都为正整数。试求满足以上方程组的最小正整数x。

应用枚举可得到至少的兵数。x从1开始递增1取值枚举当然可以，但不必要。事实上枚举次数可联系问题的具体实际大大缩减。

（1) 注意到x除11余10，于是可设置x从21开始，以步长11递增。此时，只要判别前三个条件即可。

（2) 由以上第2，4两方程知x+1为11的倍数，也为6的倍数。而11与6互素，因而x+1必为66的倍数。于是取x=65开始，以步长66递增。此时,只要判别x%5=1与x%7=4 两个条件即可。

这样可算得满足条件的最小整数x即点兵的数量。 2. 程序实现 // 韩信点兵 #include void main() { long int x; x=65; while(1) { x=x+66;

if(x%5==1 && x%7==4)

{ printf(\至少有兵: %ld 个。\ break; } } }

2-3 分解质因数

对给定区间[m,n]的正整数分解质因数,?每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。

例如, 2012=2*2*503, 2011=(素数!)。

解：对区间中的每一个整数i(b=i)，用k(2——sqrt(i))试商： 若不能整除，说明该数k不是b的因数，k增1后继续试商。

若能整除，说明该数k是b的因数，打印输出\；b除以k的商赋给b(b=b/k)?后继

续用k试商(注意，可能有多个k因数)，直至不能整除，k增1后继续试商。

按上述从小至大试商确定的因数显然为质因数。

如果有大于sqrt(n)的因数(至多一个!)?,在试商循环结束后要注意补上，不要遗失。 如果整个试商后b的值没有任何缩减，仍为原待分解数n，说明n是素数，作素数说明标记。

若k是b的因数，按格式输出，然后b=b/k后继续试商k。 若k不是b的因数，则k增1后继续。

若上述试商完成后1

// 质因数分解乘积形式 #include\#include void main()

{long int b,i,k,m,n,w=0;

printf(\中整数分解质因数（乘积形式）.\\n\printf(\请输入m,n:\scanf(\

for(i=m;i<=n;i++) // i为待分解的整数 { printf(\ b=i;k=2;

while(k<=sqrt(i)) // k为试商因数 {if(b%k==0) {b=b/k;

if(b>1)

{printf(\

continue; // k为质因数,返回再试 }

if(b==1) printf(\}

k++;

}

if(b>1 && b

printf(\输出大于i平方根的因数 if(b==i)

{printf(\素数!)\\n\表示i无质因数 } }

2-4 基于素数代数和的最大最小

定义和：

s(n)?1?3?3?5?5?7?7?9???(2n?1)?(2n?1)

(和式中第k项±(2k-1)*(2k+1)的符号识别：当(2k-1)与(2k+1)中至少有一个素数，取“+”；其余取“-”。例如和式中第13项取“-”，即为-25*27。)

1) 求s(2011)。

2) 设1<=n<=2011，当n为多大时，s(n)最大。 3) 设1<=n<=2011，当n为多大时，s(n)最小。

解：代数和式中各项的符号并不是简单的正负相间，而是随着构成素数而改变。因而在求和之前应用“试商判别法”对第k个奇数2k-1是否为素数进行标注：

若2k-1为素数，标注a[k]=1； 否则，若2k-1不是素数，a[k]=0。 设置k循环（1——n），循环中分别情况求和：

若a[k]+a[k+1]>=1，即(2k-1)与(2k+1)中至少有一个素数，实施“+”； 否则，若a[k]+a[k+1]==0，即(2k-1)与(2k+1)中没有素数，实施“-”。 同时，设置最大值变量smax，最小值变量smin。

在循环中，每计算一个和值s，与smax比较确定最大值，同时记录此时的项数k1；与smin比较确定最小值，同时记录此时的项数k2。

// 基于素数的整数和 #include #include void main()

{ int t,j,n,k,k1,k2,a[3000]; long s,smax,smin; printf(\请输入整数n: \ scanf(\

for(k=1;k<=n+1;k++) a[k]=0; for(k=2;k<=n+1;k++)

{for(t=0,j=3;j<=sqrt(2*k-1);j+=2) if((2*k-1)%j==0) {t=1;break;}

if(t==0) a[k]=1; // 标记第k个奇数2k-1为素数 }

s=3;smax=0;smin=s; for(k=2;k<=n;k++)

{if(a[k]+a[k+1]>=1)

s+=(2*k-1)*(2*k+1); // 实施代数和

else

s-=(2*k-1)*(2*k+1);

if(s>smax){smax=s;k1=k;} // 比较求最大值smax if(s

}

printf(\

printf(\当k=%d时s有最大值: %ld\\n\printf(\当k=%d时s有最小值: %ld\\n\}

2-5 特定数字组成的平方数

用数字2,3,5,6,7,8,9可组成多少个没有重复数字的7位平方数？ 解：求出最小7位数的平方根b, 最大7位数的平方根c.

用a枚举[b，c]中的所有整数，计算d=a*a，这样确保所求平方数在d中。 设置f数组统计d中各个数字的个数。如果f[3]=2，即平方数d中有2个“3”。 检测若f[k]>1(k=0——9)，说明d中存在有重复数字，返回。

在不存在重复数字的情形下，检测若f[0]+f[1]+f[4]=0，说明7位平方数d中没有数字“0”,“1”,“4”,d满足题意要求，打印输出。

// 组成没有重复数字的7位平方数 #include #include void main()

{int k,m,n,t,f[10]; long a,b,c,d,w; n=0;

b=sqrt(2356789);c=sqrt(9876532); for(a=b;a<=c;a++)

{d=a*a; w=d; // 确保d为平方数 for(k=0;k<=9;k++) f[k]=0; while(w>0)

{ m=w;f[m]++;w=w/10;} for(t=0,k=1;k<=9;k++)

if(f[k]>1) t=1; // 测试三个平方数是否有重复数字

if(t==0 && f[0]+f[1]+f[4]==0) // 测试平方数中没有数字0,1,4 {n++;

printf(\

printf(\ } }

printf(\共可组成%d个没有重复数字的7位平方数.\\n\}

2-6 写出例2-2中对称方阵的完整程序，并运行程序。 对称方阵程序：

#include void main()

{int i,j,n,a[30][30];

printf(\请确定方阵阶数n: \ scanf(\

for(i=1;i<=n;i++) for(j=1;j<=n;j++)

{if(i+j<=n+1 && i<=j)

a[i][j]=(n+1)/2-i+1; // 方阵上部元素赋值 if(i+jj)

a[i][j]=(n+1)/2-j+1; // 方阵左部元素赋值 if(i+j>=n+1 && i>=j)

a[i][j]=i-n/2; // 方阵下部元素赋值 if(i+j>n+1 && i

a[i][j]=j-n/2; // 方阵右部元素赋值 }

printf(\阶对称方阵为:\\n\ for(i=1;i<=n;i++)

{ for(j=1;j<=n;j++) // 输出对称方阵 printf(\ printf(\ } }

2-7 四则运算式

把数字1,2,...,9这9个数字填入以下含加减乘除的综合运算式中的9个□中,?使得该式成立

□□×□+□□□÷□-□□=0

要求数字1,2,...,9这9个数字在各式中都出现一次且只出现一次，且约定数字“1”不出现在数式的一位数中（即排除各式中的各个1位数为1这一平凡情形）。

（1） 求解要点

设式右的5个整数从左至右分别为a,b,c,d,e,其中a,e为二位整数，b,d为大于1的一位整数，c为三位整数。设置a,b,c,d循环，对每一组a,b,c,d,计算e=a*b+c/d。若其中的c/d非整数，或所得e非二位数，则返回。

然后分别对5个整数进行数字分离，设置f数组对5个整数分离的共9个数字进行统计，f(x)即为数字x(1—9)的个数。

若某一f(x)不为1，不满足数字1,2,...,9这九个数字都出现一次且只出现一次，标记t=1.

若所有f(x)全为1，满足数字1,2,...,9这九个数字都出现一次且只出现一次，保持标记t=0, 则输出所得的完美综合运算式。

设置n统计解的个数。 （2） 程序实现 // 四则运算式 #include void main()

{int x,y,t,k,a,b,c,d,e,n=0; int m[6],f[11]; for(a=12;a<=98;a++) for(b=2;b<=9;b++)

for(c=123;c<=987;c++) // 对a,b,c,d 实施枚举 for(d=2;d<=9;d++) {x=c/d;e=a*b+x;

if(c!=x*d || e>100) continue;

m[1]=a;m[2]=c;m[3]=e;m[4]=b;m[5]=d; for(x=0;x<=9;x++) f[x]=0; for(k=1;k<=5;k++) {y=m[k]; while(y>0)

{x=y;f[x]=f[x]+1;

y=(y-x)/10; // 分离数字f数组统计 }

}

for(t=0,x=1;x<=9;x++) if(f[x]!=1)

{t=1; break;} // 检验数字0--9各只出现一次 if(t==0) // 输出一个解，用n统计个数 {n++;

printf(\

} }

printf(\ }

2-8 合数世纪探求

定义一个世纪的100个年号中不存在一个素数，即100个年号全为合数的世纪称为合数世纪。

探索最早的合数世纪。 （1） 设计要点

应用穷举搜索，设置a世纪的的50个奇数年号(偶数年号无疑均为合数)为b，用k试商判别b是否为素数，用变量s统计这50个奇数中的合数的个数。

对于a世纪，若s=50，即50个奇数都为合数，找到a世纪为最早的合数世纪，打印输出后退出循环结束。

（2） 合数世纪程序设计 // 合数世纪探求 #include #include void main()

{long a,b,k; int s,x; a=1;

while (1)

{a++;s=0; // 检验a世纪

for(b=a*100-99;b<=a*100-1;b+=2) // 穷举a世纪奇数年号b {x=0;

for(k=3;k<=sqrt(b);k+=2) if(b%k==0)

{x=1;break;}

if(x==0)break; // 当前为非合数世纪时，跳出循环进行下世纪的探求 s=s+x; // 年号b为合数时，x=1，s增1 }

if(s==50) // s=50，即50个奇数均为合数 { printf(\最早出现的合数世纪为 %ld 世纪!\\n\

break; }

} }

2-9 最小连续n个合数 试求出最小的连续n个合数。（其中n是键盘输入的任意正整数。）

（1）设计要点

求出区间[c,d]内的所有素数(区间起始数c可由小到大递增)，检验其中每相邻两素数之

差。若某相邻的两素数m,f之差大于n，即m-f>n，则区间[f+1,f+n]中的n个数为最小的连续n个合数。

应用试商法求指定区间[c,d](约定起始数c=3，d=c+10000)上的所有素数。求出该区间内的一个素数m，设前一个素数为f,?判别：

若m-f>n，则输出结果[f+1,f+n]后结束； 否则，作赋值f=m，为求下一个素数作准备。

如果在区间[c,d]中没有满足条件的解，则作赋值：c=d+2，d=c+10000，继续试商下去，直到找出所要求的解。 （2） 程序实现

// 求最小的连续n个合数 #include #include void main()

{ long c,d,f,m,j; int t,n;

printf(\求最小的n个连续合数.\\n\ printf(\请输入n:\ scanf(\ c=3;d=c+10000; f=3; while(1)

{ for(m=c;m<=d;m+=2)

{ for(t=0,j=3;j<=sqrt(m);j+=2)

if(m%j==0) // 实施试商 {t=1;break;}

if(t==0 && m-f>n) // 满足条件即行输出 { printf(\最小的%d个连续合数区间为:\ printf(\。 \\n\ getch();return; }

if(t==0) f=m; // 每求出一个素数m后赋值给f } if(m>d)

{c=d+2;d=c+10000;} // 每一轮试商后改变c,d转下一轮 } }

2-10 和积9数字三角形

求解和为给定的正整数s（s≥45）的9个互不相等的正整数填入9数字三角形，使三角

形三边上的4个数字之和相等（s1）且三边上的4个数字之积也相等（s2）。

图2-7 9数字三角形

（1）求解要点。

把和为s的9个正整数存储于b数组b(1)，…，b(9)中，分布如下图所示。为避免重复，不妨约定三角形中数字“下小上大、左小右大”，即b(1)

图2-8 b数组分布示意图

可以根据约定对b(1)、b(7)和b(4)的值进行循环探索，设置： b(1)的取值范围为1～(s-21)/3（因其他6个数之和至少为21）。 b(7)的取值范围为b(1)+1～(s-28)/2。 b(4)的取值范围为b(7)+1～(s-36)。 同时探索判断步骤如下：

1）若(s+b(1)+b(7)+b(4))%3≠0，则继续探索；否则，记s1=(s+b(1)+b(7)+b(4))/3。 2）根据约定对b(3)、b(5)和b(8)的值进行探索，设置： b(3)的取值范围为(s1-b(1)-b(4))/2+1～s1-b(1)-b(4)。 b(5)的取值范围为(s1-b(4)-b(7))/2+1～s1-b(4)-b(7)。 b(8)的取值范围为(s1-b(1)-b(7))/2+1～s1-b(1)-b(7))。 同时根据各边之和为s1，计算出b(2)、b(6)和b(9)： b(2)=s1-b(1)-b(4)-b(3) b(6)=s1-b(4)-b(5)-b(7) b(9)=s1-b(1)-b(7)-b(8)

3）若b数组存在相同正整数，则继续探索。

4）设s2=b(1)*b(2)*b(3)*b(4)，若另两边之积不为s2，则继续探索；否则探索成功，打印输出结果，接着继续探索直到所有数字组探索完毕为止。 （2）9数字三角形求解程序设计。

// 9数字三角形求解 #include #include void main() {

int k,j,t,s,s1,s2,n,b[10]; printf(\请输入正整数s：\ scanf(\ n=0;

for(b[1]=1;b[1]<=(s-21)/3;b[1]++)

for(b[7]=b[1]+1;b[7]<=(s-28)/2;b[7]++) for(b[4]=b[7]+1;b[4]<=s-36;b[4]++) {

if((s+b[1]+b[4]+b[7])%3!=0) continue; s1=(s+b[1]+b[4]+b[7])/3;

for(b[3]=(s1-b[1]-b[4])/2+1;b[3]

b[2]=s1-b[1]-b[4]-b[3]; b[6]=s1-b[4]-b[7]-b[5]; b[9]=s1-b[1]-b[7]-b[8]; t=0;

for(k=1;k<=8;k++)

for(j=k+1;j<=9;j++)

if(b[k]==b[j]) {t=1;k=8;break;} if(t==1) continue;

s2=b[1]*b[2]*b[3]*b[4];

if(b[4]*b[5]*b[6]*b[7]!=s2) continue; if(b[1]*b[9]*b[8]*b[7]!=s2) continue; n++;

printf(\：-\ for(k=2;k<=9;k++)

printf(\

printf(\ } }

printf(\共%d个解。\}

习题3

3-1 递推求解b数列 已知b数列定义：

b1?1,b2?2,bn?3bn?1?bn?2(n?2)

递推求b数列的第20项与前20项之和。 解：

#include void main()

{ int k,n; long b[3000],s; printf(\请输入n: \ scanf(\ b[1]=1;b[2]=2;s=3; for(k=3;k<=n;k++)

{ b[k]=3*b[k-1]-b[k-2];

s+=b[k]; }

printf(\ printf(\ }

3-2 双关系递推数列 集合M定义如下： 1）1?M

2）x?M?2x?1?M,3x?1?M

3）再无别的数属于M

试求集合M元素从小到大排列的第2011个元素与前2011 个元素之和。 解：（1）设计要点

设n个数在数组m中，2x+1与3x+1均作为一个队列，从两队列中选一排头（数值较小者）送入数组m中。所谓“排头”就是队列中尚未选入m的最小的数（下标）。这里用p2表示2x+1这一列的排头的下标，用p3表示3x+1这一列的排头的下标。

if(2*m(p2)<3*m(p3))

{ m(i)=2*m(p2)+1;p2++;} if(2*m(p2)>3*m(p3))

{ m(i)=3*m(p3)+1;p3++;}

特别注意：两队列若出现相等时，给m数组赋值后，两排头都要增1。

if(2*m(p2)==3*m(p3)) { m(i)=2*m(p2)+1;

p2++; p3++; // 为避免重复项，P2，p3均须增1

} （2） 程序设计 // 双关系递推 #include void main()

{int n,p2,p3,i;long s,m[3000]; m[1]=1;s=1;

p2=1;p3=1; // 排头p2,p3赋初值 printf(\请输入n: \ scanf(\ for(i=2;i<=n;i++) if(2*m[p2]<3*m[p3])

{ m[i]=2*m[p2]+1; s+=m[i];

p2++; }

else

{ m[i]=3*m[p3]+1; s+=m[i];

if(2*m[p2]==3*m[p3]) p2++; // 为避免重复项，P2须增1 p3++;

}

printf(\ printf(\ }

3-3 多幂序列

设x,y,z为非负整数，试计算集合

M?{2x,3y,5z|x?0,y?0,z?0}

的元素由小到大排列的多幂序列第n项与前n项之和。 （1）递推算法设计

集合由2的幂、3的幂与5的幂组成，实际上给出的是3个递推关系。 显然，第1项也是最小项为1（当x=y=z=0时）。 从第2项开始，为了实现从小到大排列，设置3个变量a,b,c，a为2的幂，b为3的幂，c为5的幂，显然a,b,c互不相等。

设置k循环（k=2,3,…,n，其中n为键盘输入整数），在k循环外赋初值：a=2;b=3;c=5;s=1;

在k循环中通过比较赋值：

当a

当b

当c

递推过程描述：

a=2;b=3;c=5; // 为递推变量a,b,c赋初值 for(k=2;k<=n;k++) { if(a

{ f[k]=a;a=a*2;} // 用a给f[k]赋值

else if(b

{ f[k]=b;b=b*3;} // 用b给f[k]赋值 else

{ f[k]=c;c=c*5;} // 用c给f[k]赋值

}

在这一算法中，变量a,b,c是变化的，分别代表2的幂、3的幂与5的幂。 上述递推算法的时间复杂度与空间复杂度均为O(n)。 （2）多幂序列程序实现

// 多幂序列求解 #include void main()

{int k,m,t,p2,p3,p5; double a,b,c,s,f[100];

printf(\求数列的第m项与前m项和,请输入m: \ scanf(\

f[1]=1;p2=0;p3=0;p5=0; a=2;b=3;c=5;s=1; for(k=2;k<=m;k++) { if(a

{ f[k]=a;a=a*2; // 用2的幂给f[k]赋值 t=2;p2++; // t=2表示2的幂，p2为指数 }

else if(b

{ f[k]=b;b=b*3; // 用3的幂给f[k]赋值 t=3;p3++; // t=3表示3的幂，p3为指数 } else

{ f[k]=c;c=c*5; // 用5的幂给f[k]赋值 t=3;p5++; // t=5表示5的幂，p5为指数 }

s+=f[k]; }

printf(\数列的第%d项为: %.0f \

if(t==2) // 对输出项进行标注 printf(\ else if(t==3)

printf(\ else

printf(\

printf(\数列的前%d项之和为：%.0f \\n\}

3-4 双幂积序列的和

由集合M?{2x3y|x?0,y?0}元素组成的复合幂序列，求复合幂序列的指数和x+y≤n（正整数n从键盘输入）的各项之和

s?x?y?0?23xny,x?0,y?0

（1）设计要点

归纳求和递推关系: 当x+y=0时，s(1)=1； 当x+y=1时，s(1)=2+3；

222

当x+y=2时，s(2)=2+2×3+3=2*s(1)+ 3

32233

当x+y=3时，s(3)=2+2×3+2×3+3=2*s(2)+ 3

k

一般地，当x+y=k时，s(k)=2*s(k?1)+3 即有递推关系：

s(k)=2*s(k)+3k

k

其中3可以通过变量迭代实现。这样可以省略数组，简化为一重循环实现复合幂序列求和。

（2）程序实现

// 复合幂序列求和 #include void main()

{int k,n; long sum,t,s[100];

printf(\请输入幂指数和至多为n:\ scanf(\ t=1;s[0]=1; sum=1;

for(k=1;k<=n;k++)

{t=t*3; // 迭代得t=3^k s[k]=2*s[k-1]+t; // 实施递推

sum=sum+s[k]; }

printf(\幂指数和至多为%d的幂序列之和为:%ld\\n\}

3-5 粒子裂变

核反应堆中有α和β两种粒子，每秒钟内一个α粒子可以裂变为3个β粒子，而一个β粒子可以裂变为1个α粒子和2个β粒子。若在t=0时刻的反应堆中只有一个α粒子，求在t秒时反应堆裂变产生的α粒子和β粒子数。

1. 算法设计

设在t秒时α粒子数为f(t)，β粒子数为g(t)，依题可知：

g(t)=3f(t-1)+2g(t-1) （1） f(t)=g(t-1) （2） g(0)=0,f(0)=1

由（2）得f(t-1)=g(t-2) （3） 将式（3）代入（1）得

g(t)=2g(t-1)+3g(t-2) (t≥2) （4） g(0)=0,g(1)=3 （5） 以递推关系（4）与初始条件（5）完成递推。 2．粒子裂变C程序设计 // 粒子裂变

#include void main()

{int t,k;long g[100]; printf(\ scanf(\

g[0]=0; g[1]=3; // 确定初始条件 for(k=2;k<=t;k++)

g[k]=2*g[k-1]+3*g[k-2]; // 完成递推 printf(\秒时反应堆中β粒子数为:%ld \\n\ printf(\秒时反应堆中α粒子数为:%ld \\n\}

3-6 m行n列逆转矩阵

#include void main()

{int g,i,k,u,t,a[10]; long m1,m2,m3; i=1;a[1]=1; while (1) {g=1;

for(k=i-1;k>=1;k--)

if(a[i]==a[k]) {g=0;break;} // 两数相同,标记g=0 if(i==9 && g==1 && a[1]1 && a[7]>1) {m1=a[2]*10+a[3];

m2=a[5]*10+a[6]; m3=a[8]*10+a[9];

for(t=0,u=2;u<=9;u++)

{if(a[1]%u==0 && m1%u==0) t=1; if(a[4]%u==0 && m2%u==0) t=1; if(a[7]%u==0 && m3%u==0) t=1; }

if(t==0 && m1*a[4]*a[7]+m2*a[1]*a[7]==m3*a[1]*a[4]) // 判断等式 {printf(\

printf(\} }

if(i<9 && g==1)

{i++;a[i]=1;continue;} // 不到9个数,往后继续 while(a[i]==9 && i>1) i--; // 往前回溯 if(a[i]==9 && i==1) break;

else a[i]++; // 至第1个数为9结束 } }

5-2 两组均分

参加拔禾比赛的12个同学的体重如下：

48，43，57，64，50，52，18，34，39，56，16，61

为使比赛公平，要求参赛的两组每组6个人，且每组同学的体重之和相等。 请设计算法解决这 “两组均分”问题。 （1） 求解要点

一般地，对已知的2n(n从键盘输入)个整数，确定这些数能否分成2个组，每组n个数，

且每组数据的和相等。

我们可采用回溯法逐步实施调整。

对于已有的存储在b数组的2n个数,求出总和s与其和的一半s1(若这2n个数的和s为奇数,显然无法分组)。把这2n个数分成二个组,每组n个数。为方便调整,?设置数组a存储b数组的下标值，即a(i):1─2n。

考察b(1)所在的组,只要另从b(2)─b(2n)中选取n-1个数。即定下a(1)=1,?其余的a(i)(i=2,…,n)在2─2n中取不重复的数。因组合与顺序无关,不妨设 2 ≤ a(2)

从a(2)取2开始,以后a(i)从a(i-1)+1开始递增1取值,直至n+i为止。这样可避免重复。

当a(n)已取值,计算s=b(1)+b(a(2))+…+b(a(n)),对和s进行判别: 若s=s1,满足要求,实现平分。

若s≠s1,则a(n)继续增1再试。如果a(n)已增至2n,则回溯前一个a(n-1)增1再试。如果a(n-1)已增至2n-1,继续回溯。直至a(2)增至n+2时,结束。 二堆均分问题并不总有解。有解时,找到并输出所有解。没有解时,显示相关提示信息“无法实现平分”。

（2） 两组均分程序设计

// 两组均分程序设计 #define N 50

#include #include #include void main()

{int n,m,a[N],b[2*N],i,j,t; long s1,s=0;

printf(\把2n个整数分为和相等的两个组,每组n个数.\\n\ t=time(0)00;srand(t); // 随机数发生器初始化 printf(\

for(s=0,i=1;i<=2*n;i++) // 产生2n个不同的随机整数 {t=0;b[i]=rand()%(5*n)+10; for(j=1;j<=i-1;j++) if(b[i]==b[j])

{t=1;break;}

if(t==1) {i--;continue;} // 出现相同数时，返回重新产生 s+=b[i]; printf(\ } if(s%2==0)

{printf(\以上%d个整数总和为%d.\\n\

s1=s/2;

} else

printf(\和%ld为奇数,无法平分!\\n\ a[1]=1;i=2;a[i]=2; m=0; while(1) {if(i==n)

{for(s=0,j=1;j<=n;j++)

s+=b[a[j]];

if(s==s1) // 满足均分条件时输出 {m++; printf(\ for(j=1;j<=n;j++)

printf(\

} }

else

{i++; a[i]=a[i-1]+1; continue;}

while(a[i]==n+i) i--; // 调整或回溯 if(i>1) a[i]++; else break; }

if(m>0) printf(\共有以上%d种分法。\

else printf(\无法实现二堆均分. \}

5-3 指定低逐位整除数探求

试求出所有最高位为3的24位低逐位整除数（除个位数字为“0”外,其余各位数字均不得为“0”）。

// 最高位为3的n位右逐位整除 #include void main()

{ int i,j,n,r,t,a[100]; long s=0;

printf(\逐位整除n位，请确定n：\ scanf(\

printf(\所求%d位最高位为3的右逐位整除数：\\n\ for(j=1;j<=100;j++) a[j]=1; t=0;a[1]=0;i=1; while(a[1]<1)

{ if(t==0 && i

for(r=0,j=i;j>=1;j--) // 检测i时是否整除i { r=r*10+a[j]; r=r%i; } if(r!=0)

{ a[i]=a[i]+1;t=1; // 余数r!=0时a[i]增1,t=1 while(a[i]>9 && i>1)

{ a[i]=1;i--; // 回溯 a[i]=a[i]+1; }

}

else t=0; // 余数r=0时,t=0

if(t==0 && i==n) { if(a[n]==3)

{s++;printf(\

for(j=n;j>=1;j--) printf(\ printf(\

}

a[i]=a[i]+1; } }

if(s>0)

printf(\最高位为3的%d位右逐位整除数共%ld个.\ else

printf(\未找到n位右逐位整除数.\ }

5-4 枚举求解8项素数和环，与回溯结果进行比较。 (1) 设计要点

为简化输出，环序列简化为一般序列输出，为避免重复，约定首项为“1”。

环中的每一项为一个数字，相连的8项构成一个8位数。因而设置a循环在没有重复数字数字且以“1”开头的8位数812345678——18765432中枚举。注意到所有1——8没有重复数字的8位数的数字和为9的倍数，该数也为9的倍数，为此，枚举循环步长可取9，以精简枚举次数。

为操作与判断方便，设置3个数组：

f数组统计8位数a中各个数字的频数。如f[3]=2，即a中有2个数字“3”。 g数组表示8位数a中每位数的数字。如g[4]=6，即a的从高位开始第4位数为数字“6”。 b数组标记整数x是否为素数。如b[13]=1，标识“1”表示13为素数，标识“0”为非素数。

枚举实施：

1） 注意到8项中每相邻两项之和不超过15,对15以内的5个素数用b数组标注“1”,其余均为“0”。

2） 在8位数的a 循环中，对a实施8次求余分离出各个数字x，应用f[x]++统计数字x的频数，应用g[9-k]=x记录a的各位数字。

3） 设置k(1——8)判断循环：

若f[k]!=1 ，表明数字k出现重复或遗漏，返回。

若 b[g[k]+g[k+1]]!=1，表明相邻的第k项与第k+1项之和不是素数，返回。顺便说明，为判断方便，首项“1”先行赋值给g[9]，以与g[8]相邻，在k循环中一道进行判别。

4） 通过以上判断筛选的a，其各个数字即为所求的8项素数环的各项，打印输出。 (2) 枚举实现8项素数和环 // 8项素数和环枚举求解 #include #include void main()

{ int t,k,s,x,g[10],f[10],b[18];long a,y; for(k=1;k<=15;k++) b[k]=0; g[9]=1;s=0;

b[3]=b[5]=b[7]=b[11]=b[13]=1; // 5个奇素数标记 printf(\项素数和环：\\n\

for(a=12345678;a<=18765432;a+=9) // 步长为9枚举8位数 {t=0;y=a;

for(k=0;k<=9;k++) f[k]=0; for(k=1;k<=8;k++)

{x=y;f[x]++; // 分离a的8个数字,用f数组统计x的个数 g[9-k]=x; // 用g数组记录a的第k位数字

y=y/10;

}

for(k=1;k<=8;k++)

if(f[k]!=1 || b[g[k]+g[k+1]]!=1) t=1;

if(t==1) continue; // 有相同数字或相邻和非素，返回 s++;

printf(\输出8项素数和环 for(k=2;k<=8;k++) printf(\ printf(\ } }

5-5 递归求解20项素数环