第2讲穷举

更新时间：2024-01-18 12:28:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

盖马三锤第2讲推荐度：
相关推荐

程序设计竞赛系列讲座

第1讲

第2讲

第3讲

第4讲

第5讲

第6讲

第7讲

杨克昌

程序设计竞赛引论穷举递推递归回溯动态规划综合训练 1

第2讲穷举

穷举是计算机程序设计引导入门的基础算法，也是在数量较小的问题求解中应用广泛的算法。应用穷举设计可以非常简明地解决许多实际问题。

本章介绍统计求和、解方程、解不等式、求最值以及涉及素数的基础案例的穷举求解，并由整币兑零、完美综合式与和积三角形三个安全的求解说明穷举设计的改进与优化。

2.1 穷举概述

1. 穷举的概念

穷举法又称列举法、枚举法，是蛮力策略的具体体现，是一种简单而直接地解决问题的方法。其基本思想是逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。

通常程序设计入门都是从穷举设计开始的。今天，计算机的运算速度非常快，应用穷举设计程序可快捷地解决一般数量的许多实际应用问题。

穷举法的特点是算法设计比较简单，解的可能为有限种，一一列举问题所涉及的所有情形。穷举法常用于解决“是否存在”或“有多少种可能”等问题。其中许多实际应用问题靠人工推算求解是不可想象的，而应用计算机来求解，充分发挥计算机运算速度快、擅长重复操作的特点，穷举判断，快速简便。

应用穷举时应注意对问题所涉及的有限种情形须一一列举，既不能重复，又不能遗漏。重复列举直接引发增解，影响解的准确性；而列举的遗漏可能导致问题解的遗漏。

2. 穷举的框架描述

穷举通常应用循环结构来实现。在循环体中，根据所求解的具体条件，应用选择结构实施判断筛选，求得所要求的解。

穷举法的框架描述： n=0;

for(k=<区间下限>;k<=<区间上限>;k++) // 根据指定范围实施穷举 if(<约束条件>) // 根据约束条件实施筛选 { printf(<满足要求的解>); // 输出满足要求的解 n++; // 统计解的个数 }

有些问题没有明确的区间限制，可根据问题的具体实际试探性的从某个数开始，增值穷举，对每一个数作一判断，若满足条件即输出结果，结束穷举。

尽管穷举比较简单，在应用穷举设计求解实际问题时要认真分析，准确选定穷举范围与约束条件。

3. 穷举的实施步骤

应用穷举设计求解，通常分以下几个步骤：

（1）根据问题的具体情况确定穷举量（简单变量或数组）；（2）根据确定的范围设置穷举循环；

（3）根据问题的具体要求确定筛选约束条件；

（4）设计穷举程序并运行、调试，对运行结果进行分析与讨论。

当问题所涉及数量非常大时，穷举的工作量也就相应较大，程序运行时间也就相应较长。为此，应用穷举求解时，应根据问题的具体情况分析归纳，寻找简化规律，精简穷举循环，优化穷举策略。

4. 穷举设计的意义虽然巧妙和高效的算法很少来自穷举，但穷举设计作为一种常用的基础算法不能受到冷漠与轻视：

（1）理论上，穷举可以解决可计算领域中的各种问题。尤其处在计算机计算速度非常高的今天，穷举的应用领域是非常广阔的。

（2）在实际应用中，通常要解决的问题规模不大，用穷举设计的算法其运算速度是可以接受的。此时，设计一个更高效率的算法代价不值得。

（3）穷举可作为某类问题时间性能的底限，用来衡量同样问题的更高效率的算法。

本章将通过若干典型案例的求解，说明穷举的实际应用。

2.2 统计与求和

统计与求和是程序设计最基本的课题，通常只要合理运用穷举即可简捷地解决问题。本节介绍最简真分数与数字有特殊要求的整数这两个典型案例的穷举求解，提高对运用穷举实施统计与求和技巧的认识。

2.2.1 最简真分数统计求和

1. 案例提出

统计分母在指定区间[a,b]的最简真分数(分子小于分母，且分子分母无公因数)共有多少个,并求这些最简真分数的和(正整数a,b从键盘输入)。

2．算法设计

设分数为分子为i，分母为j，最简真分数的和为s。在指定范围内[a,b]穷举分数的分母j:a——b；同时对每一个分母j穷举分子i:1——j-1。对每一分数i/j，置t=0，然后进行是否存在公因数的检测。

如果分子i与分母j?存在大于1的公因数u，说明i/j非最简真分数,应予舍略。因为分子分母同时约去u后，分母可能不在[a,b]，即使在[a,b]时前面已作了统计求和。

注意到公因数u的取值范围为[2,i]，因而设置u循环在[2,i]中穷举u，若满足条件 j%u==0 && i%u==0

说明分子分母存在公因数，标记t=1后退出，不予统计与求和。否则保持原t=0，说明分子分母无公因数，用n实施迭代“n=n+1或n++”统计个数，应用s实施迭代求和。

为操作方便分子分母等变量设置为整型，和可能存在小数，和变量s设置为双精度double型，因而求和时要注意把分数i/j转变为double型。

3．求最简真分数程序设计

// 求分母在[a,b]的最简真分数的个数及其和 #include #include

void main()

{int a,b,n,i,j,t,u; double s;

printf(\最简真分数分母在[a,b]内,请确定a,b: \scanf(\输入区间的上下限 n=0;s=0;

for(j=a;j<=b;j++) // 穷举分母

for(i=1;i<=j-1;i++) // 穷举分子 { for(t=0,u=2;u<=i;u++) // 穷举因数 if(j%u==0 && i%u==0)

{ t=1;

break; // 分子分母有公因数舍去 }

if(t==0)

{ n++; // 统计最简真分数个数

s+=(double)i/j; // 求最简真分数和 }

}

printf(\最简真分数个数 n=%d \\n\ printf(\其和 s=%.5f \\n\}

4. 程序运行示例

最简真分数分母在[a,b]内, 请确定a,b: 10,99 最简真分数个数 n=2976 其和 s=1488.00000

2.2.2 特殊整数统计求和

1. 案例提出

试求含有数字7且不能被7整除的5位整数的个数，并求这些整数的和。同时，求这些整数中恰含2个数字7的整数的个数，以及这些整数的和。

2. 设计要点

一般地，设m，n为一位正整数，含有数字m且不能被m整除的n位整数的个数g1，这些整数的和s1。其中恰含2个数字m的整数的个数g2及其和s2。这里m，n(n>2)是从键盘输入的一位正整数。

首先，通过循环n-1次相乘求出最小的n位整数t。然后通过k从t至10*t-1循环，穷举所有n位整数。

为了检测k是否含有数字m，是否恰含2个数字m，每个n位整数k赋给d(为了保持k不变)。然后通过n次求余先后分离出k的数字c，并用f(c)=f(c)+1统计数字c 的个数。

例如f(7)=2，说明整数k中恰含2个数字7；若f(3)>0，说明整数k中含有数字3. 然后据f(m)>0 && k%m>0检测含有数字m且不能被m整除，g1与s1作相应统计求和。据f(m)＝2 && k%m>0检测恰含2个数字m且不能被m整除，g2与s2作相应统计求和。 3. 程序设计

// 含数字m且不能被m整除的n位整数的个数、和 #include void main()

{ int c,j,m,n,f[10];

long d,k,g1,g2,s1,s2,t;

printf(\请输入一位整数m,n: \ scanf(\ t=1;

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

t=t*10; // 求最小的n位整数t g1=0;s1=0;

g2=0;s2=0;

for(k=t;k<=10*t-1;k++) // 穷举每一个n位数 { d=k;

for(j=0;j<=9;j++) f[j]=0;

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

{ c=d;f[c]+=1; // 统计n位整数k中各数字的个数 d=d/10;

}

if(f[m]>0 && k%m>0) // k含数字m且不能被m整除 {g1++;s1+=k;}

if(f[m]==2 && k%m>0) // k恰含2个数字m且不能被m整除 {g2++;s2+=k;} }

printf(\含数字%d且不能被%d整除的%d位整数的个数 g1=%ld \\n\

printf(\这些整数的和为 s1=%ld \\n\

printf(\恰含2个数字%d且不能被%d整除的%d位整数个数 g2=%ld \\n\

printf(\这些整数的和为 s2=%ld \\n\}

4. 程序运行示例请输入一位整数m,n: 7,5

含数字7且不能被7整除的5位整数的个数 g1=32152 这些整数的和为 s1=1894711910

恰含2个数字7且不能被7整除的5位整数个数 g2=5837 这些整数的和为 s2=368002794

2.3 解方程

解方程(组)是程序设计的应用课题之一。有些较为复杂的方程用常规方法是难以胜任的，运用程序设计可望有效求解，得到相应的准确解或近似解。

2.3.1 韩信点兵

1. 案例提出

在中国数学史上，广泛流传着一个“韩信点兵”的故事。韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝建立了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了知道有多少个兵，同时又能保住军事机密，便让士兵排队报数: 按从1至5报数,记下最末一个士兵报的数为1；

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

最后按1至11报数,最末一个士兵报的数为10。你知道韩信至少有多少兵?

2. 求解要点

设兵数为x，则x满足下述的不定方程组:

x=5y+1 即 x=1 (mod 5) x=6z+5 x=5 (mod 6) x=7u+4 x=4 (mod 7) x=11v+10 x=10 (mod 11)

其中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=1与x%7=4 两个条件即可。

这样可算得满足条件的最小整数x即点兵的数量。 3. 程序实现 // 韩信点兵 #include void main() { long int x; x=65;

while(1) { x=x+66;

if(x%5==1 && x%7==4)

{ printf(\至少有兵: %ld 个。\ break; } } }

运行程序，得

至少有兵：2111个。 4. 案例一般化

上述点兵是报4遍数，一般化为报n遍数，第i次从1至p(i)报数时，最末一名士兵报数为r(i)，（i=1,2,...,n）。

这里，n与p(i),r(i)（i=1,2,...,n）均从键盘输入。（1）设计要点设置输入循环，输入中如果出现r(i)=p(i)，这在报数过程中是可能的。为统一处理，这里需归零r(i)=0。

设人数为x，并取初值x=r(n)，进入永真循环。

循环中x按步长p(i)增值，即x=x+p(n)。对每一次x取值，置标志t=0。然后在i循环中进行n-1次检测：

若对某一i，x%p[i]!=r[i]，即人数x不满足第i次报数，t=1，x需增值再试；若对所有i，（i=1,2,...,n），x%p[i]==r[i]，即此时人数x满足所有n次报数，保持原有t=0，则输出人数x为所求，结束。

（2）程序设计

// 一般化韩信点兵

#include void main()

{ long n,t,i,x,p[20],r[20];

printf(\按1至p报数,最末一人报数为r。\\n\ printf(\需报数n轮, 请输入n: \ scanf(\

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

{ printf(\第 %ld 轮, 请输入p，r: \ scanf(\ if(r[i]==p[i]) r[i]=0; } x=r[n];

while(1)

{x=x+p[n];

t=0;

for(i=1;i<=n-1;i++) if(x%p[i]!=r[i])

{t=1;break;} if(t==0)

{ printf(\至少有 %ld 个兵。\\n\ break; } }

}

（3）程序运行示例与讨论

按1至p报数,最末一人报数为r。需报数n轮, 请输入n: 5 第 1 轮, 请输入p，r: 3,1 第 2 轮, 请输入p，r: 5,2

第 3 轮, 请输入p，r: 7,5 第 4 轮, 请输入p，r: 11,9 第 5 轮, 请输入p，r: 13,10 至少有 2077 个兵。

以上求解的不定方程组，满足上述不定方程组的正整数解有无穷多组，程序输出的只是满足条件的最小正整数解。

例如，以上示例数据，2077+3*5*7*11*13=17092也是一个解。

2.3.2 解超越方程

1. 案例提出试求方程

2xsin(x)?3x?5e?4?0

在区间（1,3）中的一个解，精确到小数点后6位。

2. 基于最小的穷举求精穷举求解（1）算法设计

对任意给定的一个单变量超越方程或高次方程,?在指定范围内求它的一个解（精确到小数点后6位）。若在指定区间内无解,则显示“无解”信息。

给定的一元超越方程fny(x)=0在指定区间[a,b]内的解即方程对应曲线与x轴交点的x坐标值。

首先初步判定方程在指定区间内是否有解:x从a开始按步长量0.1递增取值,?其函数值fny(x)逐个与b点的函数值fny(b)比较:

若异号,方程有解(标记t=1),继续求精探求。

若全都同号,方程无解(标记t=0),打印“无解”信息后结束。

求方程fny(x)=0的解，采用求｜fny(x)｜的最小值来实现。设置记录其最小值的变量mi，并赋一个大的初值（例如mi=100）。

设置x从a至b步长c（初值0.1）的循环，比较mi与｜fny(x)｜得最小值mi,并用x1记录此时的x值。

然后逐位求精，求精循环的步长量c缩小为上位的十分之一,即c=c/10，循环初值a=x1-5c，终值b=x1+5c。

控制8（可根据精度适当增减）次求精后，打印所得的解的结果。（2）基于最小的穷举求精程序设计

// 基于最小的穷举求精解超越方程

#include #include

double fny(double x) // 自定义函数fny，用来定义方程式

{return 2*pow(x,9)*sin(x)+3*pow(x,4)-5*exp(x)-4;} // 据方程实际改变 void main() { int k,t;

double a,b,c,x,x1,y,mi;

printf(\求方程在[a,b]中的一个解，请确定a,b: \

scanf(\

for(t=0,x=a;x<=b;x+=0.1) // 按步长0.1初步扫描 if(fny(x)*fny(b)<=0) // 调用自定义函数fny() {t=1;break;}

94x 9

if(t==0)

{ printf(\无解!\

c=0.1; k=1; mi=100.0;

while(k<=8) // 设置8次求精循环 { for(x=a;x<=b;x+=c) { y=fny(x);

if(fabs(y)

c=c/10;a=x1-5*c;b=x1+5*c; // 缩小循环步长求精 k++; }

printf(\所求方程的一个解为 x=%f \\n\输出解 }

3. 基于符号判定的穷举求精穷举求解

对任意给定的一个单变量超越方程或高次方程,?在指定范围内求它的一个解（精确到小数点后6位）。若在指定区间内无解,则显示“无解”信息。 (1) 求解要点

给定的一元超越方程fny(x)=0在指定区间[a,b]内的解即方程对应曲线与x轴交点的x坐标值。

我们采用符号判定,逐位求精。

首先初步判定方程在指定区间内是否有解:x从a开始按步长量0.1递增取值,?其函数值fny(x)逐个与b点的函数值fny(b)比较:若异号,方程有解(标记t=1),此时x的值赋给x1,b赋给x2,显然其解在[x1,x2]中.若全都同号,方程无解(标记t=0),打印无解信息后结束。

然后逐位求精，每位求精时其步长量c缩小为上位的十分之一,即c=c/10. x从x1开始递增c取值,其函数值fny(x)逐个与x2点的函数值fny(x2)比较：若异号,?循环取下一点继续。若同号,说明方程的解在此时的x值与上一个点的x值(即x-c)之间,作赋值x2=x,x1=x-c,即方程的解在[x1,x2]中,本位求精判定完成。

若已求精到小数点后6位,打印所得的解后结束。

(2) 符号判定穷举求精程序设计

// 符号判定穷举求精解超越方程 #include #include

double fny(double x) // 自定义函数fny，用来定义方程式

{return 2*pow(x,9)*sin(x)+3*pow(x,4)-5*exp(x)-4;} // 可根据方程实际改变 void main()

{ int i,t=0;

double a,b,x,x1,x2,c;

printf(\求方程在[a,b]中的一个解，请确定a,b: \

scanf(\

for(x=a;x<=b;x+=0.1) // 初步扫描

if(fny(x)*fny(b)<=0) // 调用自定义函数fny() {x1=x;x2=b;t=1;break;} if(t==0)

{ printf(\无解!\

c=0.01;

for(i=2;i<=7;i++) // 逐位求精 {for(x=x1;x<=x2;x+=c)

if(fny(x)*fny(x2)>0) // 如果变为同号，缩小循环范围 {x2=x;x1=x-c;break;} // 调整循环的初值x1与终值x2 c=c/10; // 缩小循环步长求精 }

x=(x1+x2)/2;

printf(\所求方程的一个解为x=%f\输出解，小数点后6位 }

4. 程序运行结果

求方程在[a,b]中的一个解，请确定a,b: 1,3 所求方程的一个解为 x=1.249880

2.4 解不等式

应用程序设计求解一些难度较大的不等式是程序设计应用的一个有趣的课题。解不等式通常只要简单穷举即可实现。

2.4.1 分数和不等式

1. 案例提出

试解下列关于正整数n的分数不等式

1000?12?23?34???nn?1?2010 （1）

2. 设计要点

为一般计，解不等式

m1?12?23?34???nn?1?m2 （2）

这里正整数m1,m2从键盘输入（m1

设和变量为s，在sm1退出循环，赋值c=i，所得c为n解区间的下限。

继续在sm2退出循环，通过赋值d=i-1，所得d为n解区间的上限。注意，解的上限是d=i-1，而不是i。

然后打印输出不等式的解区间[c,d]。 3. 程序实现

// 解分数不等式 #include #include void main()

{ long c,d,i,m1,m2; double s;

printf(\请输入正整数m1,m2(m1

{i=i+1;s=s+sqrt(i)/(i+1);} c=i;

while(s

{i=i+1;s=s+sqrt(i)/(i+1);} d=i-1;

printf(\满足不等式的正整数n为: %ld≤n≤%ld \\n\}

4. 程序运行示例

请输入正整数m1,m2(m1

2.4.2 代数和不等式

1. 案例提出

试解下列关于正整数n的代数和不等式

4?1?111112?3?4?5?6???1n (3)

(式中代数和表达式中符号为二个“+”号后一个“-”号) 2. 设计要点一般地，解不等式

d?1?12?13?14?15?16???1n （4）

（其中d为从键盘输入的正数）

式中符号为二个“+”号后一个“-”号，即分母能被3整除时为“-”，式中出现减运算，导致不等式的解可能分段。

设置条件循环，每三项（包含二正一负）一起求和，得一个区间解。然后回过头来一项项求和，得个别离散解。（2）程序设计

// 解不等式：d<1+1/2-1/3+1/4+1/5-1/6+...+-1/n #include void main() { long d,n,k; double s;

printf(\请输入正整数d: \ scanf(\

printf(\?+-1/n 的解：\ n=1;s=0; while(1)

{ s=s+1.0/n+1.0/(n+1)-1.0/(n+2); if(s>d) break; n=n+3;

}

printf(\得一个区间解 k=1;s=0; while(k

{ if(k%3>0) s=s+1.0/k; else s=s-1.0/k;

if(s>d) // 得一个离散解 printf(\ k++; } }

（3）程序运行示例请输入正整数d: 5

5<1+1/2-1/3+1/4+1/5-1/6+?+-1/n 的解：

n>=203938 n=203936

注意：前一个是区间解，后一个是离散解。要特别注意，不要把后一个解遗失。

2.5 求最值

求最值通常是程序设计最具魅力的课题之一。本节介绍两个有趣的最值案例求解，是运用穷举求解的典型手法。

2.5.1 基于素数的代数和

1. 案例提出定义和：

s(n)?13?35?57?79?911?1113???2n?12n?1

(和式中第k项±(2k-1)/(2k+1)的符号识别：分子分母中有且只有一个素数，取“+”；分子分母中没有素数或两个都是素数时取“-”。) 1) 求s(2011)(精确到小数点后5位)。

2) 设1<=n<=2011，当n为多大时，s(n)最大。 3) 设1<=n<=2011，当n为多大时，s(n)最接近0。 2. 设计要点

在求和之前应用“试商判别法”对第k个奇数2k-1是否为素数进行标注：若2k-1为素数，标注a[k]=1；否则，若2k-1不是素数，a[k]=0。

设置k循环（1——n），循环中分别情况求和：

若a[k]+a[k+1]=1，即(2k-1)与(2k+1)中有且只有一个素数，实施“+”；

否则，若a[k]+a[k+1]!=0，即(2k-1)与(2k+1)中没有素数或有两个素数，实施“-”。同时，设置最大变量smax，最接近“0”的绝对值变量mi。

在循环中，每计算一个和值s，与smax比较确定最大值，同时记录此时的项数k1；因s可正可负，s的绝对值与mi比较确定最接近“0”的绝对值，记录此时的项数k2，同时记录此时的和值s2。

最后，求和循环结束时输出所求值。 3. 程序实现

// 基于素数的分数和

#include #include

void main()

{ int t,j,n,k,k1,k2,a[3000]; double s,s2,smax,mi;

printf(\请输入整数n: \

scanf(\

for(k=1;k<=n+1;k++) a[k]=0; for(k=2;k<=n+1;k++)

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

if((2*k-1)%j==0) {t=1;break;}

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

s=0;smax=0;mi=10; for(k=1;k<=n;k++)

{if(a[k]+a[k+1]==1) // 判断a[k]与a[k+1]中有一个素数 s+=(double)(2*k-1)/(2*k+1); // 实施加 else

s-=(double)(2*k-1)/(2*k+1); // 否则，实施减 if(s>smax)

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

{mi=fabs(s);k2=k;s2=s;} // 绝对值比较求最接近0点 }

printf(\

printf(\当k=%d时s有最大值: %.5f\\n\printf(\当k=%d时s=%.5f最接近0. \\n\}

4. 程序运行示例请输入整数n: 2011 s(2011)=-211.88387

当k=387时s有最大值: 35.88835 当k=785时s=-0.04341最接近0.

2.5.2 整数的因数比

1. 案例提出

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

p(a)=s/a 为整数a的因数比。

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

有些资料还介绍了因数之和为数本身2倍的整数，如p(120)=2。试求指定区间[x,y]中整数的因数比最大值。 2. 设计要点

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

对比较得因数比最大的整数，通过试商输出其因数和式。 3. 程序实现

// 求[x,y]范围内整数的因数比最大值 #include #include void main()

{ double a,s,a1,s1,b,k,t,x,y,max=0;

printf(\求区间[x,y]中整数的因数比最大值.\ printf(\请输入整数x,y:\

scanf(\

for(a=x;a<=y;a++) // 穷举区间内的所有整数a {s=1;b=sqrt(a);

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

s=s+k+a/k; // k与a/k是a的因数，求和 if(a==b*b)

s=s-b; // 如果a=b^2,去掉重复因数b t=s/a; if(max

printf(\整数%.0f的因数比最大：%.4f \\n\ printf(\的因数和为：\\n\

printf(\输出其因数和式 for(k=2;k<=a1/2;k++) if(fmod(a1,k)==0)

printf(\}

（3）程序运行示例

求区间[x,y]中整数的因数比最大值.请输入整数x,y: 1,2011 整数1680的因数比最大：2.5429

1680的因数和为：

4272=1+2+3+4+5+6+7+8+10+12+14+15+16+20+21+24+28+30+35+40+42+48

+56+60+70+80+84+105+112+120+140+168+210+240+280+336+420+560+840

2.6 合数世纪

基于素数的课题很多，其中很多都有悠久的历史背景。本节介绍的是与素数有关的两个新案例，其求解是穷举运用的典范。

2.6.1 合数世纪探求

1. 案例提出

由求区间素数的程序可知20世纪的100个年号[1901—2000]中有13个素数，而21世纪的100个年号[2001，2100]中有14个素数。

那么，是否存在一个世纪的100个年号中一个素数都没有？

定义一个世纪的100个年号中不存在一个素数，即100个年号全为合数的世纪称为合数世纪。设计程序探索最早的合数世纪。

这一与素数探求相关的趣题最早于1996年由杨克昌教授在《中国电脑教育报》“编程实践”栏中提出并设计求解。

2. 设计要点应用穷举搜索，设置a世纪的的50个奇数年号(偶数年号无疑均为合数)为b，用k试商判别b是否为素数，用变量s统计这50个奇数中的合数的个数。

对于a世纪，若s=50，即50个奇数都为合数，找到a世纪为最早的合数世纪，打印输出后退出循环结束。

3. 合数世纪程序设计 // 合数世纪探求 #include #include void main()

{long a,b,k; int s,x; a=1;

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

{x=1;break;}

if(x==0)break; // 当前为非合数世纪时，跳出循环进行下一个世纪的探求 s=s+x; // 年号b为合数时，x=1，s增1 }

if(s==50) // s=50，即50个奇数均为合数 { printf(\最早出现的合数世纪为 %ld 世纪!\\n\

break; }

} }

4. 程序运行示例运行程序，得

最早出现的合数世纪为 16719 世纪!

16719 世纪的100个年号为[1671801，1671900]，这一区间中的100个整数全为合数。这是一个非常漫长的年代，可谓天长地久，地老天荒！

2.6.2 最小连续n个合数

1. 案例提出

最小的连续3个合数为[8,10]，最小的连续5个合数为[24,28]。试求出最小的连续n个合数。（其中n是键盘输入的任意正整数。）

这一问题与合数世纪问题密切相关，解的存在性无庸置疑。对任意正整数n，总存在连续n个合数。例如，n=100时,易知101!+2,101!+3,...,101!+101为连续100个合数，它们分别被2,3,...,?101整除。

然而，要具体找出最小的连续n个合数谈何容易,?这不是一般简单推理所能完成的。 2. 设计要点

求出区间[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+1,f+n]后结束；否则，作赋值f=m，为求下一个素数作准备。

如果在区间[c,d]中没有满足条件的解，则作赋值：c=d+2，d=c+10000，继续试商下去，直到找出所要求的解。 3. 程序实现

// 求最小的连续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转下一轮 }

}

4 程序运行示例

求最小的n个连续合数,输入n(2--100): 50 最小的50个连续合数区间为:[19610,19659]。

求最小的n个连续合数,输入n(2--100): 100

最小的100个连续合数区间为: [370262，370361]。

建议：运行前面求区间素数的程序验证这些区间上是否存在素数。

2.7 三阶素数方阵

通常的n阶幻方由1,2,...,n2构成的各行、各列与两对角线之和均相等n行n列方阵。素数幻方全是由素数构成的各行、各列与两对角线之和均相等方阵。

2.7.1 指定区间的三阶素数方阵

1. 案例提出

试在区间[300,600]找出9个素数，构成一个3阶素数幻方，使得该方阵中3行、3列与两对角线上的3个数之和均相等。

2. 设计要点

试在一般区间[c,d]找出9个素数，构成一个3阶素数幻方，使得该方阵中3行、3列与两对角线上的3个数之和均相等。如果有解，统计有多少个解？这是一个新颖的有一定难度的问题。

设置a数组，数组元素清“0”。通过试商判别，寻找出[c,d]中的所有素数k，并标注a[k]=1，为以后的判断提供依据。

设方阵正中间数为n，幻和(即每行,每列与每对角线之和)为s。?注意到

(中间一行)+(中间一列)+2*(两对角线)=6s (上下行)+(左右列)=4s 两式相减即得

6n=2s → n=s/3

这意味着凡含n的行或列或对角线的三数中，除n之外的另两数与n相差等距。为此，设方阵为:

n-x n+w n-y n+z n n-z n+y n-w n+x

同时设方阵的两对角线的三数为大数在下(即x,y>0)，下面一行三数为大数在右(即x>y)。这样约定是避免重复统计解。

显见,上述3×3方阵的中间一行，中间一列与两对角线上三数之和均为3n。?要使左右两列，上下两行的三数之和也为3n，当且仅当

z=x-y

w=x+y (x>y)

同时易知9个素数中不能有偶素数2，因而x，y，z，w都只能是正偶数。 ? 穷举[c,d]中的素数n，穷举y，x，并按上述两式得z，w：

若出现x=2y，将导致z=y，方阵中出现两对相同的数，显然应予排除。

显然n-w是9个数中最小的，n+w是9个数中最大的。若n-wd，已超出[c,d]界限，应予以排除。另外，由于n+x≤d且n+y≤d且x>y，所以y≤d-n-1和x≤d-n。? 检测方阵中其他8个数是否是素数，引用变量t1,t2，t1*t2为8个数的标记之积。若t1*t2=0，即8个数中存在非素数，返回。否则，已找到一个三阶素数幻方解，按方阵格式输出并用变量m统计基本解的个数。

这样处理，能较快的找出所有解，既无重复，也没有遗漏。

3. 三阶素数幻方程序设计

// 指定区间内素数构造三阶素数幻方 #include #include void main()

{int c,d,j,k,n,t,t1,t2,w,x,y,z,m=0; int a[3000];

printf(\请确定区间下限c,上限d: \ scanf(\ if(c%2==0) c=c+1;

for(k=c;k<=d;k++) a[k]=0; for(k=c;k<=d;k+=2)

{for(t=0,j=3;j<=sqrt(k);j+=2) if(k%j==0) {t=1;break;}

if(t==0) a[k]=1; // [c,d]中的奇数k为素数，标注1 } for(k=c;k

{n=k; // 探索合适的 n,x,y for(y=2;y<=d-n-1;y+=2)

for(x=y+2;x<=d-n;x+=2) { z=x-y;w=x+y;

if(x==2*y || n-wd)

continue; // 控制幻方的素数范围 t1=a[n-w]*a[n+w]*a[n-z]*a[n+z]; t2=a[n-x]*a[n+x]*a[n-y]*a[n+y];

if(t1*t2==0) continue; // 控制其余8个均为素数

m++;

printf(\统计并输出三阶素数幻方 printf(\ printf(\ printf(\ } }

printf(\共 %d 个素数方阵.\\n\ }

4. 程序运行示例

请确定区间下限c,上限d: 300,600 NO 1: 401 563 419 479 461 443 503 359 521 共 1 个素数方阵.

2.7.2 指定幻和的三阶素数方阵

1. 案例提出

试寻求9个素数，构造一个3阶素数幻方，使得该素数方阵中3行、3列与两对角线上的3个素数之和均等于给定的整数s。

2. 设计要点

按前例构造9数组成的方阵。

对于键盘输入的整数s, 如果存在幻和为s的素数幻方，则s应为中间素数的3倍。设n=s/3，若通过试商知n不是素数，显然不存在幻和为s的素数幻，显示“此时无解！”后结束。

若n=s/3是一个素数，确定素数幻方中素数取值的上限d=s-8，并在[3,d]范围内确定x,y,w,z,并检测8个数n-x，n+w，n-y，n+z，n-z，n+y，n-w，n+x是否同时为素数。若同时为素数，即可按以上规定作输出，并用m统计解的个数。

3. 程序实现

// 指定幻和的三阶素数幻方 #include #include void main()

{int c,d,j,k,n,t,t1,t2,s,w,x,y,z,m; int a[3000];

printf(\请确定素数幻方的幻和s: \

scanf(\ n=s/3;m=0;

c=3;d=s-8; // 确定幻和为s时素数的最大最小区间 for(k=c;k<=d;k++) a[k]=0; for(k=c;k<=d;k+=2) {for(t=0,j=3;j<=sqrt(k);j+=2) if(k%j==0)

{t=1;break;} if(t==0) a[k]=1; // [c,d]中的奇数k为素数，标注1 }

if(a[n]==0)

{ printf(\幻和为%d时无解! \\n\for(y=2;y<=d-n-1;y+=2)

for(x=y+2;x<=d-n;x+=2) { z=x-y;w=x+y;

if(x==2*y || n-wd) continue; // 控制幻方的素数范围

t1=a[n-w]*a[n+w]*a[n-z]*a[n+z]; t2=a[n-x]*a[n+x]*a[n-y]*a[n+y];

if(t1*t2==0) continue; // 控制其余8个均为素数 m++; printf(\统计并输出三阶素数幻方 printf(\ printf(\

printf(\}

printf(\共 %d 个素数方阵.\\n\ }

4. 程序运行示例

请确定素数幻方的幻和s: 789 NO 1:

173 359 257 347 263 179 269 167 353 NO 2:

137 419 233 359 263 167 293 107 389 共 2 个素数方阵.

2.8 穷举设计的改进与优化

应用穷举设计求解比较简单，不存在太多难点，但也不能太随意。

实际上，穷举结构的设置，穷举参数的选取，都有很多值得我们观注与思考的地方，自然也存在很多改进与优化的空间。

2.8.1 整币兑零

1. 案例提出

计算把一张1元整币兑换成1分、2分、5分、1角、2角和5角共6种零币的不同兑换种数。

进一步计算把一张2元整币与一张5元整币兑换成上述6种零币的不同兑换种数。 2. 穷举设计求解设整币的面值为n个单位，面值为1、2、5、10、20、50单位零币的个数分别为p1, p2, p3, p4, p5, p6。显然需解一次不定方程

p1+2*p2+5*p3+10*p4+20*p5+50*p6=n (p1, p2, p3, p4, p5, p6为非负整数) 对这6个变量实施穷举，确定穷举范围为0≤p1≤n, 0≤p2≤n/2, 0≤p3≤n/5, 0≤p4≤n/10, 0≤p5≤n/20, 0≤p6≤n/50。

在以上穷举的6重循环中，若满足条件 p1+2*p2+5*p3+10*p4+20*p5+50*p6=n

则为一种兑零方法，输出结果并通过变量m增1统计不同的兑换种数。 3. 穷举求解C程序设计 // 整币兑零穷举设计1 #include void main()

{int p1,p2,p3,p4,p5,p6,n; long m=0;

printf(\

printf(\分 2分 5分 1角 2角 5角 \\n\ for(p1=0;p1<=n;p1++) for(p2=0;p2<=n/2;p2++) for(p3=0;p3<=n/5;p3++)

for(p4=0;p4<=n/10;p4++) for(p5=0;p5<=n/20;p5++) for(p6=0;p6<=n/50;p6++)

if(p1+2*p2+5*p3+10*p4+20*p5+50*p6==n) // 根据条件检验 {m++;

printf(\ printf(\ }

printf(\}

运行程序，输入100，即得1元整币兑换成1分、2分、5分、1角、2角、5角共6?种零币的不同兑换方法及种数为：

1分 2分 5分 1角 2角 5角 0 0 0 0 0 2 0 0 0 0 5 0 0 0 0 1 2 1 ??

100(1,2,5,10,20,50)=4562

共有4562个解，即有4562种不同的兑换种数。 4. 精简穷举循环设计

在上述程序的6重循环中，我们可精简p1循环，在循环内应用 p1=n-(2*p2+5*p3+10*p4+20*p5+50*p6) 给p1赋值。如果p1为非负数，对应一种兑换法。

// 精简循环设计2 #include void main()

{int p1,p2,p3,p4,p5,p6,n; long m=0; printf(\

printf(\分 2分 5分 1角 2角 5角 \\n\

for(p2=0;p2<=n/2;p2++) // 已精简了p1循环 for(p3=0;p3<=n/5;p3++) for(p4=0;p4<=n/10;p4++) for(p5=0;p5<=n/20;p5++) for(p6=0;p6<=n/50;p6++)

{p1=n-(2*p2+5*p3+10*p4+20*p5+50*p6); // p1为一分币的个数 if(p1>=0) {m++;

printf(\ printf(\ } }

printf(\}

运行程序，输入200，即得2元整币兑换成1分，2分，5分，1角，2角，5角共6?种零币的不同兑换种数为

200(1,2,5,10,20,50)=69118

精简穷举循环设计使穷举循环次数缩减为以上设计的1/n。 5. 穷举设计的进一步优化以上程序的循环次数已经大大精简了。进一步的分析，我们看到在程序的循环设置中，p3循环从0～n/5可改进为0～(n-2*p2)/5，因为在n中p2已占去了2*p2。依此类推，对p4, p5, p6的循环可作类似的循环参量优化。

// 优化穷举设计3 #include

void main()

{int p1,p2,p3,p4,p5,p6,n; long m=0; printf(\

printf(\分 2分 5分 1角 2角 5角 \\n\

for(p2=0;p2<=n/2;p2++)

for(p3=0;p3<=(n-2*p2)/5;p3++) // 缩减p3,p4,p5,p6循环范围 for(p4=0;p4<=(n-2*p2-5*p3)/10;p4++)

for(p5=0;p5<=(n-2*p2-5*p3-10*p4)/20;p5++) for(p6=0;p6<=(n-2*p2-5*p3-10*p4-20*p5)/50;p6++) {p1=n-(2*p2+5*p3+10*p4+20*p5+50*p6); if(p1>=0) {m++;

printf(\ printf(\ }

}

printf(\}

运行程序，输入n=500，即得5元整币兑换成1分、2分、5分、1角、2角、5角共6?种零币的不同兑换种数为

500(1,2,5,10,20,50)=3937256 6. 以上3个穷举设计比较

以上3个穷举求解程序体现了程序的改进与优化过程，因循环设置的差异与循环参量的不同，直接影响程序求解的速度。

由以上穷举设计1到精简循环改进设计2，到进一步优化设计3，循环次数逐步精简，程序运行时间逐步缩减。测试3个穷举算法中条件判断语句执行次数如表2.1所示。

表2.1

n取值整币兑零穷举设计1 精简循环设计2 优化穷举设计3 3个穷举算法中条件判断语句执行次数比较

100 21 417 858 212 058 4 562 200 961 353 855 4 782 855 69 118 500 1.8e+11 369 769 686 3 937 256 由表2.1所列举的数据可见，求解同一个问题的穷举设计，精简循环的求解时间缩减为原穷举设计的数百分之一，而优化算法的求解时间缩减为精简循环设计的数百分之一。由此可见，算法的改进与优化对于提高求解效率的作用。

由于穷举计算所需的时间随n增加而迅速增加，以致当n比较大或所兑零币种数增多时求解变得无望，改进算法才能快速解决整币兑零种数问题。

2.8.2 完美综合式

1. 案例提出

把数字1,2,...,9这9个数字填入以下含加减乘除与乘方的综合运算式中的9个□中,?使得该式成立

□^□+□□÷□□-□□×□=0

要求数字1,2,...,9这9个数字在各式中都出现一次且只出现一次，且约定数字“1”不出现在乘、乘方的一位数中（即排除各式中的各个1位数为1这一平凡情形）。

2. 设计要点

式中含有加减乘除与乘方5种运算，求解难度更大些。

设式右的6个整数从左至右分别为 a,b,z,c,d,e,其中z,c,d为2位整数，a,b,e为大于1的一位整数。因式中有乘方，6个变量设置为double型。

设置a,b,c,d,e,z循环，对每一组a,b,c,d,e,z，进行以下检测: （1）若z不是c的倍数, 即fmod(z,c)!=0，则返回继续；（2）若等式不成立，即pow(a,b)+z/c!=d*e, 则返回继续；（3）式中9个数字是否存在相同数字。

对6个整数共9个数字进行分离，分别赋值给数组f[1]——f[9]。连同附加的f[0]=0，共10个数字在二重循环中逐个比较：

若存在相同数字，t=1，不作输出。

若不存在相同，即式中9 个数字为1——9不重复，保持标记t=0, 则输出所得的完美综合运算式。

设置n统计解的个数。 3. 程序实现

// 含乘方的完美综合运算式

#include #include void main()

{double a,b,c,d,e,z; int j,k,t,n,f[11];

printf(\□^□+□□/□□-□□*□=0 \\n\ n=0;

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

for(b=2;b<=9;b++) for(c=12;c<=98;c++)

for(d=12;d<=98;d++) // 对a,b,c,d,e 实施穷举

for(e=2;e<=9;e++) for(z=12;z<=98;z++)

{if(fmod(z,c)!=0) continue;

if(pow(a,b)+z/c!=d*e) continue; t=0;

f[0]=0;f[1]=a;f[2]=b;f[3]=e; // 9个数字赋给f数组 f[4]=fmod(c,10);f[5]=floor(c/10); f[6]=fmod(d,10);f[7]=floor(d/10); f[8]=fmod(z,10);f[9]=floor(z/10); for(k=0;k<=8;k++)

for(j=k+1;j<=9;j++) if(f[k]==f[j])

{t=1; break;} // 检验数字是否有重复 if(t==0)

{ n++; // 输出一个解，用n统计个数

printf(\printf(\ } } }

4. 程序运行结果

□^□+□□/□□-□□*□=0

1: 3^5+87/29-41*6=0 2: 7^3+28/14-69*5=0 3: 7^3+82/41-69*5=0

5. 完美综合运算式优化 (1) 优化设计要点

所有量设置在整数范围内取值，其中a^b用a自乘b次即可。即要求的综合运算式为

a^b+z/c-d*e=0

设置a,b,c,d,e循环，对每一组a,b,c,d,e，计算z=(d*e-a^b)*c。同样是穷举，这样处理，可省略z循环，同时省略z是否能被c整除，省略等式是否成立的检测。

计算z后，只要检测z是否为二位数即可。若计算所得z非二位数，则返回。然后分别对6个整数进行数字分离，设置f数组对6个整数分离的共9个数字进行统计，f(x)即为数字x(1—9)的个数。

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

若所有f(x)全为1，满足数字1,2,...,9这九个数字都出现一次且只出现一次，保持标记t=0, 则输出所得的完美综合运算式。

(2) 优化程序设计

// 完美综合运算式优化

#include #include void main()

{int a,b,c,d,e,k,t,n,x,y,z,m[7],f[10]; printf(\□^□+□□/□□-□□*□=0 \\n\ n=0;

for(a=2;a<=9;a++) for(b=2;b<=9;b++)

for(c=12;c<=98;c++)

for(d=12;d<=98;d++) // 对a,b,c,d,e 实施穷举 for(e=2;e<=9;e++)

{ for(t=1,k=1;k<=b;k++) t=t*a;

z=(d*e-t)*c;

if(z<10 || z>98) continue;

m[1]=a;m[2]=b;m[3]=c;m[4]=d;m[5]=e;m[6]=z;

for(x=0;x<=9;x++) f[x]=0; for(k=1;k<=6;k++) { y=m[k]; while(y>0)

{ x=y;f[x]=f[x]+1;

y=y/10; // 分离数字f数组统计 }

}

for(t=0,x=1;x<=9;x++)

if(f[x]!=1) {t=1;break;} // 检验数字1-9各出现一次 if(t==0) // 输出一个解，用n统计个数 { n++;

printf(\printf(\

} } }

优化程序还是得到以上三个解，但可读性好，且运行要快得多。

2.8.3 和积三角形

1. 案例提出

把和为正整数s（s≥36）的8个互不相等的正整数填入8数字三角形(如图1所示)中，若三角形三边上的数字之和相等(s1)且三边上的数字之积也相等(s2)，该三角形称为和积三角形。

图1 8数字三角形

1) 存在和积三角形,s至少为多大? 写出此时的和积三角形。

2) s=89时存在多少个不同的和积三角形? 分别写出此时的和积三角形。

2. 求解要点

把和为s的8个正整数存储于b数组b(1)，?，b(8)，分布如图2所示。为避免重复，不妨约定三角形中数字“下小上大、左小右大”，即 b(1)

b(4) b(3) b(5) b(2) b(6) b(1) b(8) b(7)

图2 b数组分布示意图

可以根据约定对b(1)、b(7)的值进行循环探索，设置:

b(1)的取值范围为1—(s-21)/2；（因除b(1),b(4)外其他6个数之和至少为21） b(7)的取值范围为b(1)+1—(s-28)；（因其他7个数之和至少为28） b(4)的取值范围为1—(s-28)；（因其他7个数之和至少为28）同时据b(2)

b(8)=s-(b(1)+b(2)+b(3)+b(4)+b(5)+b(6)+b(7)) 对所取的8个整数，进行以下4道检测： 1）若b(8)<=0，则返回；

2）若这8个数出现相同数，则返回；

3）若三边之和不等，则返回； 4）若三边之积不等，则返回；

凡通过以上4道检测，即为一个解，打印输出，并用n统计解的个数。 3. 和积三角形C程序设计 #include void main()

{ int k,j,t,s,s1,s2,n,b[9];

printf(\请输入s:\printf(\ n=0; for(b[1]=1;b[1]<=(s-21)/2;b[1]++) for(b[7]=b[1]+1;b[7]<=s-28;b[7]++) for(b[4]=1;b[4]<=s-28;b[4]++) for(b[2]=1;b[2]<=(s-21)/2;b[2]++) for(b[3]=b[2]+1;b[3]<=s-28;b[3]++) for(b[6]=1;b[6]<=(s-21)/2;b[6]++) for(b[5]=b[6]+1;b[5]<=s-28;b[5]++)

{ b[8]= s-(b[1]+b[2]+b[3]+b[4]+b[5]+b[6]+b[7]); if(b[8]<=0) continue; t=0; for(k=1;k<=7;k++) for(j=k+1;j<=8;j++) if(b[k]==b[j]) {t=1;k=7;break;}

if(t==1) continue;

s1= b[1]+b[2]+b[3]+b[4];

if(b[4]+b[5]+b[6]+b[7]!=s1 || b[1]+b[8]+b[7]!=s1)

continue;

s2=b[1]*b[2]*b[3]*b[4];

if(b[4]*b[5]*b[6]*b[7]!=s2 || b[1]*b[8]*b[7]!=s2) continue; n++;

printf(\ for(k=2;k<=8;k++) printf(\

printf(\

}

printf(\共%d个解。\\n\}

4. 程序运行示例与讨论

(1）输入n=36——44，没有解输出。输入n=45，得一个解

1: 2, 8, 9, 1, 4, 3, 12, 6 s1=20, s2=144 此和积三角形如图所示。

1 9 4 8 3 2 6 12

可见s至少为45时，才出现和积三角形。 (2）输入n=89，得4个解

1: 6, 14, 18, 1, 9, 8, 21, 12 s1=39, s2=1512 2: 8, 12, 15, 1, 16, 9, 10, 18 s1=36, s2=1440 3: 8, 4, 27, 2, 12, 3, 24, 9 s1=41, s2=1728 4: 15, 9, 16, 1, 12, 10, 18, 8 s1=41, s2=2160

(3）以上穷举程序设计是可行，运行速度太慢。例如，输入s=89，得到以上4个解需等待较长时间。为了提高求解效率，必须从循环设置入手。 5. 穷举设计的改进

(1) 增加s+b(1)+b(7)+b(4)是否为3的倍数检测。

注意到三个角的元素在计算三边时各计算了两次，即s+b(1)+b(7)+b(4)＝3*s1,则在b(1),b(4),b(7)循环中增加对s+b(1)+b(7)+b(4)是否能被3整除的检测。

若(s+b(1)+b(7)+b(4))%3≠0，则continue继续探索；否则，记s1=(s+b(1)+b(7)+b(4))/3。（2）精简循环，把7重循环精简为5重。

可以根据约定对b(1)、b(7)的值进行循环探索，设置: b(1)的取值范围为1—(s-21)/2；（因除b(1),b(4)外其他6个数之和至少为21） b(7)的取值范围为b(1)+1—(s-28)；（因其他7个数之和至少为28） b(4)的取值范围为1—(s-28)。(因其他7个数之和至少为28) （3）根据约定对b(3)、b(5)的值进行探索，设置：

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)；同时根据各边之和为s1，计算出b(2)、b(6)和b(8)： b(2)=s1-b(1)-b(4)-b(3) b(6)=s1-b(4)-b(5)-b(7) b(8)=s1-b(1)-b(7)

（4）精简了关于b(8)是否为正的检测，也精简了三边和是否相等的检测。只需检测b数组存在相同正整数与三边积是否相同即可。

(5) 改进穷举的程序实现 #include void main()

{ int k,j,t,s,s1,n,b[9]; long s2;

printf(\请输入s:\ n=0;

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

for(b[4]=1;b[4]<=s-28;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[6]=s1-b[4]-b[7]-b[5];

b[8]=s1-b[1]-b[7]; t=0; for(k=1;k<=7;k++) for(j=k+1;j<=8;j++)

if(b[k]==b[j])

{t=1;k=7;break;} if(t==1) continue;

s2=b[1]*b[2]*b[3]*b[4];

if(b[4]*b[5]*b[6]*b[7]!=s2 || b[1]*b[8]*b[7]!=s2)

continue; n++;

printf(\

for(k=2;k<=8;k++) printf(\

printf(\

}

printf(\共%d个解。\\n\

}

(6) 改进后程序运行示例

运行以上改进穷举的程序，当s=45与s=89时所得解与前相同，时间大大缩短。对于更大的s值，例如s=300，可得请输入s:300

1: 13, 6, 93, 4, 78, 3, 31, 72 s1=116, s2=29016 2: 13, 16, 90, 2, 65, 6, 48, 60 s1=121, s2=37440 3: 19, 16, 90, 2, 57, 8, 60, 48 s1=127, s2=54720

4: 36, 14, 77, 2, 66, 12, 49, 44 s1=129, s2=77616 5: 39, 1, 50, 72, 13, 2, 75, 48 s1=162, s2=140400 6: 40, 9, 90, 2, 50, 8, 81, 20 s1=141, s2=64800 7: 45, 2, 18, 102, 6, 5, 54, 68 s1=167, s2=165240

共7个解。

对于原穷举程序，求解s=300就非常困难了。

习题2

2.1 6位分段和平方数

把一个6位整数分为前后两个3位数，若该数等于所分两个3位数和的平方，则称该数为6位分段和平方数。试求出所有6位分段和平方数。 2.2 解不等式

2000?12?23???nn?1?2011

2.3 解Pell方程

试求解方程： x-29y=1

的非平凡（排除x,y为0或1）正整数解。

2.4 分解质因数

对给定区间[m,n]的正整数分解质因数,?每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。

例如, 2012=2*2*503, 2011=(素数!)。 2.5 基于素数的代数和的最大最小定义和：