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

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

习题解答提要

习题1

1-1分数分解算法描述

把真分数a/b分解为若干个分母为整数分子为“1”的埃及分数之和：

(1)寻找并输出小于a/b的最大埃及分数1/c；

(2)若c>900000000,则退出；

(3)若CW900000000,把差a/bT/c整理为分数a/b,若a/b为埃及分数，则输

出后结束。

(4)若a/b不为埃及分数，则继续⑴、(2)、(3)。

试描述以上算法。

解：设二)(这里int(x)表示取正数x的整数)，注意到+有

aa

aIa(d+\)-b

—="+----------------------

bd+Ib(d+1)

算法描述：令C=d+1,则

input(a,b)

while(l)

{c=int(b/a)+l;

if(c>900000000)return;

else

{print(l/c+);

a=a*c-b;

b=b*c;〃a,b迭代，为选择下一个分母作准备

if(a=l)

{print(l/b)jreturn;}

)

)

1-2求出以下程序段所代表算法的时间复杂度

(1)m=0;

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

for(j=k;j>=l;j­)

m=m+j;

解：因s=1+2+•­•+n=n(n+1)/2

时间复杂度为05)。

(2)m=0;

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

for(j=l;j<=k/2;j++)

m=m+j;

解：设n=2u+l,语句nFm+1的执行频数为

s=1+1+2+2+3+3+…+u+u=u(u+l)=(n-l)(n+l)/4

设n=2u,语句m初+1的执行频数为

s=1+1+2+2+3+3+,,,+u=uJ=n2/4

时间复杂度为0日)。

(3)t=l;m=0;

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)!).

(4)for(a=l;a<=n;a++)

{s=0;

for(b=a*l00-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)

printf(^%ld\n，z,a);break;}

}

解：因a循环n次；对每一个a,b循环50次；对每一个b,k循环2次。因而k循环

体的执行次数s满足

时间复杂度为0(〃VT)o

1-3若p(n)是n的多项式，证明：0(log(p(n)))=0(logo)o

证：设m为正整数，p(n)=alXnm+a2Xnn11+---+an)Xn,

取常数c>mal+(mT)a2+…+am,则

log(p(n))=malXlogn+(mT)a2Xlogn+…二(mal+(mT)a2+…)Xlogn

<clogn

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

1-4构建对称方阵

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

o110

1022201

1203021

1230321

1203021

1022201

010

图1-57阶对称方阵

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

解：这是•道培养与锻炼我们的观察能力与归纳能力的案例，一个•个元素枚举赋值显

然行不通，必须全局着眼，分区域归纳其构造特点，分区域枚举赋值。

(1)设计要点

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

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

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

i+j<n+l/

i+j<n+?><l+j>n+l

图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=j||i+j==n+l)

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

if(i+j<n+l&&i<j)

a[i][j]=i;//方阵上部元素赋值

if(i+j<n+l&&i>j)

a[i][j]=j;//方阵左部元素赋值

if(i+j>n+l&&i>j)

a[i][j]=n+l-i;//方阵下部元素赋值

if(i+j>n+l&&i<j)

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

}

printf("%d阶对称方阵为：\n”,n);

for(i=l;i<=n;i++)

{for(j=l;j<=n;j++)//输出对称方阵

printf("%3d",a[i][j]);

printf("\n");

)

)

1-5据例1-2的算法，写出求解n个“1”组成的整数能被2011整除的程序。

修改程序，求出n至少为多大时，n个“1”组成的整数能被2013整除？

解：程序为

#include<stdio.h>

voidmainO

{inta,c,p,n;

p=2011;

c=llll;n=4;//变量c与n赋初值

while(c!=0)//循环模拟整数竖式除法

{a=c*10+l;

c=a%p;

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

）

printf（w由%d个1组成的整数能被%d整除。\n”,n,p）;

)

习题2

2-1解不等式

设n为正整数，解不等式

I11

2010<I+-------------+-------------------------++---------------------------------<2011

1+1/21+I/2+1/3I+1/2+--+|/«

解：上下限一般为键盘输入的a,b。

//解不等式：a<l+l/(1+1/2)+...+1/(1+1/2+...+l/n)<b

Sinclude<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(z，\n满足不等式的正整数n为：%ldWnW%ld\n”,c,d);

)

2-2韩信点兵

韩信在点兵的时候，为了知道有多少个兵，同时又能保住军事机密，便让士兵排队报数。

按从1至5报数，记下最末一个士兵报的数为1；

再按从1至6报数,记下最末一个士兵报的数为5；

再按1至7报数,记下最末一个报的数为4；

最后按1至11报数,最末一个士兵报的数为10。

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

1.求解要点

设兵数为X,则X满足下述的同余方程组：

x=5y+l即x=l(mod5)

x=6z+5x=5(mod6)

x=7u+4x=4(mod7)

x=llv+10x=10(mod11)

其中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=l与x%7=4两

个条件即可。

这样可算得满足条件的最小整数x即点兵的数量。

2.程序实现

//韩信点兵

#include<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不是b的因数，则k增1后继续。

若上述试商完成后说明i有一个大于sqrt(i)的因数，要补上该因数。

若试商后b还是原来的i,则i是素数。

〃质因数分解乘积形式

#includez/math.h"

ttinclude<stdio.h>

voidmain()

{longintb,i,k,m,n,w=0;

printf中整数分解质因数(乘积形式)八n");

printf("请输入m,n:");

scanf("%ld,%ld”,&m,&n);

for(i=m;i〈=n;i++)//i为待分解的整数

{printf("%1d=",i);

b=i;k=2;

while(k<=sqrt(i))//k为试商因数

{if(b%k==O)

(b=b/k;

if(b>l)

{printf("%ld*”,k);

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

)

if(b==l)printf("%ld\n”,k);

k++;

)

if(b>l&&b<i)

printfC%ld\n?z,b);//输出大于i平方根的因数

if(b=i)

{printf("(素数!)\n");w++;}//b=i,表示i无质因数

}

}

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

定义和:

s(n)=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〈=2011,当n为多大时，s(n)最大。

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

解：代数和式中各项的符号并不是简单的正负相间，而是随着构成素数而改变。因而在

求和之前应用“试商判别法”对第k个奇数2k-1是否为素数进行标注：

若2k-l为素数,标注a[k]=l；

否则,若2kT不是素数，a[k]=0。

设置k循环(1——n),循环中分别情况求和：

若a[k]+a[k+l]>=l,即(2k-l)与(2k+l)中至少有一个素数，实施"+”；

否则,若a[k]+a[k+l]=0,即(2kT)与(2k+l)中没有素数，实施

同时，设置最大值变量smax,最小值变量smin。

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

smin比较确定最小值，同时记录此时的项数k2。

//基于素数的整数和

#include<stdio.h>

#include<math.h>

voidmain()

{intt,j,n,k,kl,k2,a[3000];longs,smax,smin;

printf(z/请输入整数n:〃)；

scanf&n);

for(k=l;k<=n+l;k++)a[k>0;

for(k=2;k<=n+l;k++)

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

if((2*k-l)%j==0)

{t=l;break;}

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

}

s=3;smax=0;smin=s;

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

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

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

else

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

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

if(s〈smin){smin=s;k2=k;}//比较求最大值smin

)

printfCs(%d)=%ld\nz，,n,s);

printf(〃当k=%d时s有最大值:%ld\n”,kl,smax);

printf(〃当k=%d时s有最小值：%ld\n，z,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中各个数字的个数。如果f[3]=2,即平方数d中有2个“3”。

检测若f[k]〉l(k=O—9),说明d中存在有重复数字，返回。

在不存在重复数字的情形下，检测若f[0]+f[l]+f[4]=0,说明7位平方数d中没有数

字字”,“4”，d满足题意要求,打印输出。

//组成没有重复数字的7位平方数

#include<math.h>

ttinclude<stdio.h>

voidmainO

{intk,m,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为平方数

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=l;//测试三个平方数是否有重复数字

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

{n++;

printf(z，%2d:〃，n);

printf(z，%ld=%ld2\n〃,d,a);

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

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

对称方阵程序：

^include<stdio.h>

voidmain()

{inti,j,n,a[30][30];

printf("请确定方阵阶数n:");

scanf("机T,&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&ai>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;//方阵右部元素赋值

)

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个口中，使得该

式成立

□□*口+口口口+口-口口=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=l.

若所有f(x)全为1,满足数字1,2,...,9这九个数字都出现一次且只出现一次，保持标

记t=0,则输出所得的完美综合运算式。

设置n统计解的个数。

(2)程序实现

//四则运算式

#include<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++)//对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[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;}//检验数字0—9各只出现一次

if(t=O)//输出一个解，用n统计个数

{n++;

printf(z，%2d:%2d*%ld+%3d/%ld-%2d=0\n”,n,a,b,c,d,e);

)

)

printf(/zn=%d.\n",n);

)

2-8合数世纪探求

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

世纪。

探索最早的合数世纪。

(1)设计要点

应用穷举搜索，设置a世纪的的50个奇数年号(偶数年号无疑均为合数)为b,用k试商

判别b是否为素数，用变量s统计这50个奇数中的合数的个数。

对于a世纪，若s=50,即50个奇数都为合数，找到a世纪为最早的合数世纪，打印输

出后退出循环结束。

(2)合数世纪程序设计

//合数世纪探求

ttinclude<stdio.h>

^include<math.h>

voidmain()

{longa,b,k;ints,x;

a=l;

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=O)

{x=l;break;}

if(x=0)break;//当前为非合数世纪时，跳出循环进行下世纪的探求

s=s+x;//年号b为合数时，x=l,s增1

)

if(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,判别：

若则输出结果［f+1,f+n］后结束；

否则，作赋值f=m,为求下一个素数作准备。

如果在区间［c,d］中没有满足条件的解，则作赋值：c=d+2,d=c+10000,继续试商下去,

直到找出所要求的解。

(2)程序实现

//求最小的连续n个合数

ttinclude<stdio.h>

ttinclude<math.h>

voidmain()

{longc,d,f,m,j;

intt,n;

printfC求最小的n个连续合数.\n");

printf("请输入n:");

scanf&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(m%j=0)//实施试商

{t=l;break;}

if(t-0&&m-f>n)//满足条件即行输出

{printf("最小的刎个连续合数区间为:",n);

printfC［%ld,%ld］»\n”,f+1,f+n);

getchO;return;

)

if(t==O)f=m;〃每求出一个素数m后赋值给f

)

if(m>d)

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

)

)

2-10和积9数字三角形

求解和为给定的正整数s(s245)的9个互不相等的正整数填入9数字三角形，使三角

形三边上的4个数字之和相等(si)且三边上的4个数字之积也相等(s2)。

(1)求解要点。

把和为s的9个正整数存储于b数组b(l),…，b(9)中，分布如下图所示。为避免重复,

不妨约定三角形中数字“下小上大、左小右大”,即b(l)<b⑺<b(4)且b(2)<b(3)且b(6)<b⑸

且b(9)<b(8)。

b4

b3b5

b2b6

blb9b8b7

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

可以根据约定对b(l)、b(7)和b(4)的值进行循环探索，设置：

b(l)的取值范围为1〜(S-2D/3(因其他6个数之和至少为21)。

b(7)的取值范围为b⑴+1〜(s-28)/2。

b(4)的取值范围为b⑺+1〜(s-36)。

同时探索判断步骤如下：

1)若(s+b(l)+b(7)+b(4))%3W0,则继续探索;否则，记sl=(s+b(l)+b(7)+b(4))/3。

2)根据约定对b(3)、b(5)和b(8)的值进行探索，设置：

b⑶的取值范围为(sl-b(l)-b(4))/2+l-sl-b(l)-b⑷。

b(5)的取值范围为(sl-b(4)-b(7))/2+l-sl-b(4)-b⑺。

b⑻的取值范围为(sl-b(l)-b(7))/2+l〜sl-b(l)-b⑺)。

同时根据各边之和为si,计算出b(2)、b⑹和b⑼:

b(2)=sl-b(l)-b(4)-b(3)

b(6)=sl-b(4)-b(5)-b(7)

b(9)=sl-b(l)-b⑺-b(8)

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

4)设s2=b⑴*b(2)*b(3)*b⑷,若另两边之积不为s2,则继续探索;否则探索成功,

打印输出结果，接着继续探索直到所有数字组探索完毕为止。

(2)9数字三角形求解程序设计。

//9数字三角形求解

#include<stdio.h>

#include<math.h>

voidmainO

{

intk,j,t,s,si,s2,n,b[10];

printf(/z请输入正整数s：〃)；

scanf&s);

n=0;

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

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

for(b[4]=b[7]+l;b[4]<=s­36;b[4]++)

(

if((s+b[l]+b[4]+b[7])%3!=0)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=0;

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[l]*b[9]*b[8]*b[7]!=s2)continue;

n++;

printf(，z%3d：%2d，z,n,b[l]);

for(k=2;k<=9;k++)

printf(，z,%2d，z,b[k]);

printf(，zsl=%d,s2=%d\n”,si,s2);

)

}

printf("共%d个解。〃,n);

}

习题3

3-1递推求解b数列

已知b数列定义：

b

i=I，匕=2,bn=3b…-b…(n>2)

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

解：

ttinclude<stdio.h>

voidmain()

{intk,n;longb[3000],s;

printf("请输入n:");

scanf&n);

b[l]=l;b[2]=2;s=3;

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

{b[k]=3*b[k-l]-b;Ik-2];

s+=b[k];

}

printf(z/b(%d)=%ld\n”,n,b[n]);

printf(z/s=%ld\n”,s);

)

3-2双关系递推数列

集合M定义如下：

1)1eM

2)xeA/=>2x+IeM.3x+1eM

3)再无别的数属于M

试求集合M元素从小到大排列的第2011个元素与前2011个元素之和。

解：(1)设计要点

设n个数在数组m中，2x+l与3x+l均作为一个队列，从两队列中选一排头(数值较小

者)送入数组m中。所谓“排头”就是队列中尚未选入m的最小的数(下标)。这里用p2表

示2x+l这一列的排头的下标，用p3表示3x+l这一列的排头的下标。

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

{m(i)=2*m(p2)+1;p2++;}

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

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

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

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

{m(i)=2*m(p2)+l;

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

}

(2)程序设计

//双关系递推

#include<stdio.h>

voidmain()

{intn,p2,p3,i;longs,m[3000];

p2=l;p3=l;//排头p2,p3赋初值

printf(/z请输入n:");

scanf&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+=m[i];

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

p3++;

)

printf(/zm(%d)=%ld\nz/,n,m[n]);

printf(z，s=%ld\n”,s);

3-3多哥序列

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

M\x>Q,y>Q,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,为后一轮比较作准备。

递推过程描述：

a=2;b=3;c=5;//为递推变量a,b,c赋初值

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

{if(a<b&&a<c)

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

elseif(b<a&&b<c)

{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的幕。

上述递推算法的时间复杂度与空间复杂度均为0(n)。

(2)多基序列程序实现

//多幕序列求解

ttinclude<stdio.h>

voidmain()

{intk,m,t,p2,p3,p5;

doublea,b,c,s,f[100];

printfC求数列的第m项与前m项和,请输入m:");

scanf&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;//用2的幕给f[k]赋值

t=2;p2++;//t=2表示2的基，p2为指数

)

elseif(b<a&&b<c)

{f[k]=b;b=b*3;//用3的藉给f[k]赋值

t=3;p3++;//t=3表示3的嘉，p3为指数

else

{fW=c;c=c*5;〃用5的哥给f[k]赋值

t=3;p5++;//t=5表示5的幕，p5为指数

}

s+=f[k];

)

printfC数列的第%d项为：%.Ofz/,m,f[m]);

if(t==2)//对输出项进行标注

printfC(2"%d)\n”,p2);

elseif(t-3)

printf("(3'%d)\n”,p3);

else

printfC(5"%d)\n”,p5);

printfC数列的前为d项之和为：%.Of\n，z,m,s);

)

3-4双幕积序列的和

由集合M..3,I,20.>2。；元素组成的复合幕序列，求复合幕序列的指数和x+yWn(正

整数n从键盘输入)的各项之和

s■Z2'3',x20,"0

(1)设计要点

归纳求和递推关系：

当x+y=0时，s(l)=l；

当x+y=l时，s⑴=2+3；

当x+y=2时，s⑵=2?+2X3+32*s(1)+32

当x+y=3时，s⑶=2*2?X3+2X32+3=2*s(2)+33

一般地，当x+y=k时，s(k)=2*s(k-l)+3k

即有递推关系：

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

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

和。

(2)程序实现

//复合嘉序列求和

ttinclude<stdio.h>

voidmainO

{intk,n;longsum,t,s[100];

printf(〃请输入基指数和至多为n:〃)；

scanf&n);

t=l;s[0]=l;sum=l;

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

{t=t*3;//迭代得t=3”k

s[k]=2*s[k-l]+t;//实施递推

sum=sum+s[k];

printf("新指数和至多为%d的幕序列之和为:%ld\n”,n,sum)

3-5粒子裂变

核反应堆中有a和0两种粒子，每秒钟内一个a粒子可以裂变为3个B粒子，而一个B

粒子可以裂变为1个a粒子和2个B粒子。若在t=0时刻的反应堆中只有一个a粒子，求在

t秒时反应堆裂变产生的a粒子和B粒子数。

1.算法设计

设在t秒时a粒子数为f(t),B粒子数为g(t),依题可知：

g(t)=3f(t-l)+2g(t-l)(1)

f(t)=g(t-l)(2)

g(O)=O,f(O)=l

由(2)得f(t-D=g(t-2)(3)

将式(3)代入⑴得

晨t)=2g(t-l)+3g(t-2)(t22)(4)

g(0)=0,g(l)=3(5)

以递推关系(4)与初始条件(5)完成递推。

2.粒子裂变C程序设计

//粒子裂变

#include<stdio.h>

voidmain()

{intt,k；longg[100];

printfCinputt:");

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];//完成递推

printfC%d秒时反应堆中B粒子数为:％ld\n",t,g[t]);

printf(z，%d秒时反应堆中a粒子数为:%Id\n”,t,g[tT]);

3-6ni行n列逆转矩阵

图3-4所示为4行5列逆转矩阵。

114131211

215201910

31617189

45678

图3-44行5列逆转矩阵

试应用递推设计构造并输出任意指定m行n列逆转矩阵。

解：对输入的叫n,取c初in(m,n),计算数字矩阵的圈数d=(c+l)/2。

设置i(l——d)循环，从外圈至内圈，分4边进行递推赋值。

程序设计：

//mXn数字逆转矩阵

#include<stdio.h>

voidmainO

{inti,j,c,d,h,v,m,n,s,a[30][30];

printf(，zm行n列矩阵，请确定m,n:〃)；scanf(〃％d,%d〃,&m,&n);

c=n;

if(m<n)c=m;

d=(c+l)/2;

s=0;v=0;

for(i=l;i〈=d;i++)//从外至内第d圈赋值

{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;}

for(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;

if(s=m*n){v=i;break;}

)

)

printf(〃%d行对列旋转矩阵为：\n〃,m,n);

for(i=l;i<=m;i++)

{for(j=l;j<=n;j++)//按m行n列输出矩阵

printf(〃%4d〃，a[i][j]);

printf("\n");

}

3-7猴子吃桃

有一猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了1个。第2天早

上又将剩下的桃子吃掉一半，又多吃了1个。以后每天早上都吃了前一天剩下的一半后又多

吃1个。到第10天早上想再吃时，见只剩下1个桃子了。

求第1天共摘了多少个桃子。

(1)求解要点

第1天的桃子数是第2天桃子数加1后的2倍，第2天的桃子数是第3天桃子数加1后

的2倍，…，一般地，第k天的桃子数是第k+1天桃子数加1后的2倍。设第k天的桃子数

是t(k),则有递推关系

t(k)=2*(t(k+l)+l)(k=l,2,…,9)

初始条件：t(10)=1

逆推求出t(l