源代码算法设计与分析实用教程习题参考解答

《算法设计与分析实用教程》参考解答

(各习题的算法设计与数据测试仅供参考)

习题1

1-1加减得1的数学游戏

西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于

1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。

例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1,需要做10次加减法计算。

设计算法，输入两个不同的正整数，输出得到1的最少计算次数。(如果无法得到1,则

输出T)。

(1)若输入两个不同的正整数a,b均为偶数，显然不可能得到1。

设x*a与y*b之差为"1”或“-1”，则对于正整数a,b经n=x+y-l次加减可得到1。

为了求n的最小值，令n从1开始递增，x在1----n中取值，y=n+l-x：

检测d=x*a+y*b,若d=l或T,则n=x+yT为所求的最少次数。

(2)算法描述

//两数若干次加减结果为1的数学游戏

ttinclude<stdio.h>

voidmainO

{longa,b,d,n,x,y;

printf(/z请输入整数a,b:");

scanfC%ld,%ldzz,&a,&b);

if(a%2==0&&b%2==0)

{printf(z/T\n");return;}

n=0;

while(l)

{n++;

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

{y=n+l-x;d=x*a-y*b;

if(d==l11d=T)〃满足加减结果为1

{printf(zzn=%ld\nzz,n);return;}

}

)

)

请输入整数a,b:2012,19

961

请输入整数a,b:101,2013

606

1-2埃及分数式算法描述

分母为整数分子为“1”的分数称埃及分数，试把真分数a/b分解为若干个分母不为b

的埃及分数之和。

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

(2)若C900000000,则退出；

(3)若CW900000000,把差a/b-1/c整理为分数a/b,若a/b为埃及分数，则输出后结

束。

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

试描述以上算法。

解：设"=int(2)(这里int(x)表示取正数x的整数)，注意到"<2<”+i，有

aa

a1a(d+\)-b

-=-------1----------------

bd+1b(d+1)

算法描述:令c=d+L则

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(1/b);return;}

)

1-3求解时间复杂度

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

(1)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(r)。

(2)m=0;

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

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

m=m+j;

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

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

设rp2u,语句m=m+l的执行频数为

s=1+1+2+2+3+3+・-+u=u2=n74

时间复杂度为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；

)

解:0s=l+2X2!+3X3!+-+nXn!=(n+l)!-1

时间复杂度为0((n+l)!).

(4)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)

printf(〃机d\n〃,a);break;}

)

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

体的执行次数s满足

s<25(回+V199+•••+J100"-1)<250(1+/+•“+«)

<250-册〈250“册

算法的时间复杂度为0(〃6)o

1-4时间复杂度的一个性质

若p(n)是n的多项式,证明：0(log(p(n)))=0(logn).

证：设m为正整数,p(n)=alXnm+a2Xn-'+■,■+amXn,

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

log(p(n))=malXlogn+(m-l)a2Xlogn+…=(mal+(mT)a2+…)Xlogn

<clogn

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

1-5统计n!中数字“0”的个数

修改1.3.2计算n!的算法，统计并输出n!中数字“0”的个数及其尾部连续“0”的个数

(n<10000),,

解：计算n!完成后，在j(1—m)循环中通过

if(a[j]==0)p++;

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

应用q=l;while(用q]=0)q++;统计尾部连续“0"的个数qT。

//统计n!中0的个数及尾部连续0的个数(n<10000)

#include<stdio.h>

#include<math.h>

voidmainO

{intg,j,k,m,n,p,q,t,a[40000];doubles;

printf(“请输入正整数n(n〈10000):");

scanf&n);//输入n

s=0;

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

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

m=(int)s+l;

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

a[k]=0;//数组清零

a[l]=l;g=0;

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

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

{t=a[j]*k+g;//数组累乘并进位

a[j]=t%10;

g=t/10;

)

P=0;

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

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

q=l；

while(a[q]=0)q++;//q尾部连续0的个数

printf(z/p=%d,q=%d\n”,p,qT);//输出结果

)

数据测试：

请输入正整数n(n<l0000):1000

p=472,q=249

请输入正整数n(n<10000):2013

p=1032,q=501

1-6构建斜折对称方阵

图-4是一个7阶斜折对称方阵，试观察斜折对称方阵的构造特点，总结归纳其构造规

律，设计并输出n(奇数)阶斜折对称方阵。

0123210

1012101

2101012

3210123

2101012

1012101

0123210

图-47阶斜折对称方阵

(1)构造规律与赋值要点

对n阶方阵中的每一个元素都必须赋值，但不可能逐行逐列地一个个赋值，有必要分析

方阵的构造特点，分块或分片实施。

斜折对称方阵的构造特点：两对角线上均为“0”，依两对角线把方阵分为4个区域，每

-区域表现为同数字依附两对角线折叠对称，至上下左右正中元素为n/2。

同样设置2维a[n][n]数组存储方阵中元素，行号为i,列号为j,a[i][j]为第i行第j

列元素。

令m=(n+l)/2,按m把方阵分成的4个小矩形区如图卜5所示。

|iWm

卜Wm3

10

图15按m分成的4个小矩形

注意到方阵的主对角线(从左上至右下)上元素为：i=j,则左上区与右下区依主对角线

赋值:a[i][j]=abs(i-j);

注意到方阵的次对角线(从右上至左下)上元素为：i+j=n+l,则右上区与左下区依次

对角线赋值：a[i][j]=abs(i+j-n-l);

(2)程序设计

//斜折对称方阵

^include<math.h>

ttinclude<stdio.h>

voidmainO

(inti,j,m,n,a[30][30];

printf("请确定方阵阶数(奇数)n:;scanf(绘d",&n);

if(n%2==0)

{printf("请输入奇数！")；return;}

m=(n+l)/2;

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

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

{if(i<=m&&j<=m||i>m&&j>m)

a[i][j]=abs(i-j);//方阵左上部与右下部元素赋值

if(i<=m&&j>m||i>m&&j<=m)

a[i][j]=abs(i+j-n-l);//方阵右上部与左下部元素赋值

)

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

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

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

printf(绘3d”,a[i][j]);

printf("\n");

1-7构建横竖折对称方阵

试观察图1-6所示的横竖折对称方阵的构造特点，总结归纳其构造规律，设计并输出n

(奇数)阶横竖折对称方阵。

1234321

2234322

3334333

4444-44■4

33343：33

2234322

1234321

图1-67阶横竖折对称方阵

(1)构造规律与赋值要点

观察横竖折对称方阵的构造特点，方阵横向与纵向正中有一对称轴。两对称轴所分4个

小矩形区域表现为同数字横竖折递减，至4顶角元素为1。

设阶数n(奇数)从键盘输入，对称轴为m=(n+l)/2。

设置2维a数组存储方阵中元素，行号为i,列号为j,为第i行第j列元素。

可知主对角线（从左上至右下）有：i二j；

次对角线（从右上至左下）有：i+j=n+l。

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

图卜7对角线分成的4个区

对角线上元素可归纳到上、下部，即上、下部区域带等号即可。

上、下部按列号j的函数m-abs(m-j)赋值：

if(i+j<=n+l&&i<=jI|i+j>=n+l&&i>=j)

a[i][j]=m-abs(m-j);

左、右部按行号i的函数m-abs(m-i)赋值：

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

a[i][j]=m-abs(m-i);

(2)算法描述

//横竖折对称方阵

#include<stdio.h>//调用2个头文件

ttinclude<math.h>

voidmainO

{inti,j,m,n,a[30][30];//定义数据结构

printfC请确定方阵阶数(奇数)n:〃)；scanf(〃%d〃,&n);

if(碌2=0)

{printf("请输入奇数！〃)；return;}

m=(n+l)/2;

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

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

(

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

a[i][j]=m-abs(m-j);//方阵上、下部元素赋值

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

a[i][j>m-abs(m-i);//方阵左、右部元素赋值

)

printfC%4阶对称方阵为:\口〃》);

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

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

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

printfC\nz，);

}

1-8应用定义求最大公约与最小公倍数

应用定义求n个正整数的最大公约数与最小公倍数，给出算法设计。

为方便表述，记

(al,a2,,an)为n个正整数al,a2........an的最大公约数。

{al,a2........an}为n个正整数al,a2,....an的最小公倍数。

(1)设计要点

求3个或3个以上正整数的最大公约数与最小公倍数，可通过反复运用求两个正整数的

最大公约数与最小公倍数的方法来实现。

对于3个或3个以上正整数，最大公约数与最小公倍数有以下性质：

(al,a2,a3)=((al,a2),a3)

(al,a2,a3,a4)=((al,a2,a3),a4),...

{al,a2,a3}={{al,a2},a3}

{al,a2,a3,a4}={{al,a2,a3},a4},...

应用这•性质，要求n个数的最大公约数，先求出前nT个数的最大公约数b,再求第n

个数与b的最大公约数。要求n个数的最小公倍数，先求出前n-1个数的最小公倍数b,再

求第n个数与b的最小公倍数。

程序设计求最大公约数时变量b的值：开始b=m[O],即输入的第一个数；进入循环后，

每次把输入的数赋值给a,求得a、b的最大公约数c,同时赋值给b,为下一轮循环作准备。

求最小公倍数时变量b的值：开始b=m[O],即输入的第•个数；进入循环后，每次把输入

的数赋值给a,求得a、b的最小公倍数c,同时赋值给b,为下一轮循环作准备。

(2)算法描述

〃求n个正整数的最大公约数与最小公倍数

#include<stdio.h>

voidmain()

{intk,n;

longa,b,c,m[100];

printf(”请输入正整数个数n:");

scanf("%d",&n);

printf("请依次输入%d个正整数：”,n);

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

{printf("\n请输入第%(1个正整数：”,k+l);

scanf("断;//输入原始数据

b=m[0];

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

{a=m[k];

if(a<b)

{c=a;a=b;b=c;}//交换a、b,确保a>b

for(c=b;c>=l;c--)

if(a%c==0&&b%c==0)//计算最大公约数

break;

b二c;

)

printf(〃(％ld〃,m[0]);//输出最大公约数结果

for(k=l;k<=n-l;k++)printf%ld”,m[k])

printfC/)=%ld\n，，jc);

b=m[0];

for(k=1;k〈=n-l;k++)

{

a=m[k];

if(a<b)

{c=a;a=b;b=c;}

for(c=a;c<=a*b;c=c+a)

if(c%b=0)//计算最小公倍数

break;

b二c;

)

printfC{%ld/，,m[0]);//输出最小公倍数结果

for(k=l;k<=n-l;k++)printf(，/,%ld〃，m[k]);

printf(/，)=%ld\n，/,c);

)

(3)数据测试

请输入正整数个数n：3

请依次输入3个正整数：

请输入第1个正整数：238

请输入第2个正整数：782

请输入第3个正整数：646

(238,782,646)=34

{238,782,646)=104006

习题2

2-1广义同码小数之和

s(d,n)=0.d+0.dd+0.ddd+...+0.dd...d(n个d)

其中正整数d,n从键盘输入(l<d,n<10000)

例如：s(301,4)=0.301+0.301301+0.301301301+0.301301301301

依次输入整数d,n(l〈d,n〈10000),输出和s(d,n)的整数部分与小数点后前10位。

(1)设计要点

1)求出输入的整数d的位数k及d的各位数字p[k](p[□为个位数字)。

2)枚举小数点后各位(共n*k位)求和。

3)设置n*k次循环，从后往前进位。

(2)枚举描述

//求和s(d,n)=0.d+0.dd+0,ddd+...+0.dd...d(n个d)

tfinclude<stdio.h>

voidmain()

{inta,d,i,j,k,m,n,p[10];longs[50000];

printf(z/请输入整数d,n:");

scanf("%d,%d",&d,&n);

a=d;k=0;

while(a>0)

{k++;p[k]=a%10;a=a/10;}

for(j=0;j〈=k*n;j++)s[j]=O;//s[0]为整数部分

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

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

s[i*k+j]=(n-i)*p[k+l-j];//小数点后各位求和

for(j=k*n;j>=l;j—)//加完n个数从后往前统一进位

{s[j-l]=s[j-l]+s[j]/10;s[j]=s[j]%10;}

printf(，zs(%d,%d)=%ld.",d,n,s[0]);

m=k*n;

if(m>10)m=10;

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

printfs[j]);

)

数据测试：

输入整数d,n:2014,2013

s(2014,2013)=405.4587257305

2-2解不等式

设n为正整数，解不等式

1

2013<1+------+-------------+<2014

1+1/21+1/2+1/31+1/2+…+1/〃

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

分两段求和：应用条件s〈a实施循环段；应用条件s〈b实施循环段。

//解不等式：a<l+l/(1+1/2)+...+1/(1+1/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=O;ts=O;s=O;

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;

printfC\n满足不等式的正整数n为:%ldWnW%ld\n〃,c,d);

)

数据测试：

请输入a,b:2013,2014

满足不等式的正整数n为：18642WnW18652

2-3解不定方程

试求解三元不定方程

—1—--1-=----1---

abxca+b+c

满足条件x<a,b,c<y,b<c的所有正整数解。

（1）枚举设计要点

1）为了扩大求解范围，所涉变量设置为double型。

2）注意a,b,c的取值范围，在区间［x,y］中取值：

a与b,c没有限制，只限制b〈c,因而c枚举循环可设计为：

for（c=b+l;c<=y;c++）

3）另外，原三元不定方程为分数形式，转化为以下的整数形式

（a+h+c）xhx,c=ax（（a+b+c）+hxc）

在枚举循环中应用以上整式进行筛选是可行的。

（2）枚举描述

//解不定方程

itinclude<stdio.h>

#include<math.h>

voidmainO

{doublea,b,c,s,x,y,m;

printf（z，请输入正整数x,y:"）;

scanf&x,&y);

m=0;

for(a=x;a<=y;a++)//设计三重循环实现枚举

for(b=x;b<=y-l;b++)

for(c=b+l;c<=y;c++)

{s=a+b+c;

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

continue;

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

printf(〃%.Of:a=%.Of,b=%.Of,c=%.Of\n〃，m,a,b,c);

)

)

数据测试：

请输入正整数x,y:10,100

1:a=50,b=10,c=15

2:a=90,b=15,c=21

2-4合数世纪探索

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

数世纪。

试探索第m（约定m<100）个合数世纪。

（1）枚举要点

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

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

对于a世纪，若s=50,即50个奇数都为合数，找到a世纪为合数世纪，用n统计合数

世纪的个数。当n=m时打印输出a世纪。

当n=m时退出循环结束。

(2)枚举描述

//探求第m个合数世纪

Sinclude<stdio.h>

ttinclude<math.h>

voidmain()

{longa,b,k;intm,n,s,x;

printfC请确定m:");scanf("%d",&m);

a=l;n=0;

while(1)

{a++;s=0;//检验a世纪

for(b=a*100-99;b<=a*100-l;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个奇数均为合数

{n++;

if(n==m)

printf(，z第%d个合数世纪为：%ld世纪。\n”,n,a);

)

if(n=m)break;

)

)

数据测试：

请确定m:10

第10个合数世纪为：58453世纪。

2-5分解质因数

对给定区间［m,n］的正整数分解质因数，每一整数表示为质因数从小到大顺序的乘积形

式。如果被分解的数本身是素数，则注明为素数。

例如，2012=2*2*503,2011=(素数!)。

(1)设计要点

对区间中的每一个整数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后继续。

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

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

(2)枚举描述

//质因数分解乘积形式

#include"math.h"

^include<stdio.h>

voidmainO

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

printf("Dn,n］中整数分解质因数(乘积形式).\n");

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

scanf(z/%ld,%ld”,&m,&n);

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

{printfC%ld="Z,i);

b=i;k=2;

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

{if(b%k==O)

{b=b/k;

if(b>l)

{printf(z/%ld*z/,k);

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

)

if(b==l)printf("断d\n",k);

}

k++;

}

if(b>l&&b<i)

printf("%ld\n",b);//输出大于i平方根的因数

if(b=i)

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

)

数据测试：

[m,n]中整数分解质因数(乘积形式).

请输入m,n:5845201,5845300

5845201=593*9857

5845202=2*11*47*5653

5845300=2*2*5*5*58453

以上测试可知没有••个素数，验证了上题的第10个合数世纪的100个合数年号。

2-6因数比的最大值

设整数a的小于其本身的因数之和为s,定义

p(a)=s/a

为整数a的因数比。

事实上，a为完全数时，p(a)=1。例如，p(6)=1。

有些资料还介绍了因数之和为数本身2倍的整数，例如p(120)=2o

试搜索指定区间［x,y］中因数比最大的整数。

(1)设计要点

设置循环枚举区间［x,y］中的整数a。

为了求整数a的因数和s,显然1是因数,设置因数k(2——sqrt(a))的枚举循环，如果

k是a的因数，则a/k也是a的因数，实施求和s=s+k+a/k。

有一点值得注意：如果a=b*b,显然卜书通人力是同一个因数，为避免重复求和，所以

此时必须从和s中减去一个bo

设置max存储因数比最大值。枚举区间内每一整数a,求得其因数和s。通过比值s/a

与max比较，求取因数比最大值。

(2)枚举描述

//求［x,y］范围内整数的因数比最大值

ttinclude<stdio.h>

#include<math.h>

voidmain()

{doublea,s,al,si,b,k,t,x,y,max=0;

printf("请输入整数x,y:;

scanf&x,&y);

for(a=x;a<=y;a++)//枚举区间内的所有整数a

{s=l;b=sqrt(a);

for(k=2;k<=b;k++)//试商寻求a的因数k

if(fmod(a,k)=0)

s=s+k+a/k;〃1<与2/1<是a的因数，求和

if(a—b*b)

s=s-b;//如果a=b~2,去掉重复因数b

t=s/a;

if(max<t)

{max=t;al=a;sl=s;}

)

printfC整数%.Of的因数和为:%.Of,al,si);

printf("其因数比最大：%.5f\n，z,max);

}

数据测试：

请输入整数x,y:10000,100000

整数55440的因数和为：176688,其因数比最大：3.18701

算法中在区间枚举循环中含试商因数枚举的内循环。设区间中整数个数为n,算法的时间

复杂度为O(n4n)o

思考：请探求是否存在因数比p(a)=s/a24的整数a?若存在，整数a至少为多大？

2-7基于素数代数和的最值

定义和：

s(n)=1X3+3X5+5X7+7X9±---±(2n-l)x(2"+1)

(和式中第k项土(2kT)*(2k+l)的符号识别：当(2kT)与(2k+l)中至少有一个素数，取

"+"；其余取例如和式中第13项取即为-25*27。)

1)求s(2013)。

2)设l〈=n<=2013,当n为多大时，s(n)最大。

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

(1)设计要点

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

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

若2k-l为素数，标注若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+l)中没有素数，实施

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

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

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

(2)算法描述

//基于素数的整数和

#include<stdio.h>

#include<math.h>

voidmain()

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

printfC请输入整数n:〃)；

scanf&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=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

)

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

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

printf(〃当k=%d时s有最小值：%ld\n〃,k2,smin);

)

数据测试：

请输入整数n:2013

s(2013)=-889733139

当k=814时s有最大值：46296494

当k=1999时s有最小值:-1018390543

2-8完美四则运算式

把数字1,2,...，9这9个数字填入以下含加减乘除的综合运算式中的9个口中，使得该

式成立

□□x□+□□□+□-□□=()

要求数字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(l—9)的个数。

若某一f(x)不为1,不满足数字1,29这九个数字都出现一次且只出现一次，标记

t=l.

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

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

设置n统计解的个数。

(2)设计描述

//四则运算式

^include<stdio.h>

voidmainO

{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;mE2]=c;m[3]=e：m[4]=b;ni[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("%2d:%2d*%1d+%3d/%1d-%2d=0\n”,n,a,b,c,d,e);

)

)

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

)

数据测试：

1:12*4+376/8-95=0

2:17*3+258/6-94=0

3:35*2+168/7-94=0

n=3.

2-9区间内的最大连续合数区间

搜索指定区间［c,d］内的最大连续合数区间。

输入：键盘输入区间范围c,d。

输出：区间内最多连续合数的个数，连续合数的起始与终止数。

例如输入c,d:10,100

最多连续合数的个数为：7

连续合数区间为：［90,96］

(1)应用试商设计

//求指定区间内最多有多少个连续合数

Sinclude<stdio.h>

ttinclude<math.h>

voidmainO

{longc,d,i,j,f,t,fl,il,max;

printfC请输入c,d:");scanf("Id,%ld",&c,&d);

f=c;max=0;

if(c%2=0)c++;

i=c;

for(i=c;i<=d;i+=2)

{t=0;

for(j=3;j〈=sqrt(i);j+=2)//试商判别素数

if(i%j==0){t=l;break;}

if(t==O)//t为。表明i为素数

{if(i-f>max)

{max=i-f;fl=f+l;il=i-l;}

f=i；〃f为i的前一个素数

)

)

printf(z/最多连续合数的个数为：%ld\nz，,max-1);

printf(z/连续合数区间为：［%ld,%ld］\n",fl,il);

)

数据测试：

请输入c,d:10000,1000000

最多连续合数的个数为：113

连续合数区间为：［492114,492226］

(2)筛法设计

求出区间［c,d］内的所有相邻素数对f,m,求取m-f的最大值max。

注意到本题的搜索范围较大,采用效率较高的筛法求素数是适宜的。

求素数的筛法是公元前三世纪的厄拉多塞(Eratosthenes)提出来的：对于一个大整数x,

只要知道不超过sqrt(x)的所有素数p,划去所有p的倍数2p,3p,...,剩下的整数就是不超

过x的全部素数。

应用筛法求素数，为了方便实施"划去”操作，设置数组。

考虑到有时待测区间［c,d］比较大，为不使数组下标超维,或把［c,d］分割为若干子区间

［cs,ds］,确保在子区间中操作不超维。

每一数组元素对应一个待判别的奇数，并赋初值0。如果该奇数为p的倍数则应划去，

对应元素加一个划去标记，通常给该元素赋值-1。最后，打印元素值不是-1(即没有划去)的

元素对应的奇数即所求素数。

在实际应用筛法的过程中，P通常不限于取不超过sqrt(x)的素数，而是适当放宽取不超

过sqrt(x)的奇数(从3开始)。这样做尽管多了•些重复划去操作，但程序实现要简便些。

在指定区间区s,ds］(约定cs为奇数)上所有奇数表示为j=cs+2k,(k=0,1,...,e,这里

e=(ds-cs)/2)。于是k=(j-cs)/2是奇数j在数组中的序号(下标)。如果j为奇数的倍数时，

对应数组元素作划去标记,即a［(j-cs)/2］=-lo

根据cs与奇数i,确定g=2*int(cs/(2*i))+l,使得gi接近区间下限cs,从而使划去的

gi,(g+2)i,...在［cs,ds］中,减少无效操作,以提高对大区间的筛选效率。

最后,凡数组元素a［k］W-1,对应的奇数j=cs+2k则为素数。

//求指定区间内最多有多少个连续合数

^include<stdio.h>

Sinclude<math.h>

voidmainO

{longc,d,cs,ds,ct,dt,f,g,i,j,k,m,max,a［11000］;

inte,u,x,y;

printf(/z请输入c,d:");scanf(z/%ld,%ldz/,&c,&d);

if(d-c<=20000){cs=c;ds=d;x=0;}

else{x=(d-c)/20000;cs=c;ds=d-20000*x;}

f=cs;max=0;

for(y=l;y<=x+l;y++)//把［c,d］中分x+1个子区间筛选素数

{if(cs%2==0)cs++;

for(i=0;i〈=10999;i++)a[i]=O;

e=(ds-cs)/2;i=l;

while(i<=sqrt(ds))

{i=i+2;g=2*(cs/(2*i))+l;

if(g*i>ds)continue;

if(g==l)g=3;

j=i*g；

while(j<=ds)

{if(j>=cs)a[(j-cs)/2]=-l;//筛去标记T

j=j+2*i;

)

}

for(u=l,k=0;k<=e;k++)

{if(a[k]!=T)

{m=cs+2*k;//m即筛选所得素数

if(nrf>max)//寻求两相邻素数间距的最大值

{max=m-f;ct=f+l;dt=cs+2*kT;}

f=m;

)

)

cs=ds+l;ds=ds+20000;//cs与ds增长后继续探求

)

printf("最多连续合数的个数为：%ld\n，z,max-1);

printfC连续合数区间为：[%ld,%ld]\n",ct,dt);

)

数据测试：

请输入c,d:10,10000000

最多连续合数的个数为：153

连续合数区间为：[4652354,4652506]

2-10三角形双分线

设一块木板为非等腰A48C,其三边长分别为BC=a,CA=b,AB=c,寻求三角形木板上的分

割线，把该三角形木板分割为周长相等且面枳相等的两块。

试确定双分线的具体位置。

依次输入正整数a,b,c(约定a,b,c<100),输出各分割线的位置(四舍五入精确到小数点

后第4位)。

(1)设计要点

1)设A4BC的周长为p,AB边上的分割点为D,AC边上的分割点为E,BC边上的分割

点为F(如图2-6所示)。显然，p=a+b+Co

若线段EF为双分线，则ACE尸的面积为A48C面积的一半，CE+CF=p/2(分割线段EF

为两块公共)。

图2-6A45C及其分割线示意图

2)设CE=x,CF=p/2-x,则面积相等的条件为CE*CF=x(p/2-x)=ab/2

同样，设CF=x,CE=p/2-x,则面积相等的条件为CE*CF=x(p/2-x)=ab/2

整理为关于x的二次方程：

2x~-(a+b+c)x+ab=O

可见若E