2011-2013年湖南理工学院程序设计试题(5)

由约定知a

3）另外，原三元不定方程为分数形式，转化为以下的整数形式 (a+b+c)*(b*c-a*c-a*b)=a*b*c

在枚举循环中应用以上整式进行筛选是可行的。 （2）枚举描述 // 解不定方程 #include #include void main()

{ double a,b,c,s,x,y,m; printf(\请输入正整数x,y: \scanf(\m=0;

for(a=x;a<=y-2;a++) // 设计三重循环实现枚举 for(b=a+1;b<=y-1;b++) for(c=b+1;c<=y;c++) { s=a+b+c;

if((b*c-a*b-a*c)*s!=a*b*c) // 应用方程式实施筛选 continue;

m++; // 统计解的个数并输出解

printf(\} }

请输入正整数x,y: 400,1000 1: a=408,b=984,c=986

请输入正整数x,y: 1000,2500 1: a=1015,b=2436,c=2465 2: a=1020,b=2460,c=2465 3: a=1026,b=2470,c=2484

6 递推序列

设集合M定义如下: (1) 1∈M

(2) x∈M => 2x+1∈M,5x-1∈M (3) 再无其它的数属于M。

试求集合M元素从小到大排列所得序列的第n项与前n项之和。 输入正整数n（n<10000），输出序列的第n项与前n项之和。 数据测试： （1） n=100 （2） n=2013 参考解答： 1. 枚举设计

（1）枚举设计要点

设递推序列的第i项为m(i)，显然m(1)=1。

设置枚举变量k: k从2开始递增1取值，若k可由已有的项m(j)（j

// 2x+1,5x-1递推序列枚举判别 #include void main()

{ int n,i,j; long k,s,m[10000]; printf(\请输入n：\scanf(\m[1]=1;s=1;

k=1;i=1; // 确定初始值 while(i

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

if(k==2*m[j]+1 || k==5*m[j]-1)

{ i++;m[i]=k; // 判断k为递推项，给m数组赋值 s=s+k; break; } }

printf(\}

２. 递推设计

(１) 递推设计要点

该题有2x+1,5x-1两个递推关系，设置数组m(i)存储M元素从小到大排列序列的第i项，显然m(1)=1，这是递推的初始条件。 同时设置两个队列： 2*m(p2)+1, p2=1,2,3,? 5*m(p5)-1, p5=1,2,3,?

这里用p2表示2x+1这一队列的下标，用p5表示5x-1这一队列的下标。

从两队列中选一排头，通过比较选数值较小者送入数组m中。所谓“排头”就是队列中尚未选入m的最小的下标。

若2*m(p2)+1<5*m(p5)-1, 则m(i)=2*m(p2)+1;下标p2增1； 若2*m(p2)+1>5*m(p5)-1, 则m(i)=5*m(p5)-1;下标p5增1；

若2*m(p2)+1=5*m(p5)-1, 则m(i)=5*m(p5)-1;下标p2与p5同时增1。 (２) 递推描述 // 双关系递推 #include void main()

{long n,p2,p5,i,s,m[10000]; printf(\请输入n：\

scanf(\m[1]=1;s=1;

p2=1;p5=1; // 排头p2,p5赋初值 for(i=2;i<=n;i++)

{ if(2*m[p2]+1<5*m[p5]-1) { m[i]=2*m[p2]+1;p2++;} else

{ m[i]=5*m[p5]-1;

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

s+=m[i]; // 实现求和 }

printf(\}

请输入n：100

m(100)=1444,s=55021

请输入n：2013

m(2013)=157879,s=128116164 实训6. 振动数列 已知递推数列：

a(1)=1，a(2*i)=a(i)+2，a(2*i+1)=a(i+1)-a(i)，（i＝1,2,?）

数列平台定义：数列中相连两项或相连两项以上相等，则称为一个平台。 数列波峰定义：

(1) 若某项同时大于其前、后相邻项；

(2) 若存在相连若干项相等，这些项同时大于其相邻前项与后项。

例如相连的某3项为4,7,5,则为一个波峰；相连的某4项为-1,3,3,2,也为一个波峰，其中3,3为一个平台。

对指定的正整数m,n（m

测试数据： m=1000,n=2014 7 子数对最大值 TUIJIAN

设b是正整数a去掉一个数字后的正整数，对于给出的正整数n，如果a+b=n（n>10），则称正整数对a,b为整数n的一组子数对。 例如，n=34时，有3组子数对：（27,7）,(31,3),(32,2)。 试求给定区间[x,y]中整数的子数对组数的最大值。

输入区间x,y (10

（1） x=100,y=999 （2） x=2013,y=3000 参考解答： 1. 设计要点

（1）根据给出的n设置整数a的枚举循环，对每一个a,计算b=n-a。

对于给定的n，确定枚举a的取值范围必须慎重：范围太小，可能造成遗解；范围太大，造

成无效操作太多。

注意到b≥1（有可能取1）,因而取a循环终点为n-1。 由a>b，a+b=n可知a>n/2，因而取n/2为a循环起点。

（2）设计赋值表达式d=a/(t*10)*t+a%t; 生成a的去数字数。

事实上，当t=1时，表达式为d=a/10; d即为a的去个位数字后的数； 当t=10时，表达式为d=a/100*10+a; d即为a的去十位数字后的数； ??

依此类推，设a是一个m位数，应用t可实现生成a的m个去数字数。这些去数字数逐个与b=n-a进行比较并决定取舍。 2. 枚举描述 // 整数对

#include void main()

{ int a,b,c,n,k,j,t,x,y,max; long p[100],q[100];

printf(\请输入整数x,y: \max=0;

for(n=x;n<=y;n++) {k=0;

for(a=n/2;a<=n-1;a++) { b=n-a;t=1;

while(a>t) // 应用t控制去数字循环次数 { d=a/(t*10)*t+a%t; // d为a的一个去数字数 if(d==b) { k++;

p[k]=a*10000+b; }

t=t*10; } }

if(k>max) { max=k;c=a;

for(j=1;j<=k;j++) q[j]=p[j]; } }

printf(\最大值为%d\\n\printf(\如%d：\for(j=1;j<=max;j++)

printf(\}

请输入整数x,y: 100,999 最大值为5

如202：(151,51),(184,18),(186,16),(191,11),(201,1) 请输入整数x,y: 2013,9999

最大值为7

如2014：(1507,507),(1827,187),(1831,183),(1832,182),(1857,157), (1907,107),(2007,7)

8 统计n!中数字“0”的个数

设n为正整数，定义n!=1×2×3×?×n，统计n!中数字“0”的个数及其尾部连续“0”的个数。 输入正整数n（n<10000）,输出n!中数字“0”的个数及其尾部连续“0”的个数。数据测试： （1） n=1000 （2） n=2013 参考解答：

解：n规模较大，n!的位数也就相应地大，设计a数组存储n!的各位数字，a[1]存储个位数字，a[2]存储十位数字，余类推。 1) 算法设计要点

模拟整数竖式乘运算实施精确计算。

通过常用对数累加和s=lg2+lg3+?+lgn确定n!的位数m=s+1,即a数组元素的个数。设置2重循环，模拟整数竖式乘法实施各数组元素的累乘： 乘数k：k=2,3,?,n；

累乘积各位a[j]：j=1,2,?,m； 实施乘运算：

t=a[j]*k+g; // 第j位乘k，g为进位数

a[j]=t; // 乘积t的个位数字存于本元素 g=t/10; // 乘积t的十位以上数字作为进位数 计算n!完成后，在j（1——m）循环中通过 if(a[j]==0) p++;

统计n!中数字“0”的个数p。

应用q=1; while(a[q]==0) q++;统计尾部连续“0”的个数q-1。 2）程序设计

// 统计n!中0的个数及尾部连续0的个数（n<10000） #include #include void main()

{ int g,j,k,m,n,p,q,t,a[40000];double s; printf(\请输入正整数n(n<10000): \scanf(\输入n s=0;

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

s+=log10(k); // 对数累加确定n!的位数m

m=(int)s+1;；for(k=1;k<=m;k++)；a[k]=0;//数组清零；a[1]=1;g=0;；for(k=2;k<=n;k++)；for(j=1;j<=m;j++)；{t=a[j]*k+g;//数组累乘并进位a[j；g=t/10;//统计0个数；p=0;；for(j=m;j>=1;j--)；if(a[j]==0)p+ m=(int)s+1;

for(k=1;k<=m;k++) a[k]=0; // 数组清零 a[1]=1;g=0;

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

for(j=1;j<=m;j++)

{ t=a[j]*k+g; // 数组累乘并进位 a[j]=t; g=t/10; //统计0个数 } p=0;

for(j=m;j>=1;j--)

if(a[j]==0) p++; // p统计n!中0的个数 q=1;

while(a[q]==0) q++; // q尾部连续0的个数 printf(\输出结果 } 数据测试：

请输入正整数n(n<10000): 1000 p=472,q=249

请输入正整数n(n<10000): 2013 p=1032,q=501