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

1、计算机常用算法与程序设计案例教程习题解答提要习题11-1 分数分解算法描述把真分数a/b分解为若干个分母为整数分子为“1”的埃及分数之和： （1） 寻找并输出小于a/b的最大埃及分数1/c； （2） 若c>900000000，则退出； （3） 若c900000000，把差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(c>90

2、0000000) 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 时间复杂度为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+

3、u+u=u(u+1)=(n1)(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*1001;b>=a*10099;b=2) for(x=0,k=1;k<=sqrt(b);k+=2) if(

4、b%k=0) x=1;break; s=s+x; if(s=50) printf("%ld n",a);break;解：因a循环n次；对每一个a,b循环50次；对每一个b,k循环次。因而k循环体的执行次数s满足时间复杂度为o()。1-3 若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+=(ma1+(m-1)a2+)×lo

5、gn <clogn因而有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赋值；右部按列

6、号函数n+1-j赋值。（2） 程序实现#include <stdio.h>void main()int i,j,n,a3030; printf(" 请确定方阵阶数n: "); scanf("%d",&n); for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(i=j | i+j=n+1) aij=0; / 方阵对角线元素赋值 if(i+j<n+1 && i<j) aij=i; / 方阵上部元素赋值 if(i+j<n+1 && i>j) aij=j

7、; / 方阵左部元素赋值 if(i+j>n+1 && i>j) aij=n+1-i; / 方阵下部元素赋值 if(i+j>n+1 && i<j) aij=n+1-j; / 方阵右部元素赋值 printf(" %d阶对称方阵为:n",n); for(i=1;i<=n;i+) for(j=1;j<=n;j+) / 输出对称方阵 printf("%3d",aij); printf("n"); 1-5 据例1-2的算法，写出求解n个“1”组成的整数能被2011整除的程序。修改

8、程序，求出 n至少为多大时，n个“1”组成的整数能被2013整除？解：程序为#include <stdio.h>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",n,p);习题22-1 解不等式设n为正整数，解不等式解：上下限一般为键盘输入的a,b。/ 解不等式: a<1+1/(1+1/2)+.+1/(1+1/2+.+

9、1/n)<b#include <stdio.h>#include<math.h>void main() long a,b,c,d,i; double ts,s; printf(" 请输入a,b: "); scanf("%d,%d",&a,&b); i=0;ts=0;s=0; while(s<a) i=i+1; ts=ts+(double)1/i; s=s+1/ts; c=i; while(s<b) i=i+1; ts=ts+(double)1/i; s=s+1/ts; d=i-1; printf(

10、"n 满足不等式的正整数n为: %ldn%ld n",c,d);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

11、,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 <stdio.h>void m

12、ain() long int x; x=65; while(1) x=x+66; if(x%5=1 && x%7=4) printf("至少有兵: %ld 个。",x); break; 2-3 分解质因数对给定区间m,n的正整数分解质因数,每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。例如, 2012=2*2*503, 2011=(素数!)。解：对区间中的每一个整数i(b=i)，用k(2sqrt(i)试商：若不能整除，说明该数k不是b的因数，k增1后继续试商。若能整除，说明该数k是b的因数，打印输出"k*&qu

13、ot;；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<b<i，说明i有一个大于sqrt(i)的因数，要补上该因数。若试商后b还是原来的i,则i是素数。/ 质因数分解乘积形式 #include"math

14、.h"#include <stdio.h>void main()long int b,i,k,m,n,w=0;printf("m,n中整数分解质因数（乘积形式）.n");printf("请输入m,n:");scanf("%ld,%ld",&m,&n);for(i=m;i<=n;i+) / i为待分解的整数 printf("%ld=",i); b=i;k=2; while(k<=sqrt(i) / k为试商因数 if(b%k=0) b=b/k;if(b>1) p

15、rintf("%ld*",k);continue; / k为质因数,返回再试 if(b=1) printf("%ldn",k); k+; if(b>1 && b<i) printf("%ldn",b); / 输出大于i平方根的因数 if(b=i) printf("(素数!)n");w+; / b=i,表示i无质因数 2-4 基于素数代数和的最大最小定义和： (和式中第k项±(2k-1)*(2k+1)的符号识别：当(2k-1)与(2k+1)中至少有一个素数，取“+”；其余取“-”

16、。例如和式中第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为素数，标注ak=1；否则，若2k-1不是素数，ak=0。设置k循环（1n），循环中分别情况求和：若ak+ak+1>=1，即(2k-1)与(2k+1)中至少有一个素数，实施“+”；否则，若ak+ak+1=0，即(2k-1)与(2

17、k+1)中没有素数，实施“-”。同时，设置最大值变量smax，最小值变量smin。在循环中，每计算一个和值s，与smax比较确定最大值，同时记录此时的项数k1；与smin比较确定最小值，同时记录此时的项数k2。/ 基于素数的整数和 #include<stdio.h>#include<math.h>void main() int t,j,n,k,k1,k2,a3000; long s,smax,smin; printf(" 请输入整数n: "); scanf("%d",&n); for(k=1;k<=n+1;k+) a

18、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) ak=1; / 标记第k个奇数2k-1为素数 s=3;smax=0;smin=s; for(k=2;k<=n;k+) if(ak+ak+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<smin)smin=s;k2=k; / 比较求

19、最大值smin printf("s(%d)=%ld n",n,s);printf("当k=%d时s有最大值: %ldn",k1,smax);printf("当k=%d时s有最小值: %ldn",k2,smin);2-5 特定数字组成的平方数用数字2,3,5,6,7,8,9可组成多少个没有重复数字的7位平方数？解：求出最小7位数的平方根b, 最大7位数的平方根c.用a枚举b，c中的所有整数，计算d=a*a，这样确保所求平方数在d中。设置f数组统计d中各个数字的个数。如果f3=2，即平方数d中有2个“3”。检测若fk>1(k=09)

20、，说明d中存在有重复数字，返回。在不存在重复数字的情形下，检测若f0+f1+f4=0，说明7位平方数d中没有数字“0”,“1”,“4”,d满足题意要求，打印输出。/ 组成没有重复数字的7位平方数 #include <math.h>#include <stdio.h>void main()int k,m,n,t,f10; 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+) fk=0; while(w&g

21、t;0) m=w%10;fm+;w=w/10; for(t=0,k=1;k<=9;k+) if(fk>1) t=1; / 测试三个平方数是否有重复数字 if(t=0 && f0+f1+f4=0) / 测试平方数中没有数字0,1,4 n+; printf(" %2d: ",n); printf(" %ld=%ld2 n",d,a); printf(" 共可组成%d个没有重复数字的7位平方数.n",n); 2-6 写出例2-2中对称方阵的完整程序，并运行程序。对称方阵程序：#include <stdio.

22、h>void main()int i,j,n,a3030; printf(" 请确定方阵阶数n: "); scanf("%d",&n); for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(i+j<=n+1 && i<=j) aij=(n+1)/2-i+1; / 方阵上部元素赋值 if(i+j<n+1 && i>j) aij=(n+1)/2-j+1; / 方阵左部元素赋值 if(i+j>=n+1 && i>=j) aij=i

23、-n/2; / 方阵下部元素赋值 if(i+j>n+1 && i<j) aij=j-n/2; / 方阵右部元素赋值 printf(" %d阶对称方阵为:n",n); for(i=1;i<=n;i+) for(j=1;j<=n;j+) / 输出对称方阵 printf("%3d",aij); printf("n"); 2-7 四则运算式把数字1,2,.,9这9个数字填入以下含加减乘除的综合运算式中的9个中,使得该式成立×+÷-=0 要求数字1,2,.,9这9个数字在各式中都出现一

24、次且只出现一次，且约定数字“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(19)的个数。若某一f(x)不为1，不满足数字1,2,.,9这九个数字都出现一次且只出现一次，标记t=1.若所有f(x)全为1，满足数字1,2,.,9这九

25、个数字都出现一次且只出现一次，保持标记t=0, 则输出所得的完美综合运算式。设置n统计解的个数。（2） 程序实现/ 四则运算式 #include <stdio.h>void main()int x,y,t,k,a,b,c,d,e,n=0; int m6,f11; 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; m1=a;m2=c;m3=

26、e;m4=b;m5=d; for(x=0;x<=9;x+) fx=0; for(k=1;k<=5;k+) y=mk; while(y>0) x=y%10;fx=fx+1;y=(y-x)/10; / 分离数字f数组统计 for(t=0,x=1;x<=9;x+) if(fx!=1) t=1; break; / 检验数字0-9各只出现一次 if(t=0) / 输出一个解，用n统计个数 n+; printf("%2d: %2d*%1d+%3d/%1d-%2d=0 n",n,a,b,c,d,e); printf(" n=%d.n",n);

27、2-8 合数世纪探求定义一个世纪的100个年号中不存在一个素数，即100个年号全为合数的世纪称为合数世纪。探索最早的合数世纪。（1） 设计要点应用穷举搜索，设置a世纪的的50个奇数年号(偶数年号无疑均为合数)为b，用k试商判别b是否为素数，用变量s统计这50个奇数中的合数的个数。对于a世纪，若s=50，即50个奇数都为合数，找到a世纪为最早的合数世纪，打印输出后退出循环结束。（2） 合数世纪程序设计/ 合数世纪探求 #include <stdio.h>#include <math.h>void main()long a,b,k; int s,x; a=1; while

28、(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",a);break; 2-9 最小连续n个合数试求出最小的连续n个合数。（其中n是键盘输入的任意正

29、整数。） （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个合数 #i

30、nclude <stdio.h>#include <math.h>void main() long c,d,f,m,j; int t,n; printf(" 求最小的n个连续合数.n"); printf(" 请输入n:"); scanf("%d",&n); 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 &&a

31、mp; m-f>n) / 满足条件即行输出 printf("最小的%d个连续合数区间为:",n); printf("%ld,%ld。 n",f+1,f+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（s45）的9个互不相等的正整数填入9数字三角形，使三角形三边上的4个数字之和相等（s1）且三边上的4个数字之积也相等（s2）。图2-7 9数字三角形（1）求解要点

32、。把和为s的9个正整数存储于b数组b(1)，b(9)中，分布如下图所示。为避免重复，不妨约定三角形中数字“下小上大、左小右大”，即b(1)<b(7)<b(4)且b(2)<b(3)且b(6)<b(5)且b(9)<b(8)。图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)%30，则继续探索；否则，记s

33、1=(s+b(1)+b(7)+b(4)/3。2）根据约定对b(3)、b(5)和b(8)的值进行探索，设置： b(3)的取值范围为(s1-b(1)-b(4)/2+1s1-b(1)-b(4)。 b(5)的取值范围为(s1-b(4)-b(7)/2+1s1-b(4)-b(7)。 b(8)的取值范围为(s1-b(1)-b(7)/2+1s1-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

34、=b(1)*b(2)*b(3)*b(4)，若另两边之积不为s2，则继续探索；否则探索成功，打印输出结果，接着继续探索直到所有数字组探索完毕为止。（2）9数字三角形求解程序设计。/ 9数字三角形求解 #include<stdio.h>#include<math.h>void main() int k,j,t,s,s1,s2,n,b10; printf(" 请输入正整数s："); scanf("%d",&s); n=0; for(b1=1;b1<=(s-21)/3;b1+) for(b7=b1+1;b7<=(s-2

35、8)/2;b7+) for(b4=b7+1;b4<=s-36;b4+) if(s+b1+b4+b7)%3!=0) continue; s1=(s+b1+b4+b7)/3; for(b3=(s1-b1-b4)/2+1;b3<s1-b1-b4;b3+) for(b5=(s1-b4-b7)/2+1;b5<s1-b4-b7;b5+) for(b8=(s1-b1-b7)/2+1;b8<s1-b1-b7;b8+) b2=s1-b1-b4-b3; b6=s1-b4-b7-b5; b9=s1-b1-b7-b8; t=0; for(k=1;k<=8;k+) for(j=k+1;j&

36、lt;=9;j+) if(bk=bj) t=1;k=8;break; if(t=1) continue; s2=b1*b2*b3*b4; if(b4*b5*b6*b7!=s2) continue; if(b1*b9*b8*b7!=s2) continue; n+; printf(" %3d：%2d",n,b1); for(k=2;k<=9;k+) printf(", %2d",bk); printf(" s1=%d, s2=%d n",s1,s2); printf("共%d个解。",n);习题33-1 递推求

37、解b数列已知b数列定义：递推求b数列的第20项与前20项之和。解： #include <stdio.h>void main() int k,n; long b3000,s; printf(" 请输入n: "); scanf("%d",&n); b1=1;b2=2;s=3; for(k=3;k<=n;k+) bk=3*bk-1-bk-2;s+=bk; printf(" b(%d)=%ld n",n,bn); printf(" s=%ld n",s); 3-2 双关系递推数列集合m定义如下：1

38、）2）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

39、(p3) m(i)=2*m(p2)+1;p2+; p3+; / 为避免重复项，p2，p3均须增1 （2） 程序设计/ 双关系递推 #include <stdio.h> void main() int n,p2,p3,i;long s,m3000; m1=1;s=1; p2=1;p3=1; / 排头p2,p3赋初值 printf(" 请输入n: "); scanf("%d",&n); for(i=2;i<=n;i+) if(2*mp2<3*mp3) mi=2*mp2+1; s+=mi;p2+; else mi=3*mp3+1

40、; s+=mi; if(2*mp2=3*mp3) p2+; / 为避免重复项，p2须增1 p3+; printf(" m(%d)=%ldn",n,mn); printf(" s=%ldn",s); 3-3 多幂序列设x,y,z为非负整数，试计算集合的元素由小到大排列的多幂序列第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

41、=2,3,n，其中n为键盘输入整数），在k循环外赋初值：a=2;b=3;c=5;s=1;在k循环中通过比较赋值：当a<b且a<c时，由赋值fk=a确定为序列的第k项；然后a=a*2，即a按递推规律乘2，为后一轮比较作准备；当b<a且b<c时，由赋值fk=b确定为序列的第k项；然后b=b*3，即b按递推规律乘3，为后一轮比较作准备。当c<a且c<b时，由赋值fk=c确定为序列的第k项；然后c=c*5，即c按递推规律乘5，为后一轮比较作准备。递推过程描述：a=2;b=3;c=5; / 为递推变量a,b,c赋初值 for(k=2;k<=n;k+) if(a&

42、lt;b && a<c) fk=a;a=a*2; / 用a给fk赋值 else if(b<a && b<c) fk=b;b=b*3; / 用b给fk赋值 else fk=c;c=c*5; / 用c给fk赋值 在这一算法中，变量a,b,c是变化的，分别代表2的幂、3的幂与5的幂。上述递推算法的时间复杂度与空间复杂度均为o(n)。（2）多幂序列程序实现/ 多幂序列求解 #include <stdio.h>void main()int k,m,t,p2,p3,p5; double a,b,c,s,f100; printf(" 求

43、数列的第m项与前m项和,请输入m: "); scanf("%d",&m); f1=1;p2=0;p3=0;p5=0; a=2;b=3;c=5;s=1; for(k=2;k<=m;k+) if(a<b && a<c) fk=a;a=a*2; / 用2的幂给fk赋值 t=2;p2+; / t=2表示2的幂，p2为指数 else if(b<a && b<c) fk=b;b=b*3; / 用3的幂给fk赋值 t=3;p3+; / t=3表示3的幂，p3为指数 else fk=c;c=c*5; / 用5的

44、幂给fk赋值 t=3;p5+; / t=5表示5的幂，p5为指数 s+=fk; printf(" 数列的第%d项为: %.0f ",m,fm); if(t=2) / 对输出项进行标注 printf("(2%d) n",p2); else if(t=3) printf("(3%d) n",p3); else printf("(5%d) n",p5); printf(" 数列的前%d项之和为：%.0f n",m,s);3-4 双幂积序列的和由集合元素组成的复合幂序列，求复合幂序列的指数和x+yn（正

45、整数n从键盘输入）的各项之和 （1）设计要点归纳求和递推关系:当x+y=0时，s(1)=1；当x+y=1时，s(1)=2+3；当x+y=2时，s(2)=22+2×3+32=2*s(1)+ 32当x+y=3时，s(3)=23+22×3+2×32+33=2*s(2)+ 33一般地，当x+y=k时，s(k)=2*s(k1)+3k即有递推关系：s(k)=2*s(k)+3k其中3k可以通过变量迭代实现。这样可以省略数组，简化为一重循环实现复合幂序列求和。（2）程序实现/ 复合幂序列求和 #include <stdio.h>void main()int k,n;

46、long sum,t,s100; printf("请输入幂指数和至多为n:"); scanf("%d",&n); t=1;s0=1; sum=1; for(k=1;k<=n;k+) t=t*3; / 迭代得t=3k sk=2*sk-1+t; / 实施递推 sum=sum+sk; printf("幂指数和至多为%d的幂序列之和为:%ldn",n,sum); 3-5 粒子裂变核反应堆中有和两种粒子，每秒钟内一个粒子可以裂变为3个粒子，而一个粒子可以裂变为1个粒子和2个粒子。若在t=0时刻的反应堆中只有一个粒子，求在t秒时反应

47、堆裂变产生的粒子和粒子数。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) (t2) （4）g(0)=0,g(1)=3 （5）以递推关系（4）与初始条件（5）完成递推。2粒子裂变c程序设计/ 粒子裂变#include<stdio.h>void main()int t,k;long g100; printf(" input t:");

48、 scanf("%d",&t); g0=0; g1=3; / 确定初始条件 for(k=2;k<=t;k+) gk=2*gk-1+3*gk-2; / 完成递推 printf("%d 秒时反应堆中粒子数为:%ld n",t,gt); printf("%d 秒时反应堆中粒子数为:%ld n",t,gt-1);3-6 m行n列逆转矩阵 图3-4所示为4行5 列逆转矩阵。 1 14 13 12 112 15 20 19 10 3 16 17 18 9 4 5 6 7 8图3-4 4行5列逆转矩阵试应用递推设计构造并输出任意指定m

49、行n列逆转矩阵。解： 对输入的m,n，取c=min(m,n)，计算数字矩阵的圈数d=(c+1)/2。设置i(1d)循环，从外圈至内圈，分4边进行递推赋值。程序设计：/ m×n数字逆转矩阵 #include <stdio.h>void main()int i,j,c,d,h,v,m,n,s,a3030; printf(" m行n列矩阵,请确定m,n: "); scanf("%d,%d",&m,&n); c=n; if(m<n) c=m; d=(c+1)/2; s=0;v=0; for(i=1;i<=d;i+) / 从外至内第d圈赋值 v+; for(h=i;h<=m-i;h+) / 一圈的左列从上至下递增 s+; ahv=s;for(v=i;v<=n-i;v+) / 一圈的下行从左至右递增 s+; ahv=s;for(h=m+1-i;h>i;h-) / 一圈的右列从下至上递增 s+; ahv=s;if(s=m*n) h=i;break;for(v=n+1-i;v>i;v-) / 一圈的上行从