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

WORD格式可编辑

差。若某相邻的两素数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数字三角形,使三角

专业知识分享

WORD格式可编辑

形三边上的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数字三角形求解程序设计。

专业知识分享

WORD格式可编辑

// 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个解。\}

专业知识分享

WORD格式可编辑

习题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))

专业知识分享

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4