超难奥数题之数论专题：穷举用技巧

第三讲穷举法一、穷举法的基本概念穷举方法是基于计算机特点而进行解题的思维方法。

一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的公式或规则）时，可以根据问题中的的部分条件（约束条件）将所有可能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。

这样解决问题的方法我们称之为穷举算法。

穷举算法特点是算法简单，但运行时所花费的时间量大。

有些问题所列举出来的情况数目会大得惊人，就是用高速的电子计算机运行，其等待运行结果的时间也将使人无法忍受。

因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。

二、穷举算法模式穷举算法模式：(1)问题解的可能搜索的范围：用循环或循环嵌套结构实现(2)写出符合问题解的条件。

(3)能使程序优化的语句，以便缩小搜索范围，减少程序运行时间。

三、使用穷举法设计算法穷举法应用很多，比如一些密码破译软件通常就是用的穷举算法。

如在QQ上，OicqPassOver这个工具穷举你的口令，它根据机器性能最高可以每秒测试20000个口令，如果口令简单，一分钟内，密码就会遭到破译。

下面我们来以三个例子说明穷举法的具体应用。

实例一：古希腊人认为因子的和等于它本身的数是一个完全数（自身因子除外），例如28的因子是1、2、4、7、14，且1+2+4+7+14=28，则28是一个完全数，编写一个程序求2～1000内的所有完全数。

分析：(1)本题是一个搜索问题，搜索范围 2～1000，找出该范围内的完全数；(2)完全数必须满足的条件：因子的和等于该数据的本身。

(3)问题关键在于将该数的因子一一寻找出来，并求出因子的和。

程序如下：Program p3_1 ;Var a , b,s :integer ;BeginFor a:=2 to 1000 doBeginS:=0 ;For b:=1 to a -1 doIf a mod b =0 then s:=s+b ; { 分解因子并求和 }If a=s then beginWrite( a, ‘=’ ,1, );For b:=2 to a -1 doIf a mod b=0 then write( ’+’, b );Writeln ;End;End;End.当程序运行后，输出结果：6 = 1 + 2 + 328 = 1 + 2 + 4 + 7 + 14496 =1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248实例二：（第七届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题）在A，B两个城市之间设有N个路站(如下图中的S1，且N<100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20，且每条路段上的距离均为一个整数)。

Βιβλιοθήκη 穷举法一、引 入穷举法
实例一：输入绳子的长度n，将该绳子分成三段， 每段的长度为正整数，输出由该三段绳子组成的 三角形个数。
算法分析：没有公式直接求出三角形的个数,所以程 序只能采用穷举法,一一验证范围内的数是否能构成 三角形,若是则累计。
一、引 入
穷举法
s:=0; for a:=1 to n-2 do for b:=a to n-2 do for c:=b to n-2 do if (a+b>c) and (b+c>a) and (c+a>b) and (a+b+c=n) then s:=s+1;
四、穷举法 应用 实例二：有形如：ax +bx +cx+d=0 这样的
3 2
一个一元三次方程。给出该方程中各项的系数 (a，b，c，d 均为实数)，并约定该方程存在 三个不同实根(根的范围在-100至100之间)， 且根与根之差的绝对值>=1。要求由小到大依 次在同一行输出这三个实根(根与根之间留有 空格)，并精确到小数点后2位。 提示：记方程f(x)=0，若存在2个数x1和x2， 且x1<x2，f(x1)*(x2)<0，则在(x1，x2) 之间一定有一个 根。 样例 输入：1 -5 -4 20 输出：-2.00 2.00 5.00
穷举法
五、穷举算法 的深入应用 算法分析：
为了使得程序尽快运行出正确结果,程序中使用 了一个数组power存放所有数字的各次幂之值, power[i,j]等于i的j次方。变量currentnumber 存放当前要被验证的数,数组digit存放当前数的 各位数字,开始时digit[3]=1,其它元素均为0,此 时表示当前数为100。 highest为当前数的位数。

算法--穷举法
MR.CHEW 2018.11.22
导入
• 某个暑假你携带密码行李箱外出旅游，旅行中发现自己 忘记了开锁的密码，怎么办？
用穷举法设计程序
• 一、穷举法的基本思想
• 二、穷举法的程序实践
• 三、穷举算法总结
穷举法的基本含义
• 穷举法也称为“枚举法”或“列举法”。 • 穷举法，指在一个有穷的可能的解的集合中，一一列举 出集合中的每一个元素。用题目给定的检验条件来判断 该元素是否符合条件，若满足条件，则该元素为本问题 的一个解；否则，该元素就不是本问题的解。 • 穷举法在具体的程序实现过程中，可以通过循环和条件 判断语句来完成。 • 穷举法常用于解决“是否存在”或“有多少种可能”等类型的 问题
穷举法的应用举例
• 4.水仙花数问题
• 水仙花数是指一个三位数，它的各位数的立方和正好是 等于该数本身。例如153=1^3+5^3+3^3。请设计算法求 解该问题。
1.思路：三位数范围100--999 2.约束条件：该三位数的各位数的立方和正好是 等于该数本身 3.程序结构选择：1重循环
谢谢！
2.程序结构选择：2重循环
百钱百鸡
• 3.我国古代数学家张丘建在《算经》一书中提出的数学 问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。 百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？
1.思路：确定公鸡的范围，母鸡的范围，小鸡的 范围 2.约束条件：总共100元钱，100只鸡 3.程序结构选择：3重循环
1.思路：枚举所有情况1000--1999 2.约束条件：5人一组剩余1人，7个人一组还剩 两个人，8个人一组还剩3个人 3.程序结构选择：1重循环
穷举法的应用举例
• 2.鸡兔同笼

1，2 ， 3，4 ， 5
最优解Biblioteka 11, 3, 4 2，5 ，
5 4
3 2
4
三、回溯法：八皇后问题
要求在8×8格的国际象棋棋盘上摆放 要求在 × 格的国际象棋棋盘上摆放 8个皇后，使其不能互相攻击。由于 个皇后，使其不能互相攻击。由于 皇后的走棋法是可以横走、直走、走 斜线，每次走任意格数，所以要求这 八个皇后中的任意两个都不处于同一 行、同一列或同一斜线上。问有多少 种摆法？ 分析： 穷举法 穷举法”， 个皇后各占一行， 分析：“穷举法 ，8个皇后各占一行， 穷举每一行上可能占有的列，再排除 不合条件的情况，只输出合理的解。
表示一个皇后的控制范围（续）
同理，从左下角到右上角的主对角线及平 行线(即斜率为 的各斜线)上， (行号 - 列 行线 即斜率为-1的各斜线 上， 行号 即斜率为 的各斜线 相等，从左到右的15条直线这种差值 号)相等，从左到右的 条直线这种差值 相等，从左到右的 分别为7, 分别为 6, 5, …，0, -1, -2，…，-7。 ， ， ， 。 用以下的变量来表示当摆设第i个皇后时， 用以下的变量来表示当摆设第 个皇后时， 前面几个皇后在各列、各± 前面几个皇后在各列、各± 对角线上的占 用情况 bool A[n]; // 第j行皇后 行皇后 bool B[2*n-1]; // 斜率为 的对角线 斜率为+1的对角线 bool C[2*n-1]; // 斜率为-1， C[i-j+7] 斜率为 ，
• 从人工模拟的角度可直接从第 个回溯 从人工模拟的角度可直接从第6个回溯 • 从算法的角度是继续试探第7个 从算法的角度是继续试探第 个
4
试探安排八个皇后（续2）
在回溯的过程中，应该抹掉前面试探 留下的标记，即恢复A[j]、B[i+j]、 留下的标记，即恢复 、 、 C[i-j+7]为未被占用状态，这样才能 为未被占用状态，这样才能 正确地开展下一步的试探。 不管是找到了解还是没有找到解都必 须抹掉以前的标记，并回溯。 这种回溯过程将逐步返回，使得各行 的皇后都能试探到各种可能的摆法

穷举算法及解题穷举算法及解题例12-1 古希腊人认为因子的和等于它本身的数是一个完全数（自身因子除外），例如28的因子是1、2、4、7、14，且1+2+4+7+14=28，则28是一个完全数，编写一个程序求2~1000内的所有完全数。

问题分析（1）本题是一个搜索问题，搜索范围2~1000，找出该范围内的完全数；（2）完全数必须满足的条件：因子的和等于该数的本身；（3）问题关键在于将该数的因子一一寻找出来，并求出因子的和：分解因子的方法比较简单，采用循环完成分解因子和求因子的和。

程序如下：program p12_1;var a,b,s:integer;beginfor a:=2 to 1000 dobegins:=0;for b:=1 to a-1 doif a mod b =0 then s:=s+b;if a=s then beginwrite(a,&#39;=&#39;,1,);for b:=2 to a-1 doif a mod b=0 then write(&#39;+&#39;,b);writeln;end;end;end.当程序运行后,输出结果:6=1+2+328=1+2+4+7+14496=1+2+4+8+16+31+62+124+248例12-3邮局发行一套票面有四种不同值的邮票,如果每封信所帖邮票张数不超过三枚,存在整数r,使得用不超过三枚的邮票,可以贴出连续的整数1、2、3、……、r来，找出这四种面值数，使得r值最大。

问题分析：本题则是知道每封信邮票数的范围(&lt;=3),邮票有四种类型，编程找出能使面值最大邮票。

其算法是：(1) 面值不同的四种邮票，每封信所贴邮票不超过3张；(2) 用这四种邮票贴出连续的整数，并且使r值最大；(3) 用穷举法，找出所有符合条件的解；(4) 本题用集合的方法统计邮票的面值，提高判重的速度。

设四种邮票的面值分别为：a,b,c,d,根据题意设：a&lt;b&lt;c&lt;d,因此a=1,用循环语句完成搜索。

第16章 穷举算法与实验穷举方法是基于计算机特点而进行解题的思维方法。

一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的公式或规则）时，可以根据问题中的的部分条件（约束条件）将所有可能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。

这样解决问题的方法我们称之为穷举算法。

穷举算法特点是算法简单，但运行时所花费的时间量大。

因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。

虽然穷举法效率并不高，但是适应一些没有明显规律可循的问题的解决。

因为穷举算法就是从所有可能的情况中搜索正确的答案，所以一般可按如下步骤： 第1步: 对于一种可能的情况，列举出来并计算其结果；第2步：判断结果是否满足要求，如果不满足则执行第1步来搜索下一个可能的情况，如果满足要求，则表示寻找到一个正确的答案，执行下一步操作，如寻找其他正确（合适）的答案或者中断循环。

16.1三角形数问题16.1.1 问题描述将 ,F ,E ,D ,C ,B ,A 这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。

求使三角形三条边上的变量之和相等的全部解。

如图就是一个解。

A 6B C 3 1D F 2 4E 516.1.2 问题分析程序引入变量123456,,,,,i i i i i i ，代表,F ,E ,D ,C ,B ,A 并让它们分别顺序取1至6的正整数，在它们互不相同的前提条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。

当这些变量取尽所有的组合后，程序就可得到全部可能的解。

细节见下面的程序。

【程序1】%穷举法解三角形数 for i1=1:6 for i2=1:6 if i1==i2 continue;endfor i3=1:6if i1==i3 || i2==i3continue;endfor i4=1:6if i1==i4 || i2==i4 || i3==i4continue;endfor i5=1:6if i1==i5 || i2==i5 || i3==i5 || i4==i5continue;endfor i6=1:6if i1==i6 || i2==i6 || i3==i6 || i4==i6 || i5==i6continue;endif i1+i2+i4==i1+i3+i6 && i1+i2+i4==i4+i5+i6fprintf ('%6d\n',i1) ;fprintf ('%4d%4d\n',i2,i3) ;fprintf ('%2d%4d%4d\n\n',i4,i5,i6) ;endendendendendendEnd16.1.3 问题讨论按穷举法编写的程序通常不能适应变化的情况。

任务二：编写求三位水仙花数程序
a=x\100 b=(x-a*100)\10 c=x-a*100-b*10
水仙花代码：
Dim x, a,b, c, i As Integer For x = 100 To 999 Step 1 a = i \ 100 b = (i - a * 100) \ 10 c= i - a * 100 - b * 10 If a^3 + b^3 + c^3 = x Then Print x End If Next x
穷举法的适用条件：
①求解对象应该是有限的； ②有穷举规则 ③一时找不出解决问题的更好途径时；
穷举法解决问题步骤：
通常可以从两个方面进行分析： ⑴确定范围：问题所涉及的情况有哪些，情况 的种数可不可以确定。 ⑵验证条件：分析出来的这些情

任务三：百钱买百鸡”


相传我国南北朝时，京城有个卖鸡的张姓老汉，他有一 个儿子非常聪明，尤其擅长算术，到十二三岁时已是远近闻 名的“小神童”了。当朝宰相听说后想试探个究竟，于是派 仆人到张老汉的店里打听鸡的价钱，张老汉告知“公鸡五文 钱一只，母鸡三文一只，小鸡一文三只”。于是，仆人给他 一百文钱，要求公鸡、母鸡、小鸡都要，数量不多不少正好 一百只，命他次日送到府上。这可难为了张老汉，他怎么凑 也凑不够这个数，只好问儿子。“小神童”不慌不忙，掐指 一算就给出了答案，第二天照数送到宰相府。宰相见难不倒 “小神童”，又让仆人给张老汉一百文钱，要求再买一百只 鸡，搭配方法不能和上次一样。结果“小神童”又很快给出 了答案，宰相暗暗称奇，想最后再试一次，谁知还是没有难 倒“小神童”。 这个故事就是我国古代数学名著《张邱建算经》里的百 鸡百钱问题。请用穷举法求解所有的组合方法。

【实例1-4】完美运算式

把数字1、2、…、9这9个数字填入以下含 加减乘除与乘方的综合运算式中的9个□中， 使得该式成立 □^□+□□÷□□-□□×□=0 要求数字1，2，…、9这9个数字在式中都 出现一次且只出现一次。
编程思路1


设式右的6个整数从左至右分别为 a、b、x、y、z、c， 其中x、y、z为2位整数，范围为12~98；a、b、c为一 位整数，范围为1~9。 设臵a、b、c、x、y、z循环，对穷举的每一组a、b、c、 x、y、z，进行以下检测：


若x不是y的倍数，即 x % y!=0，则返回继续下一次穷举。 若等式不成立，即a^b+x/y-z*c!=0，则返回继续下一次穷举。 式中9个数字是否存在相同数字。将式中6个整数共9个数字 进行分离，分别赋值给数组元素f[1]~f[9]。连同附加的 f[0]=0（为保证9个数字均不为0），共10个数字在二重循环 中逐个比较。
【实例1-2】4位分段和平方数

一个4位自然数分为前后两个2位数，若该 数等于所分两个2位数和的平方，则称为4 位分段和平方数。例如，2025=（20+25）2。
编写程序求出所有4位分段和平方数。
编程思路1

对所有的4位整数n进行穷举，n的范围为 1000~9999，共9000个数。对每个数n，分 离出高两位数x（x=n/100）和低两位数y （y=n%100），然后进行判断，若满足 n==(x+y)*(x+y)，则n是一个4位分段和平方 数。
编程思路2


按程序1的思路，穷举次数有99次，如果分别设三 个数为x、2x和3x，以x为枚举对象，则x的最小值 为123、最大值为329（因为下一个数 341*3=1023>987），穷举的范围就减少为107。 由于对x进行穷举，因此需要将3个三位数的各个位 上的数字分离出来。这9个数字可以像程序1中一样， 用A~I这9个变量来保存。在程序2中，我们采用另 外一种方法。定义一个一维数组a[9]，把组成整数x、 2x、3x的9个数字存放在数组a中。然后用一个二重 循环统计1~9这9个数字是否全在数组中出现。

【例 2】【分析】
6 只能表示为 5 1 或 1 12 1 ，所以恰好有 6 个约数的数要么能表示成某个
质数的 5 次方，要么表示为某个质数的平方再乘以另一个质数，100 以内符合前者 的只有 32 ，符合后者的数枚举如下：
22 3 32 2 52 2 72 2
22 5 32 5 52 3
【例 3】 黑板上写有 1、2、3、……、100 这 100 个自然数，甲、乙二人轮流每次每人划去一个数， 直到剩下两个数为止。如剩下的两数互质则判甲胜，否则判乙胜。 ⑴乙先划甲后划，谁有必胜策略？必胜策略是怎样的？ ⑵甲先划乙后划，谁有必胜策略？必胜策略是怎样的？
【例 4】 如果一个自然数的 2004 倍恰有 2004 个约数，这个自然数自己最少有多少个约数？
穷举用技巧
【例 1】
N 是一个各位数字互不相等的自然数，它能被它的每个数字整除。N 的最大值
是
。
【例 2】 如果连续 N 个自然数，每个自然数的数字和都不是 11 的倍数，则称这连续的 N 个自然数 为一条“龙”，n 为这条龙的长度。比如 1，2，3，…，28 就是一条龙，它的长度是 28。 问：龙的长度最长可以为多少？写出一条最长的龙。
1
测试题
【例 1】求所有能被 30 整除，且恰有 30 个不同约数的自然数。
【例 2】在1到100 中，恰好有 6 个约数的数有多少个？
答案：
【例 1】【分析】 由于 30 2 3 5 ，从质数的观点看整除，如果自然数 N 能被 30 整除，那么自然 数 N 至少含有三个质因数 2，3，5。设： N 2r1 3r2 5r3 。自然数 N 恰有 30 个不同的因数，根据约数的个数公式：（（（（r（1（ 1 r2 1 r3 1 30 2 3 5 。注意到 2 3 5 是三个约数之积，由此可知自然数 N 中质因数的个数恰好有 3 个。因此（（（（r（1（ 1 r2 1 r3 1 2 3 5 ，由此可知（（（（r1 r2 r3 必是（（1（ （ 2 4 的 一个排列。 综上所述，所求的自然数有： 2 32 54 ， 2 34 52 ， 22 3 54 ， 24 3 52 ， 24 32 5 ， 22 34 5 。

常⽤算法-穷举法穷举法⼜称为枚举法，它是在计算机算法设计中⽤得最多的⼀种编程思想。

它的实现⽅式是：在已知答案范围的情况下，依次地枚举该范围内所有的取值，并对每个取值进⾏考查，确定是否满⾜条件。

经过循环遍历之后，筛选出符合要求的结果来。

这种⽅法充分利⽤了计算机运算速度快的特点，思路简单直接，能够解决⼤部分的问题。

什么样的问题适合使⽤穷举法来解决呢？归纳起来，遇到了如下的三种情况，将优先考虑使⽤穷举法：1. 答案的范围已知：虽然事先并不知道确切的结果，但能预计到结果会落在哪个取值范围内。

譬如说：①求1－100之间所有的素数：⽆论结果如何，都在1－100的范围之内。

②求2000－2015年间有⼏个⽉的13号是周⽇？这15年间共有180个⽉，⽉份的个数最多不会超过180③验证1000以内的哥德巴赫猜想：即找出1000之内所有的合数，看是否能够分解为两个质数之和。

如果仔细观察，将会发现许多题⽬的结果范围都是已知的，都可以使⽤穷举法来实现。

2. 答案的结果是离散的，不是连续的。

如果要求出1－2之间所有的⼩数，就⽆法⽤穷举法来实现，因为其结果是⽆限连续的。

3. 对时间上的要求不严格。

蓝桥杯⽐赛中的许多题⽬对于算法的设计是有时间要求的，有时会⾮常苛刻。

如果⽤穷举法则耗时过长，不可取。

例如求出21位的⽔仙花数，使⽤穷举法可能会花费30分钟的时间。

⽽蓝桥杯试题通常要求时间限制在1秒钟之内完成，少数会延长⾄3分钟。

在这种情况下，必须使⽤新的算法来解决问题。

下⾯举个经典的例⼦：100块砖100⼈来搬，男⼈⼀⼈搬4块，⼥⼈⼀⼈搬3块，⼩孩3⼈抬⼀块，问男，⼥，⼩孩各⼏⼈？若设男，⼥，⼩孩⼈数分别为X， Y， Z，则只能够列出两个等式： X+Y+Z＝100 4*X+3*Y+Z/3＝100 。

三个未知数两个等式，⽆法求解。

这就只能够使⽤穷举法来实现，具体做法如下：先确定每种类型⼈员的数量的取值范围，由题意可知，男⼈X的取值范围是0~100/4＝25 ⼥⼈Y的取值范围是0~100/3＝33 ⼩孩的取值范围是0~99（必须不⼤于100且为3的倍数）。

change(b,n);
//b表示的二进制数增1
}
printf("\n");
}
解法2：采用增量穷举法求解1～n的幂集，当n=3时的求 解过程如图3.3所示，先产生一个空子集{}，在此基础上添加1 构成一个子集{1}，然后在{}和{1}各子集中添加2产生子集{2}、 {1,2}，再在前面所有子集中添加3产生子集{3}、{1,2}、{2,3}、 {1,2,3}，从而生成{1,2,3}的所有子集。
{} 初始值 {1} 添加 1
{2} {1 2} 添加 2
{3} {1 3} {2 3} {1 2 3} 添加 3
得到 1～3 的所有幂集 {} {1} {2} {1 2} {3} {1 3} {2 3} {1 2 3}
这种思路也是穷举法方法，即穷举1～n的所有子集。先 建立一个空子集，对于i（1≤i≤n），每次都是在前面已建立 的子集上添加元素i而构成若干个子集，对应的过程如下：
}
【例3.4】有n（n≥4）个正整数，存放在数组a中，设计 一个算法从中选出3个正整数组成周长最长的三角形，输出 该最长三角形的周长，若无法组成三角形则输出0。
解：采用穷举法，用i、j、k三重循环，让i<j<k避免正 整数被重复选中，设选中的三个正整数a[i]、a[j]和a[k]之和 为len，其中最大正整数为ma，能组成三角形的条件是两边 之和大于第三边，即ma<len-ma。
6=1+2+3 28=1+2+4+7+14
解：先考虑对于一个整数m，如何判断它是否为完全数。 从数学知识可知：一个数m的除该数本身外的所有因子都在 1～m/2之间。算法中要取得因子之和，只要在1～m/2之间 找到所有整除m的数，将其累加起来即可。如果累加和与m 本身相等，则表示m是一个完全数，可以将m输出。其循环

穷举算法穷举算法有点像数学上说的"完全归纳法",在问题答案可能的全部解集内逐一查询(测试)直到找出答案为止。

穷举算法的模式：⑴问题解的可能搜索的范围:用循环或循环嵌套结构。

⑵写出符合问题解的条件。

⑶能使程序优化的语句，以便缩小搜索范围，减少程序运行时间。

用穷举算法解决问题，通常可以从两个方面进行分析：一、问题所涉及的情况：问题所涉及的情况有哪些，情况的种数可不可以确定。

把它描述出来。

二、答案需要满足的条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。

把这些条件描述出来。

练习试题第一题：36 块砖， 36 人搬。

男搬 4 ，女搬 3 ，两个小儿抬一砖。

要求一次全搬完。

问需男、女、小儿各若干？第二题： A 、 B 、 C 、 D 、 E 五人夜间合伙捕鱼，凌晨时都疲倦不堪，各自在河边的树丛中找地方睡着了。

日上三竿， A 第一个醒来，他将鱼分作五份，把多余的一条扔回河中，拿自己的一份回家去了。

B 第二个醒来，也将鱼分作五份，扔掉多余的一条，拿走自己的一份，接着 C 、 D 、 E 依次醒来，也都按同样的办法分鱼，问五人至少合伙捕了多少条鱼？试编程序算出。

第三题：古希腊人认为因子的和等于它本身的数是一个完全数（自身因子除外），例如28的因子是1、2、4、7、14，且1+2+4+7+14=28，则28是一个完全数，编写一个程序求2-1000内的所有完全数。

第四题：一根29CM长的尺子，只允许在上面刻7个刻度，要能用它量出1-29CM的各种长度。

试问这根尺的刻度应该怎样选择？算法分析:⑴对于每一组刻度的选择都需要判断是否能将1-29CM的各种刻度量出来，例如选择的刻度为：a1、a2、a3、a4、a5、a6、a7，那么能量出的刻度为：a1a2a3a4a5a7a1，29- a1；2 a2，a2- a1，29- a2；3 a3，a3- a1，a3- a2，29- a3； 4 a4，a4- a1，a4- a2，a4- a3，29- a4；5 a5，a5- a1，a5- a2，a5- a3，a5- a4，29- a5；6 a6，a6- a1，a6- a2，a6- a3，a6- a4，a6- a5，29- a6；7 a7，a7- a1，a7- a2，a7- a3，a7- a4，a7- a5，a7- a6，29- a7；8共可量出2+3+4+5+6+7+8种刻度，即35种刻度，事实上其中有许多刻度是重复的，不可能覆盖1-29。

6种方法教你轻松解决奥数难题名师指点
在学奥数的时候要善于总结规律，就像任何绝妙的武功都会有几句要诀一样，再难的奥数题也离不开以下6种常用解法：
1 、直观画图法：解奥数题时，如果能合理的、科学的、巧妙的借助点、线、面、图、表将奥数问题直观形象的展示出来，将抽象的数量关系形象化，可使同学们容易搞清数量关系，沟通已知与未知的联系，抓住问题的本质，迅速解题。

2 、倒推法：从题目所述的最后结果出发，利用已知条件一步一步向前倒推，直到题目中问题得到解决。

3 、枚举法：奥数题中常常出现一些数量关系非常特殊的题目，用普通的方法很难列式解答，有时根本列不出相应的算式来。

我们可以用枚举法，根据题目的要求，一一列举基本符合要求的数据，然后从中挑选出符合要求的答案。

4 、正难则反：有些数学问题如果你从条件正面出发考虑有困难，那么你可以改变思考的方向，从结果或问题的反面出发来考虑问题，使问题得到解决。

5 、巧妙转化：在解奥数题时，经常要提醒自己，遇到的新问题能否转化成旧问题解决，化新为旧，透过表面，抓住问题的实质，将问题转化成自己熟悉的问题去解答。

转化的类型有条件转化、问题转化、关系转化、图形转化等。

6 、整体把握：有些奥数题，如果从细节上考虑，很繁杂，也没有必要，如果能从整体上把握，宏观上考虑，通过研究问题的整体形式、整体结构、局部与整体的内在联系，只见森林，不见树木，来求得问题的解决。

cmin>sum if (_____________) { cmin=sum; for (i=1;i<=n;i++) d[i]=b[i]; } j=n; b[j]==k while( _______ ) j=j-1; b[j]=b[j]+1; for(i=j+1;j<=n;j++) b[i]=1; ___________; } printf(“%40d”,cmin); for(i=1;i<=n;i++) printf(“%d”,d[i]); }
例1．找完全数 ． 古希腊人认为因子的和等于它本身的数是一个完全数（自身因子除外）。 例如28的因子是1、2、4、7、14，且1+2+4+7+14=28，则28是一个完 全数。编写一个程序求2~10000内的所有完全数。 分析： 分析 1.本题只需一个枚举变量a即可，它的范围是2~10000； 2.验证完全数的条件是：所有因子的和等于该数据本身； 3.找出所有因子、并求出因子和是关键的一步，可采用循环完成分解因 子和求因子和。
从上例可知，穷举法是一种比较笨拙的算法，因为它需要列举出许多个可能解来 一一验证，程序往往需要运行很长时间，效率较低。但是，穷举法也有自己的优 点，它思路简单，容易编写程序，只要时间足够，穷举法能够很容易地求出问题 的全部正确解。 针对穷举法效率较低的缺点，在设计穷举算法时，我们必须注意以下二点： ①考虑枚举变量一定要慎重，枚举变量应尽量少，尽量通过计算而不是枚举来确 定变量。 ②枚举前应尽可能多地将不符合条件的情况预先排除，以缩小枚举范围。
练习：2．将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可 得到一个各自的和s1,s2,……sk,定义整数P为: P=(S1-S2)^2+(S1一S3)^2+……+(S1-Sk)^2+(s2-s3)^2+……+(Sk-1Sk)^2 问题求解:求出一种分法,使P为最小(若有多种方案仅记一种) 程序说明: 程序说明: 数组: a[1],a[2],...a[n]存放原数 s[1],s[2],...,s[k]存放每个部分的和 b[1],b[2],...,b[n]穷举用临时空间 d[1],d[2],...,d[n]存放最佳方案

穷举法
四、穷举法应用
begin e:=15-a-b-c-d;b0:=(e<>2) and (e<>3);
m:=bton(e=1)+bton(b=2)+bton(a=5)+bton(c<>1)+bton(d=1);
b0:=b0 and (m=-2); b1:=(e=1) and (a<>2); b1:=b1 or (a=5) and(c<>1) and(c<>2); b1:=b1 or (c<>1) and (d<>1) and (d<>2); b1:=b1 or (d=1) and (e<>2); b0:=b0 and not b1; if b0 then
穷举法
四、穷举法应用
分析：本题是一个逻辑判断题，一般的逻辑判断题都采 分析：本题是一个逻辑判断题， 用穷举法进行解决。 我们对5 用穷举法进行解决 。 我们对 5 所学校所得名次的各种可 能情况进行穷举。在每种情况中， 能情况进行穷举。在每种情况中，为了防止不同学校取 相同的名次，设立了逻辑数组x x[I]为false表示已有 相同的名次，设立了逻辑数组x，x[I]为false表示已有 某校取第I 某校取第I名。 此题的难点在于确定判断条件。我们设立逻辑变量b0来 此题的难点在于确定判断条件。我们设立逻辑变量b 描述这一条件，主要有两个条件： 校不是第2 描述这一条件，主要有两个条件：“E校不是第2名或第 只有第1名和第2 名的学校的人猜对” 3 名 ” 与 “ 只有第 1 名和第 2 名的学校的人猜对 ” ， 后一 条件要判断： 是否只有两人说法正确？ 条件要判断：1）是否只有两人说法正确？2）说得正确 的人是否是取得第1名和第2名的学校的人？ 的人是否是取得第1名和第2名的学校的人？要判断是否 仅有两人说正确，须统计正确命题的个数。为此，设立 仅有两人说正确，须统计正确命题的个数。为此， 了函数bton 将逻辑量数值化。 bton， 了函数bton，将逻辑量数值化。

穷举策略前面几节我们看到，在问题的解可以用公式，或者按一定的规则、规律求出时，只要把这些规则用计算机的语言写出，问题就可以得到解决。

但也有些问题一时难以找到规律或公式，或者根本没有公式可循，这种情况下，我们可以利用计算机高速运算的特点，用穷举策略来解。

所谓穷举策略，原则上说，就是第一步只考虑问题的部分条件，根据这些条件，找到所有的满足这些部分条件的解，称为可行解。

然后用尚未考虑的条件去一一检验那些可行解，删去不符合条件的解，留下符合条件的解，就是整个问题的解。

【例题5-1】如图所示的8个格子中放入1～8八个数字，使得相邻的和对角线的数字之差不为1。

编程找出所有放法。

我们先不考虑后一条件，只考虑第一个条件，即把1～8八个数字放入8个格子中。

这是容易做到的，就是8个数字的全排列，共有 8!=40320种放法。

然后对这8!个可行解用后一个条件加以检验，输出符合条件的解。

对于后一个条件中“相邻”的判断，可以建立一个邻接表来解决：i│ 1 2 3 4 5 6 7 8 9 10 11 12 13 14──┼──────────────────────j 1│ 1 1 1 2 2 2 3 3 3 4 5 5 6 72│ 2 3 4 3 5 6 4 6 7 7 6 8 7 8表中表示哪两个格子是相邻的，link[i,1]和link[i,2]是相邻的格子的编号。

全排列的产生，可以用八重循环，也可以用专门的算法，程序留给同学们自己去完成。

利用穷举策略编制的程序，其运算量一般是很大的，因此如何提高算法效率是穷举算法一个很重要的问题。

一般应尽量减少可行解的个数，使得第二步的检验运算量尽可能地少。

例如对于例5-1，如何来优化算法呢?如果注意到b3和b6两个格子，与它们“相邻”的格子有6个，也就是说，放入这两个格子中的数，必须和6个数不连续，仅可以和一个数是连续的，这样的数只有2个，即1和8。

这样，b1，b3，b6，b8 4个格子中数的放法仅有两种可能：2、8、1、7和7、1、8、2。

开始
j←1 j≤9
N 结束 N Y
i←1 i≤9
Y
n←j*10+i
输出n i← i +1 j← j +1
问题4：打印输出由1、2……8、9这九个数 字组成的所有可能的二位数n。
#include<cstdio> using namespace std; int main() { int i,j; for (i=1;i<=9;i++) { for (j=1;j<=9;j++) { printf("%d\n",i*10+j); } } return 0; }
#include<cstdio> using namespace std; int main() { int x,y,z; for(x=0;x<=14;x++) for(y=0;y<=25;y++) if(7*x+4*y==100) { z=100-x-y; printf("x=%d,y=%d,z=%d\n",x,y,z); } x=0,y=25,z=75
【例5】：（百钱买百鸡问题）大约在公元5世纪，数学家张 邱建在他的《算经》中提出了一个闻名于后世的百钱百鸡问 题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一， 百钱买百鸡，翁、母、雏各几何？
1.算法分析与设计 (1) 以三种鸡的个数为枚举对象，分别设为x,y,z。根据题 意，可以列出下面的不定方程
用穷举法设计算法

问题1： 有一把锁和一串钥匙（共有10把钥匙）， 怎样找出所有开这把锁的钥匙？
用穷举法设计算法

穷举算法的概念： 穷举算法就是按问题本身的性质，通过多 重循环一一列举出该问题所有可能的解（不能 遗漏，也不能重复），并在逐一列举的过程中， 检验每个可能的解是否是问题的真正解，若是， 我们采用这个 复），检验每个可能的解。