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

《计算机常用算法与程序设计案例教程》习题解答提要习题11-1分数分解算法描述把真分数a/b分解为若干个分母为整数分子为“げ的埃及分数之和:(1)寻找并输出小于a/b的最大埃及分数1/c；(2)若¢>900000000,则退出:(3)若cW900000000,把差a/bT/c整理为分数a/b,若a/b为埃及分数,则输出后结束。(4)若a/b不为埃及分数,则继续(1)、⑵、(3)。试描述以上算法。解:设/=血(纟)(这里int(x)表示取正数x的整数),注意到"<2<d+i，有a aa1_a(d+l)-bbd+1b(d+1)算法描述:令c=d+L则input(a,b)while(l){c=int(b/a)+l;if(¢>900000000)return;else{print(l/c+);a=a*c-b;b=b*c; //a,b迭代,为选择下ー个分母作准备if(a==l){print(1/b);return;}1-2求出以下程序段所代表算法的时间复杂度m=0;for(k=l;k<=n;k++)for(j=k;j>=l;j—)m=m+j;解:因s=l+2+…+n=n(n+l)/2时间复杂度为0(ボ)。m=0;for(k=l;k<=n;k++)for(j=l;j<=k/2;j++)m=m+j;解:设n=2u+l,语句m=m+l的执行频数为s=1+1+2+2+3+3+…+u+u=u(u+l)=(n-1)(n+l)/4设n=2u,语句m=m+l的执行频数为s=l+l+2+2+3+3+—+u=u2=n2/4时间复杂度为0(ボ)。t=l;m=O;for(k=l;k<=n;k++){t=t*k;for(j=l;j<=k*t;j++)m=m+j;解:因s=l+2X2!+3X3!+-+nXn!=(n+l)!-l时间复杂度为0((n+l)!).for(a=l;a〈=n;a++){s=0;for(b=a*100-1;b>=a*100-99;b-=2){for(x=0,k=l;k<=sqrt(b);k+=2)if(b%k==O){x=l;break;}s=s+x;if(s==50)printfC"%ld\n*,a);break;}解:因a循环n次;对每ー个a,b循环50次;对每ー个b,k循环栃/2次。因而k循环体的执行次数s满足5<25(V99+5/199+--+V100n-l)<250(l+>/2+-+>/n)<250- 250nG时间复杂度为0()〇1-3若p(n)是n的多项式,证明:0(log(p(n)))=0(logn)〇证:设m为正整数,p(n)=alXnn,+a2Xn",'+***+ainXn,取常数c>mal+(mT)a2+…+am,则log(p(n))=malXlogn+(m-l)a2Xlogn+…二(mal+(mT)a2+…)Xlogn<clogn因而有0(log(p(n)))=0(1ogn)〇1-4构建对称方阵观察图1-5所示的7阶对称方阵:TOC\o"1-5"\h\z1 0 2 2 2 0 11 2 0 3 0 2 11 2 3 0 3 2 11 2 0 3 0 2 11 0 2 2 2 0 10111110图!-57阶对称方阵试构造并输出以上n阶对称方阵。解:这是一道培养与锻炼我们的观察能力与归纳能力的案例,ー个ー个元素枚举赋值显然行不通,必须全局着眼,分区域归纳其构造特点,分区域枚举赋值。(1)设计要点设方阵中元素的行号为i,列号为jo可知主对角线:i打;次对角线:i+j=n+l。两对角线赋值“〇”。按两条对角线把方阵分成上部、左部、右部与下部4个区,如图1-6所示。图1-6对角线分成的4个区上部按行号i赋值;下部按行号函数n+1-i赋值。左部按列号j赋值;右部按列号函数n+1-j赋值。(2)程序实现#include<stdio.h>voidmain(){inti,j,n,a[30][30];printfC请确定方阵阶数n:");scanf&n);for(i=l;i〈=n;i++)for(j=l;j<=n;j++){if(i=jIIi+j==n+l)a[i][j]=0; 〃方阵对角线元素赋值if(i+j<n+l&&i<j)a[i][j]=i; /Z方阵上部元素赋值if(i+j<n+l&&i>j)a[i][j]=j! 〃方阵左部元素赋值if(i+j>n+l&&i>j)a[i][j]=n+l-i; /Z方阵下部元素赋值if(i+j>n+l&&i<j)a[i][j]=n+l-j; /Z方阵右部元素赋值printf("%d阶对称方阵为:\n”,n);for(i=l;i<=n;i++){for(j=l;j<=n;j++)/Z输出对称方阵printf("%3d",a[i][j]);printf("\n");1-5据例『2的算法,写出求解n个“ド组成的整数能被2011整除的程序。修改程序,求出n至少为多大时,n个“1”组成的整数能被2013整除?解:程序为#include<stdio.h>voidmain(){inta,c,p,n;p=2011;c=llll;n=4; //变量c与n赋初值while(c!=0) /Z循环模拟整数竖式除法{a=c*10+l;c=a%p;n=n+l; /Z每试商一位n增1}printf(/x由%d个1组成的整数能被%d整除。'n”,n,p);习题22-I解不等式设n为正整数,解不等式2010<l+ + 卜…t <20112010<l+1+1/21+1/2+1/3 1+1/2+-+1/H解:上下限一般为键盘输入的a,b。//解不等式:a<l+l/(1+1/2)+...+l/(l+l/2+...+l/n)<b#include<stdio.h>#include<math.h>voidmain(){longa,b,c,d,i;doublets,s;printf(，Z请输入a,b:");scanf("%d,%d",&a,&b);i=0;ts=0;s=0;while(s<a){i=i+l;ts=ts+(double)1/i;s=s+l/ts;c=i;while(s<b){i=i+l;ts=ts+(double)1/i;s=s+l/ts;)d=i-l;printf(zz\n满足不等式的正整数n为:%ldWnW%ld\nzz,c,d);2-2韩信点兵韩信在点兵的时候,为了知道有多少个兵,同时乂能保住军事机密,便让士兵排队报数。按从1至5报数,记下最末一个士兵报的数为1；再按从1至6报数,记下最末一个上兵报的数为5；再按1至7报数,记下最末一个报的数为4；最后按1至11报数,最末一个士兵报的数为10o你知道韩信至少有多少兵?.求解要点设兵数为X,则X满足下述的同余方程组:x=5y+! 即x=l(mod5)x-6z+5 x=5(mod6)x=7u+4 x=4(mod7)x=llv+10 x=10(mod11)其中y,z,u,v都为正整数。试求满足以上方程组的最小正整数xo应用枚举可得到至少的兵数。x从1开始递增1取值枚举当然可以,但不必要。事实上枚举次数可联系问题的具体实际大大缩减。(1)注意到x除11余10,于是可设置x从21开始,以步长11递增。此时,只要判别前三个条件即可。(2)由以上第2,4两方程知x+!为11的倍数，也为6的倍数。而11与6互素,因而x+1必为66的倍数。于是取x=65开始，以步长66递增。此时,只要判别x%5=l与x%7=4两个条件即可。这样可算得满足条件的最小整数x即点兵的数量。.程序实现/Z韩信点兵ttinclude<stdio.h>voidmain(){longintx;x=65;while(l){x=x+66;if(x%5=l&&x%7==4){printf("至少有兵:%ld个。”,x);break;2-3分解质因数对给定区间［m,n］的正整数分解质因数，每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数,则注明为素数。例如,2012=2*2*503,2011=(素数!)。解:对区间中的每一个整数i(b=i),用k(2——sqrt(i))试商:若不能整除，说明该数k不是b的因数,k增1后继续试商。若能整除，说明该数k是b的因数，打印输出"k*"；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后继续。若上述试商完成后l〈b<i,说明i有一个大于sqrt(i)的因数,要补上该因数。若试商后b还是原来的i,则i是素数。/Z质因数分解乘积形式#include"math.h"#include<stdio.h>voidmain(){longintb,i,k,m,n,w=0;printf("[m,n]中整数分解质因数(乘积形式).、n");printf("请输入m,n:");scanf("%ld,%ld",&m,&n);printf("请输入m,n:");scanf("%ld,%ld",&m,&n);for(i=m;i<=n;i++){printf("%ld=",i);b=i;k=2;while(k〈=sqrt(i)){if(b%k=O){b=b/k;if(b>l){printf("%ld*",k);continue;//i为待分解的整数//k为试商因数//k为质因数,返回再试if(b==l)printf("%ld\n”,k);)k++;/Z输出大于i/Z输出大于i平方根的因数if(b==i){printf("(素数!)、n");w++;} //b=i,表示i无质因数2-4基于素数代数和的最大最小定义和:5(〃)=lx3+3x5+5x7+7x9±…±(2n-l)x(2n+l)(和式中第k项±(2kT)*(2k+l)的符号识别:当(2kT)与(2k+l)中至少有一个素数,取其余取“-"。例如和式中第13项取即为ー25*27。)1)求s(2011)。2)设l〈=nく=2设1,当n为多大时,s(n)最大。3)设1く=nく=2011,当n为多大时，s(n)最小。解:代数和式中各项的符号并不是简单的正负相间，而是随着构成素数而改变。因而在求和之前应用“试商判别法”对第k个奇数2kT是否为素数进行标注：若2kT为素数，标注若k]=l；否则，若2kT不是素数,a[k]=0»设置k循环(1——n),循环中分别情况求和：若a[k]+a[k+l]〉=l,即(2kT)与(2k+l)中至少有一个素数，实施"+"；否则，若a[k]+a[k+l]==0,即(2kT)与(2k+D中没有素数，实施“-”。同时，设置最大值变量smax,最小值变量smin。在循环中,每计算ー个和值s,与smax比较确定最大值,同时记录此时的项数kl;与smin比较确定最小值，同时记录此时的项数k2。/Z基于素数的整数和^include<stdio.h>#include<math.h>voidmain(){intt,j,n,k,kl,k2,a[3000];longs,smax,smin;printf("请输入整数n:");scanf("%d",&n);for(k=l;k<=n+l;k++)a[k]=0;for(k=2;kく=n+1;k++){for(t=0,j=3;j<=sqrt(2*k-l);j+=2)if((2*k-l)%j=0){t=l;break;}if(t==O)a[k]=l;/Z标记第k个奇数2k-l为素数s=3;smax=0;smin=s;for(k=2;k<=n;k++){if(a[k]+a[k+1]>=1)s+=(2*k-l)*(2*k+l);/Z实施代数和elses-=(2*k-l)*(2*k+l);if(s>smax){smax=s;kl=k;}/Z比较求最大值smaxif(s<smin){smin=s;k2=k;}/Z比较求最大值smin

printf(*s(%d)=%ld\n”,n,s);printf("当k=%d时s有最大值:%ld\n*,kl,smax);printf("当k=%d时s有最小值:%ld\n*,k2,smin);2-5特定数字组成的平方数用数字2,3,5,6,7,8,9可组成多少个没有重复数字的?位平方数?解:求出最小7位数的平方根b,最大7位数的平方根c.用a枚举[b,c]中的所有整数,计算d=a*a,这样确保所求平方数在d中。设置f数组统计d中各个数字的个数。如果f[3]=2,即平方数d中有2个“3”。检测若f[k]>l(k=O—9),说明d中存在有重复数字,返回。在不存在重复数字的情形下,检测若f[0]+f[l]+f[4]=0,说明7位平方数d中没有数字字”，“1"“4”，d满足题意要求,打印输出。/Z组成没有重复数字的7位平方数#include<math.h>^include<stdio.h>voidmain(){intk,叫n,t,f[10];longa,b,c,d,w;n=0;b=sqrt(2356789);c=sqrt(9876532);for(a=b;a<=c;a++){d=a*a;w=d;//{d=a*a;w=d;//确保d为平方数for(k=0;k<=9;k++)f[k]=O;while(w>0){m=w%10;f[m]++;w=w/10;}for(t=0,k=l;kく=9;k++)if(f[k]>l)t=lJ 〃测试三个平方数是否有重复数字if(t=O&&f[0]+f[l]+f[4]==0)/Z测试平方数中没有数字0,1,4{n++;printf("%2d:",n);printf(，z%ld=%ld2\n",d,a);printff共可组成%d个没有重复数字的7位平方数.'n",n);

2-6写出例2-2中对称方阵的完整程序,并运行程序。对称方阵程序:Sinclude<stdio.h>voidmainO{inti,j,n,a[30][30]：printf("请确定方阵阶数Sinclude<stdio.h>voidmainO{inti,j,n,a[30][30]：printf("请确定方阵阶数n:scanf&n);for(i=l;i<=n;i++)for(j=l;j<=n;j++){if(i+j<=n+l&&i〈=j)a[i][j]=(n+l)/2-i+l;if(i+j<n+l&&i>j)a[i][j]=(n+l)/2-j+l;if(i+j>=n+l&&i>=j)a[i][j]=i-n/2;if(i+j>n+l&&i<j)a[i][j]=j-n/2;ヽ,/Z方阵上部元素赋值/Z方阵左部元素赋值////方阵ド部元素赋值方阵右部元素赋值printf("%d阶对称方阵为:\n",n);for(i=l;i<=n;i++)输出对称方阵{for(j=l;j<=n;j++) //输出对称方阵printf(*%3d*,a[i][j]);printf("\n");2-7四则运算式把数字1,2 9这9个数字填入以下含加减乘除的综合运算式中的9个口中,使得该式成立要求数字1,2 9这9个数字在各式中都出现一次且只出现一次,且约定数字“『‘不出现在数式的一位数中(即排除各式中的各个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(l-9)的个数。若某ーf(x)不为1,不满足数字1,2,...,9这九个数字都出现一次且只出现一次,标记t=l.若所有f(x)全为1,满足数字1,2,...,9这九个数字都出现一次且只出现一次,保持标记t=0,则输出所得的完美综合运算式。设置n统计解的个数。(2)程序实现/Z四则运算式ttinclude<stdio.h>voidmain(){intx,y,t,k,a,b,c,d,e,n=0;intm[6],f[11];for(a=12;a<=98;a++)for(b=2;b<=9;b++)for(c=123;c<=987;c++) /Z对a,b,c,d实施枚举for(d=2;d<=9;d++){x=c/d;e=a*b+x;if(c!=x*dIe>100)continue;m[l]=a;m[2]=c;m[3]=e;m[4]=b;m[5]=d;for(x=0;x<=9;x++)f[x]=0;for(k=l：k<=5;k++){y=m[k];while(y>0){x=y%10;f[x]=f[x]+l：y=(y-x)/10： //分离数字f数组统计for(t=0,x=l;x<=9;x++)if(f[x]!=l){t=l;break;}/Z检验数字0—9各只出现一次if(t==0) /Z输出ー个解,用n统计个数{n++;printf(*%2d:%2d*%ld+%3d/%1d-%2d=0\n”,n,a,b,c,d,e)))printf("n或d.\n",n);2-8合数世纪探求定义ー个世纪的100个年号中不存在ー个素数,BP100个年号全为合数的世纪称为合数世纪。探索最早的合数世纪。(1)设计要点应用穷举搜索,设置a世纪的的50个奇数年号(偶数年号无疑均为合数)为b,用k试商判别b是否为素数，用变量s统计这50个奇数中的合数的个数。对于a世纪，若s=50,即50个奇数都为合数,找到a世纪为最早的合数世纪，打印输出后退出循环结束。(2)合数世纪程序设计//合数世纪探求^include<stdio.h>#include<math.h>voidmain(){longa,b,k;ints,x;a=ljwhile(1){a++;s=0; /Z检验a世纪for(b=a*100-99;b<=a*100-l;b+=2) /Z穷举a世纪奇数年号b{x=0;for(k=3;k<=sqrt(b);k+=2)if(b%k=O){x=l;break;}if(x==0)break;/Z当前为非合数世纪时,跳出循环进行下世纪的探求s=s+x; //年号b为合数时,x=l,s增1if(s==50) //s=50,即50个奇数均为合数{printf("最早出现的合数世纪为%ld世纪!\n”,a);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+l,f+n］后结束:否则,作赋值f=m,为求下ー个素数作准备。如果在区间［c,d］中没有满足条件的解,则作赋值：c=d+2,d=c+10000J继续试商下去,直到找出所要求的解。(2)程序实现/Z求最小的连续n个合数#include<stdio.h>#include<math.h>voidmain(){longc,d,f,m,j;intt,n;printf("求最小的n个连续合数.'n");printf(・请输入n:");scanf("%d",&n);c=3;d=c+10000;f=3;while(l){for(m=c;m<=d;m+=2){for(t=0,j=3;j<=sqrt(m);j+=2)if(irt%j=0) /Z实施试商{t=l;break;}if(t==0&&m-f>n)/Z满足条件即行输出{printf("最小的%d个连续合数区间为:",n);printf("［%ld,%ld!〇'n",f+1,f+n);getchO;return;if(t==O)f=m; //每求出ー个素数m后赋值给fif(m>d){c=d+2;d=c+10000;}/Z每ー轮试商后改变c,d转下ー轮2-10和积9数字三角形求解和为给定的正整数s(s245)的9个互不相等的正整数填入9数字三角形,使三角形三边上的4个数字之和相等(si)且三边上的4个数字之积也相等(s2)。图2-79数字三角形(1)求解要点。把和为s的9个正整数存储于b数组b(l),…，b(9)中,分布如下图所示。为避免重复,不妨约定三角形中数字’’下小上大、左小右大'即b(1)くb(7)<b(4)且b(2)<b(3)且b(6)<b(5)且b⑼<b⑻。b4TOC\o"1-5"\h\zb3 b5b2 b6blb9 b8 b7图2-8b数组分布示意图可以根据约定对b(l)、b(7)和b(4)的值进行循环探索,设置:b(D的取值范围为1〜(S-2D/3(因其他6个数之和至少为21)。b(7)的取值范围为b(1)+1〜(s-28)/2。b(4)的取值范围为b(7)+1〜(s-36)。同时探索判断步骤如下:1)若(s+b(l)+b(7)+b(4))%3W0,则继续探索:否则，记sl=(s+b(D+b(7)+b(4))/3。2)根据约定对b(3)、b(5)和b(8)的值进行探索,设置:b(3)的取值范围为(sl-b(l)-b(4))/2+l-sl-b(l)-b(4).b(5)的取值范围为(sl-b(4)-b(7))/2+l-sl-b(4)-b⑺。b(8)的取值范围为(sl-b(l)-b(7))/2+l〜sl-b(l)-b(7))。同时根据各边之和为sL计算出b(2)、b(6)和b(9)：b(2)=sl-b(l)-b(4)-b(3)b(6)=s1-b(4)-b(5)-b(7)b(9)=sl-b(l)-b(7)-b(8)3)若b数组存在相同正整数,则继续探索。4)设s2=b(l)*b(2)*b(3)*b(4),若另两边之积不为s2,则继续探索:否则探索成功,打印输出结果,接着继续探索直到所有数字组探索完毕为止。(2)9数字三角形求解程序设计。//9数字三角形求解#include<stdio.h>#includeくmath.h>voidmain()intk,j,t,s,si,s2,n,b[10];printf(〃请输入正整数s:〃)；scanf(*%d*,&s);n=0;for(b[l]=l;b[l]<=(s-2l)/3;b[l]++)for(b[7]=b[l]+l;b[7]<=(s-28)/2;b[7]++)for(b[4]=b[7]+l;b[4]<=s36;b[4]++)if((s+b[l]+b[4]+b[7])%3!二〇)continue;sl=(s+b[l]+b[4]+b[7])/3;for(b[3]=(sl-b[l]-b[4])/2+l;b[3]<sl-b[l]-b[4];b[3]++)for(b[5]=(sl-b[4]-b[7])/2+l;b[5]<sl-b[4]-b[7];b[5]++)for(b[8]=(sl-b[l]-b[7])/2+l;b[8]<sl-b[l]-b[7];b[8]++)b[2]=sl-b[l]-b[4]-b[3]：b[6]=sl-b[4]-b[7]-b[5];b[9]=sl-b[l]-b[7]-b[8];t二〇;for(k=l;k<=8;k++)for(j=k+l;j<=9;j++)if(b[k]=b[j]){t=l;k=8;break;}if(t==l)continue;s2=b[l]*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(*%3d：%2d”,n,b[l]);for(k=2;k<=9;k++)printf(",%2d”,b[k]);printf(共%d个解。,n);习题33-1递推求解b数列已知b数列定义:ム=1,ら=2,b„=3b”i-b吁2(n>2)递推求b数列的第20项与前20项之和。解:#include<stdio.h>voidmain(){intk,n;longb[3000],s;printf(・请输入n:");scanf("%d",&n);b[l]=l;b[2]=2;s=3;for(k=3;k<=n;k++){b[k]=3*b[k-l]-b[k-2];s+=b[k];printfCb(%d)=%ld\n”,n,b[n]);printf("s=%ld\n”,s);3-2双关系递推数列集合M定义如下:leAfxeM=>2x+leM,3x+leAf3)再无别的数属于M试求集合M元素从小到大排列的第2011个元素与前2011个元素之和。解：(1)设计要点设n个数在数组mヰ12x+l与3x+!均作为ー个队列,从两队列中选一排头(数值较小者)送入数组m中。所谓“排头”就是队列中尚未选入m的最小的数(下标)。这里用p2表示2x+l这一列的排头的下标,用P3表示3x+!这一列的排头的下标。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)+l;p2++;p3++;/Z为避免重复项,P2,p3均须增1(2)程序设计/Z双关系递推ttinclude<stdio.h>voidmain(){intn,p2,p3,i;longs,m[3000];m[l]=l;s=l;p2=l;p3=l; //排头p2,p3赋初值printf(・请输入n:");scanf("%d",&n);for(i=2;i<=n;i++)if(2*m[p2]<3*m[p3]){m[i]=2*m[p2]+l;s+=m[i];p2++;else{m[i]=3*m[p3]+l;s+Rn[i];if(2*m[p2]=3*m[p3])p2++;/Z为避免重复项,P2须增1p3++;printf(*m(%d)=%ld\nw,n,m[n]);printf("s=%ld\n*,s);3-3多嘉序列设x,y,z为非负整数,试计算集合M={2\3',5:|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=l;

在k循环中通过比较赋值:当a<b且a<c时,由赋值f[k]=a确定为序列的第k项;然后a=a*2,即a按递推规律乘2,为后・・轮比较作准备;当bくa且bくc时,由赋值f[k]=b确定为序列的第k项;然后b=b*3,即b按递推规律乘3,为后ー轮比较作准备。当c<a且cくb时，由赋值f[k]=c确定为序列的第k项;然后c=c*5,即c按递推规律乘5,为后ー轮比较作准备。递推过程描述:5,为后ー轮比较作准备。递推过程描述:a=2;b=3;c=5;for(k=2;k<=n#++){if(a<b&&a<c){f[k]=a;a=a*2;}elseif(b<a&&b<c){f[k]=b;b=b*3;}else{f[k]=c;c=c*5;})在这•算法中,变量a,b,c是变化的,/Z为递推变量a,b,c赋初值//用a给f[用赋值//用b给f[用赋值〃用c给f[k]赋值分别代表2的幕、3的哥与5的基。上述递推算法的时间复杂度与空间复杂度均为0(n)。(2)多哥序列程序实现//多某序列求解#include<stdio.h>voidmain(){intk,m,t,p2,p3,p5;doublea,b,c,s,f[100];printf 求数列的第m项与前m项和,请输入m:");scanf("%d",&m);f[l]=l;p2=0;p3=0;p5=0;a=2;b=3;c=5;s=l;for(k=2;k<=m;k++){if(a<b&&a<c)scanf("%d",&m);f[l]=l;p2=0;p3=0;p5=0;a=2;b=3;c=5;s=l;for(k=2;k<=m;k++){if(a<b&&a<c){f[k]=a;a=a*2;t=2;p2++;)elseif(b<a&&b<c){f[k]=b;b=b*3;t=3;p3++;////用2的裏给f[k]赋值t=2表示2的界,p2为指数////用3的事给f[k]赋值t=3表示3的事,p3为指数else{f[k]=c;c=c*5; /Z用5的累给f[k]赋值t=3：p5++J 〃t=5表示5的幕,p5为指数s+=f[k];printfC数列的第%d项为:%.Of*,m,f[m]);if(t==2) /Z对输出项进行标注printf(*(2%d)\n*,p2);elseif(t=3)printf(*(3%d)\n”,p3);elseprintf(*(5"%d)\n*,p5);printf("数列的前%d项之和为:%.Of\n*,m,s);3-4双累积序列的和由集合M={23|xZ0,yZ0}元素组成的复合幕序列,求复合基序列的指数和x+yWn(正整数n从键盘输入)的各项之和s=す2,3ゝxZ0,.y20(1)设计要点归纳求和递推关系:当x+y=0时,s(l)=l；当x+y=l时，s(l)=2+3；当x+y=2时，s(2)=2ゝ2X3+3?=2*s(1)+32当x+y=3时,s(3)=2”X3+2X32+33=2*s(2)+33一般地,当x+y=k时，s(k)=2*s(k-1)+3"即有递推关系:s(k)=2*s(k)+3k其中3k可以通过变量迭代实现。这样可以省略数组,简化为一重循环实现复合箱序列求和。(2)程序实现/Z复合幕序列求和#include<stdio.h>voidmain(){intk,n;longsum,t,s[100];printf("请输入幕指数和至多为n:");scanf("%d",&n);t=l;s[0]=l;sum=l;for(k=l;kCn#++){t=t*3; 〃迭代得t=3~ks[k]=2*s[k-l]+t; /Z实施递推sum=sum+s[k];)printf("某指数和至多为%d的黑序列之和为:%ld\n”,n,sum);3-5粒子裂变核反应堆中有a和B两种粒子,每秒钟内ー个a粒子可以裂变为3个B粒子,而ー个。粒子可以裂变为1个a粒子和2个B粒子。若在t=0时刻的反应堆中只有一个a粒子,求在t秒时反应堆裂变产生的a粒子和P粒子数。TOC\o"1-5"\h\z1.算法设计设在t秒时a粒子数为f(t),B粒子数为g(t),依题可知:g(t)=3f(t-l)+2g(t-l) (1)f(t)-g(t-l) (2)g(0)=0,f(0)=l由(2)得f(tT)=g(t-2) (3)将式(3)代入(1)得g(t)=2g(t-l)+3g(t-2)(t22) (4)g(0)=0,g(l)=3 (5)以递推关系(4)与初始条件(5)完成递推。2.粒子裂变C程序设计/Z粒子裂变#include<stdio.h>voidmain(){intt,k;longg[100];printf(*inputt:");scanf("%d",&t);g[0]=0;g[l]=3; //确定初始条件for(k=2;k<=t;k++)g[k]=2*g[k-l]+3*g[k-2]; /Z完成递推printf(*%d秒时反应堆中P粒子数为:％Id\n*,t,g[t]);printf(,%d秒时反应堆中a粒子数为:％ld\n*,t,g[t-l]);3-6m行n列逆转矩阵

图3-4所示为4行5列逆转矩阵。114131211TOC\o"1-5"\h\z2 15 20 19 103 16 17 18 94 5 6 7 8图3-44行5列逆转矩阵试应用递推设计构造并输出任意指定m行n列逆转矩阵。解:对输入的m,n,取c=min(m,n),计算数字矩阵的圈数d=(c+l)/2。设置i(l-d)循环,从外圈至内圈,分4边进行递推赋值。程序设计://mXn数字逆转矩阵#include<stdio.h>voidmain(){inti,j,c,d,h,v,m,n,s,a[30][30];printfCm行n列矩阵,请确定m,n:つ;scanf(*%d,%d",&m,&n);c=n;if(m<n)c=m;d=(c+l)/2;s二〇;v=0;for(i=l;i<=d;i++){for(i=l;i<=d;i++){v++;for(h=i;h<=m-i;h++){s++;a[h][v]=s;}for(v=i;v<=n-i;v++){s++;a[h][v]=s;Jfor(h=m+l-i;h>i;h--){s++;a[h][v]=s;if(s=m*n){h=i;break;})for(v=n+l-i;v>i;v-){s++;a[h][v]=s;//从外至内第d圈赋值/Zi圈的左列从上至下递增/Zー圈的下行从左至右递增/Zー圈的右列从下至上递增/Zー圈的上行从右至左递增if(s=m*n){v=i;break;})}printf("%d行%d列旋转矩阵为:\n”,m,n);for(i=l;i<=m;i++){for(j=l;j<=n;j++) //按四行n列输出矩阵printf("%4d",a[i][j]);3-7猴子吃桃有一猴子第1天摘ド若干个桃子,当即吃了一半,还不过瘾,又多吃了1个。第2天早上又/