问题求解与程序设计-枚举

1、朴秀峰枚举q 枚举是基于已有的知识进行答案猜测的一种问题求解策略。枚举是基于已有的知识进行答案猜测的一种问题求解策略。q 在求解一个问题时，通常在求解一个问题时，通常先建立一个数学模型，包括一组变量、以及先建立一个数学模型，包括一组变量、以及这些变量需要满足的条件这些变量需要满足的条件。问题求解的目标就是确定这些变量的值。问题求解的目标就是确定这些变量的值。根据问题的描述和相关的知识，能为这些变量分别确定一个大概的取根据问题的描述和相关的知识，能为这些变量分别确定一个大概的取值范围。在这个范围内值范围。在这个范围内对变量依次取值，判断所取的值是否满足数学对变量依次取值，判断所取的值是否满足数学

2、模型中的条件模型中的条件，直到找到，直到找到(全部全部)符合条件的值为止。符合条件的值为止。q 例如例如“求小于求小于 N 的最大素数的最大素数”。q 数学模型是：一个整型变量数学模型是：一个整型变量 n，满足，满足 (1) n 不能够被不能够被 2, n) 中的任意一中的任意一个素数整除；个素数整除；(2) n 与与 N 之间没有素数。之间没有素数。q 使用枚举应注意的问题使用枚举应注意的问题v 建立简洁的数学模型。数学模型中变量的数量要尽量少，它们之间建立简洁的数学模型。数学模型中变量的数量要尽量少，它们之间相互独立。相互独立。v 减小搜索的空间。利用已有的知识，缩小数学模型中各个变量的取

3、减小搜索的空间。利用已有的知识，缩小数学模型中各个变量的取值范围，避免不必要的计算。值范围，避免不必要的计算。v 采用合适的搜索顺序。对搜索空间的遍历顺序要与数学模型中的条采用合适的搜索顺序。对搜索空间的遍历顺序要与数学模型中的条件表达式一致。件表达式一致。枚举q 首先解决以下问题：首先解决以下问题：v 根据问题确定枚举量。根据问题确定枚举量。v 确定可能解的区间范围。确定可能解的区间范围。v 根据问题要求确定约束条件。根据问题要求确定约束条件。v 根据问题要求优化枚举策略，减少循环。根据问题要求优化枚举策略，减少循环。q 枚举法程序的基本框架：枚举法程序的基本框架：int n=0;for(i

4、=; i=; i+) if (约束条件约束条件) printf(); n+;/ 记录解的个数记录解的个数 程序举例q 6位分段和平方数位分段和平方数q 完美立方完美立方q 生理周期生理周期q 谁做的好事？谁做的好事？q 回文数问题回文数问题q 熄灯问题熄灯问题q 讨厌的青蛙讨厌的青蛙q 奥数问题奥数问题6位分段和平方数q 把一个把一个6位整数分为前后两个位整数分为前后两个3位数，若该数等于所分两个位数，若该数等于所分两个3位数和的平位数和的平方，则称该数为方，则称该数为6位分段和平方数。试求出所有的位分段和平方数。试求出所有的6位分段和平方数。位分段和平方数。问题的解空间：所有的问题的解空间：

5、所有的6位数位数100000, 999999枚举量枚举量 a 的枚举范围：的枚举范围：100000, 100001. . , 999999约束条件：约束条件：a 分为前后两个三位数分为前后两个三位数x和和y，且，且 (x+y)2=along int a, b, x, y;for(a=100000; a=999999; a+) b = (int)sqrt(a); if (a = b*b) x = a/1000; y = a%1000; if (b = x+y) printf(%ld , a); 6位分段和平方数q 把一个把一个6位整数分为前后两个位整数分为前后两个3位数，若该数等于所分两个位数，

6、若该数等于所分两个3位数和的平位数和的平方，则称该数为方，则称该数为6位分段和平方数。试求出所有的位分段和平方数。试求出所有的6位分段和平方数。位分段和平方数。问题的解空间：所有的问题的解空间：所有的 6 位平方数位平方数100000, 999999枚举量枚举量 b 的枚举范围：的枚举范围：sqrt(100000), . , sqrt(999999)可能的解：可能的解：a=b*b约束条件：约束条件：a 分为前后两个三位数分为前后两个三位数x和和y，且，且(x+y)2=a, 且且x+y=blong int a, b, x, y, m, n;m = (int)sqrt(100000);n = (i

7、nt)sqrt(999999);for (b=m; b=n; b+) a = b * b; x = a/1000; y = a%1000; if (b = x+y) printf(%ld , a);完美立方q 问题描述问题描述a3 = b3 + c3 + d3 为完美立方等式。例如为完美立方等式。例如 123 = 63 + 83 + 103。编写一个程序，对任给的正整数编写一个程序，对任给的正整数 N (N100)，寻找所有的四元组，寻找所有的四元组 (a, b, c, d)，使得，使得 a3 = b3 + c3 + d3 ，其中，其中 1 a, b, c, d N。输入样例输入样例 输出样例

8、输出样例 24Cube = 6, Triple = (3,4,5)Cube = 12, Triple = (6,8,10)Cube = 18, Triple = (2,12,16)Cube = 18, Triple = (9,12,15)Cube = 19, Triple = (3,10,18)Cube = 20, Triple = (7,14,17)Cube = 24, Triple = (12,16,20)完美立方int n, a, b, c, d;long int cube101;scanf(%d, &n );for ( int i = 1 ; i = n ; i+ ) cube

9、i = i*i*i;for ( a = 6 ; a = n ; a+ )for ( b = 2 ; b a - 1; b+ ) if (cubea cubeb + cubeb+1 + cubeb+2) break; for ( c = b+1 ; c a ; c+ ) if ( cubea cubeb + cubec + cubec+1) break; for ( d = c+1; d a ; d+ ) if ( cubea = cubeb + cubec + cubed ) printf( Cube = %d, Triple = (%d,%d,%d)n, a, b, c, d); break

10、; 生理周期q 问题描述问题描述人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为期长度为 23 天、天、28 天和天和33 天。每一个周期中有一天是高峰。在高峰天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何

11、时三个高峰落在同一天。每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是，下次出现

12、三个高峰同天的时间是12，则输出，则输出2（注意这里不是（注意这里不是3） 。生理周期输入样例输入样例 输出样例输出样例 0 0 0 00 0 0 1005 20 34 3254 5 6 7283 102 23 320203 301 203 40-1 -1 -1 -1Case 1: the next triple peak occurs in 21252 days.Case 2: the next triple peak occurs in 21152 days.Case 3: the next triple peak occurs in 19575 days.Case 4: the next

13、 triple peak occurs in 16994 days.Case 5: the next triple peak occurs in 8910 days.Case 6: the next triple peak occurs in 10789 days.q 输入数据输入数据输入四个整数：输入四个整数：p, e, i 和和 d。 p, e, i 分别表示体力、情感和智力高峰出现分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于是给定的时间，可能小于p, e, 或或 i。 所有给定时间是非负的并且小于所

14、有给定时间是非负的并且小于365, 所求的时间小于等于所求的时间小于等于21252。q 输出要求输出要求从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数） 。 生理周期q 假设从当年的第一天开始数，第假设从当年的第一天开始数，第 x天时三个高峰同时出现。天时三个高峰同时出现。q 符合问题要求的符合问题要求的 x 必需大于必需大于 d、小于等于、小于等于21252，并满足下列三个条件：，并满足下列三个条件：1) (x-p) % 23 = 02) (x-e) % 28 = 03) (x-i) % 33 = 0q 在搜索空间在搜索

15、空间d+1, 21252中，对每个猜测的答案都进行三个条件的判断，中，对每个猜测的答案都进行三个条件的判断，开销很大，也没有必要。开销很大，也没有必要。q 首先从搜索空间首先从搜索空间d+1，21252中找到符合条件中找到符合条件1)的全部时间，然后从这些的全部时间，然后从这些时间中寻找符合条件时间中寻找符合条件2)、3)的时间，可以将对条件的时间，可以将对条件2)、3)的判定次数减少的判定次数减少为原来的为原来的1/23。用同样的办法，可以继续减少对条件。用同样的办法，可以继续减少对条件3)的判定次数。的判定次数。q 对每一组数据，分别执行下列算法：对每一组数据，分别执行下列算法：1) 读入

16、读入 p, e, i, d2) 从从 d+1 循环到循环到21252， 找到第一个满足条件找到第一个满足条件1)的时间的时间a、并跳出循环、并跳出循环3) 从从 a 循环到循环到21252，找到第一个满足条件，找到第一个满足条件2)的时间的时间b、并跳出循环、并跳出循环4) 从从 b 循环到循环到21252，找到第一个满足条件，找到第一个满足条件3)的时间的时间x、并跳出循环、并跳出循环5) 输出输出 x-d生理周期 int p, e, i, d, j, no=1; scanf(%d%d%d%d, &p, &e, &i, &d); while(p!=-1 &am

17、p; e!=-1 & i!=-1 & d!=-1) for(j=d+1; j21252; j+) if (j-p)%23 = 0) break; for( ; j21252; j=j+23) if (j-e)%28 = 0) break; for( ; j21252; j=j+23*28) if (j-i)%33 = 0) break; printf(Case %d, no); printf(: the next triple peak occurs in %d days.n, j-d); scanf(%d%d%d%d, &p, &e, &i, &

18、;d); no+;谁做的好事？q 问题描述问题描述某校有四位同学中的一位做了好事，不留名，表扬信来了之后，校长某校有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。问这四位是谁做的好事。(1) A说：不是我。说：不是我。(2) B说：是说：是C。(3) C说：是说：是D。(4) D说：他胡说。说：他胡说。已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。找出做了好事的人。谁做的好事？char thisman;/* 表示要找的人表示要找的人 */把四个人说的四句话写成关系表达式把四

19、个人说的四句话写成关系表达式A说：不是我。说：不是我。 thisman != AB说：是说：是C。 thisman = CC说：是说：是D。 thisman = DD说：他胡说。说：他胡说。 thisman != D谁做的好事？1. 如何找到该人，一定是如何找到该人，一定是“先假设该人是做好事者，然后到每句话中去测先假设该人是做好事者，然后到每句话中去测试看有几句是真话试看有几句是真话”。“有三句是真话就确定是该人，否则换下一人再有三句是真话就确定是该人，否则换下一人再试试”。比如，先假定是比如，先假定是A同学，让同学，让thisman=A; 代入到四句话中代入到四句话中显然，不是显然，不是A

20、做的好事（四个关系表达式值的和为做的好事（四个关系表达式值的和为1）依次假定依次假定B, C, D同学。同学。谁做的好事？2. 从编写程序的角度看，实现枚举最好用循环结构从编写程序的角度看，实现枚举最好用循环结构for (k=1; k=4; k=k+1)thisman = 64+k;/ 产生被试者，依次给产生被试者，依次给/ thisman赋值为赋值为A,B,C,Dsum = (thisman!=A)/ A的话是否为真的话是否为真 +(thisman=C)/ B的话是否为真的话是否为真 +(thisman=D)/ C的话是否为真的话是否为真 +(thisman!=D);/ D的话是否为真的话是

21、否为真谁做的好事？#include int main()int k, sum;char thisman;for (k=1; k=4; k+)/ 产生被试者，依次给产生被试者，依次给thisman赋值为赋值为A,B,C,Dthisman = 64+k;sum = (thisman!=A) / A的话是否为真的话是否为真 +(thisman=C) / B的话是否为真的话是否为真 +(thisman=D) / C的话是否为真的话是否为真 +(thisman!=D); / D的话是否为真的话是否为真if (sum=3) printf(thisman is %cn, thisman);return 0;

22、回文数字谜q 问题描述问题描述人过大佛寺人过大佛寺，寺佛大过人寺佛大过人。人过大佛寺人过大佛寺*我我=寺佛大过人寺佛大过人这里面每一字都代表着一个数字，并且不同的字代表的数字不同，你能这里面每一字都代表着一个数字，并且不同的字代表的数字不同，你能把这些数字都找出来么把这些数字都找出来么?回文数字谜bool flag, IsUsed10;int number, revert_number, t, v;for(number=0; number100000; number+) flag = true; memset(IsUsed,0,sizeof(IsUsed); t = number; rever

23、t_number=0; for (int i=0; i5; i+) v = t % 10; revert_number = revert_number*10 + v; t /= 10; if (IsUsedv) flag = false; else IsUsedv=1; if(flag &( revert_number % number=0) v = revert_number / number; if ( v10 & !IsUsedv) printf(%d*%d=%dn,number,v,revert_number); 回文数字谜思考题思考题q (he)2=she请将请将 h

24、、e、s 代表的数字找出来。代表的数字找出来。q 赛软件赛软件*比赛比赛=软件比拼软件比拼试给出能使算式成立的所有答案。试给出能使算式成立的所有答案。熄灯问题q 问题描述问题描述有一个由按钮组成的矩阵，其中每行有有一个由按钮组成的矩阵，其中每行有 6 个按钮，共个按钮，共 5 行。每个按钮行。每个按钮的位置上有一盏灯。的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边上边、下边、左边、右边)的的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被

25、点亮。来是熄灭的，则会被点亮。在矩阵角上的按钮改变在矩阵角上的按钮改变3 盏灯的状态；盏灯的状态；在矩阵边上的按钮改变在矩阵边上的按钮改变4 盏灯的状态；盏灯的状态；其他的按钮改变其他的按钮改变5 盏灯的状态。盏灯的状态。熄灯问题熄灯问题q 问题描述问题描述根据上面的规则，我们知道：根据上面的规则，我们知道：1) 第第 2 次按下同一个按钮时，将抵消第次按下同一个按钮时，将抵消第1 次按下时所产生的结果。因次按下时所产生的结果。因此，每个按钮最多只需要按下一次。此，每个按钮最多只需要按下一次。2) 各个按钮被按下的顺序对最终的结果没有影响。各个按钮被按下的顺序对最终的结果没有影响。3) 对第对

26、第 1 行中每盏点亮的灯，按下第行中每盏点亮的灯，按下第2 行对应的按钮，就可以熄灭第行对应的按钮，就可以熄灭第1 行的全部灯。如此重复下去，可以熄灭第行的全部灯。如此重复下去，可以熄灭第1、2、3、4 行的全部灯行的全部灯。同样，按下第。同样，按下第1、2、3、4、5 列的按钮，可以熄灭前列的按钮，可以熄灭前5 列的灯。列的灯。熄灯问题输入样例输入样例 输出样例输出样例 20 1 1 0 1 01 0 0 1 1 10 0 1 0 0 11 0 0 1 0 10 1 1 1 0 00 0 1 0 1 01 0 1 0 1 10 0 1 0 1 11 0 1 1 0 00 1 0 1 0 0P

27、UZZLE #11 0 1 0 0 11 1 0 1 0 10 0 1 0 1 11 0 0 1 0 00 1 0 0 0 0PUZZLE #21 0 0 1 1 11 1 0 0 0 00 0 0 1 0 01 1 0 1 0 11 0 1 1 0 1熄灯问题q 用数组元素用数组元素 puzzleij 表示位置表示位置 (i, j)上灯的初始状态：上灯的初始状态：1 表示灯是被点表示灯是被点亮的；亮的；0 表示灯是熄灭的。表示灯是熄灭的。q 用数组元素用数组元素 pressij 表示为了让全部的灯都熄灭，是否要按下位置表示为了让全部的灯都熄灭，是否要按下位置(i, j)上的按钮：上的按钮：1

28、 表示要按下；表示要按下；0 表示不用按下。表示不用按下。 q 由于第由于第 0 行、第行、第 0 列和第列和第 7 列不属于按钮矩阵的范围，没有按钮，可列不属于按钮矩阵的范围，没有按钮，可以假设这些位置上的灯总是熄灭的、按钮也不用按下。以假设这些位置上的灯总是熄灭的、按钮也不用按下。q 其它其它 30 个位置上的按钮是否需要按下是未知的。因此数组个位置上的按钮是否需要按下是未知的。因此数组 press 共有共有230 种取值。种取值。(0 0)(0 1)(0 2)(0 3)(0 4)(0 5)(0 6)(0 7)(1 0)(1 1)(1 2)(1 3)(1 4)(1 5)(1 6)(1 7)

29、(2 0)(2 1)(2 2)(2 3)(2 4)(2 5)(2 6)(2 7)(3 0)(3 1)(3 2)(3 3)(3 4)(3 5)(3 6)(3 7)(4 0)(4 1)(4 2)(4 3)(4 4)(4 5)(4 6)(4 7)(5 0)(5 1)(5 2)(5 3)(5 4)(5 5)(5 6)(5 7)熄灯问题q 根据熄灯规则，如果矩阵根据熄灯规则，如果矩阵 press 是寻找的答案，那么按照是寻找的答案，那么按照 press 的第一的第一行对矩阵中的按钮操作之后，此时在矩阵的第一行上：行对矩阵中的按钮操作之后，此时在矩阵的第一行上：q 如果位置如果位置(1, j)上的灯是点亮

30、的，则要按下位置上的灯是点亮的，则要按下位置(2, j)上按钮，即上按钮，即press2j一定取一定取1；q 如果位置如果位置(1, j)上的灯是熄灭的，则不能按位置上的灯是熄灭的，则不能按位置(2, j)上按钮，即上按钮，即press2j一定取一定取0。(0 0)(0 1)(0 2)(0 3)(0 4)(0 5)(0 6)(0 7)(1 0)(1 1)(1 2)(1 3)(1 4)(1 5)(1 6)(1 7)(2 0)(2 1)(2 2)(2 3)(2 4)(2 5)(2 6)(2 7)(3 0)(3 1)(3 2)(3 3)(3 4)(3 5)(3 6)(3 7)(4 0)(4 1)(4

31、 2)(4 3)(4 4)(4 5)(4 6)(4 7)(5 0)(5 1)(5 2)(5 3)(5 4)(5 5)(5 6)(5 7)熄灯问题q 这样依据这样依据press 的第一、二行操作矩阵中的按钮，才能保证第一行的灯的第一、二行操作矩阵中的按钮，才能保证第一行的灯全部熄灭。而对矩阵中第三、四、五行的按钮无论进行什么样的操作全部熄灭。而对矩阵中第三、四、五行的按钮无论进行什么样的操作，都不影响第一行各灯的状态。，都不影响第一行各灯的状态。q 依此类推，可以确定依此类推，可以确定press 第三、四、五行的值。第三、四、五行的值。q 因此，一旦确定了因此，一旦确定了press 第一行的值之

32、后，为熄灭矩阵中第一至四行的第一行的值之后，为熄灭矩阵中第一至四行的灯，其他行的值也就随之确定了。灯，其他行的值也就随之确定了。(0 0)(0 1)(0 2)(0 3)(0 4)(0 5)(0 6)(0 7)(1 0)(1 1)(1 2)(1 3)(1 4)(1 5)(1 6)(1 7)(2 0)(2 1)(2 2)(2 3)(2 4)(2 5)(2 6)(2 7)(3 0)(3 1)(3 2)(3 3)(3 4)(3 5)(3 6)(3 7)(4 0)(4 1)(4 2)(4 3)(4 4)(4 5)(4 6)(4 7)(5 0)(5 1)(5 2)(5 3)(5 4)(5 5)(5 6)(

33、5 7)熄灯问题q press 的第一行共有的第一行共有26 种取值，分别对应唯一的一种种取值，分别对应唯一的一种press 取值，使得取值，使得矩阵中前四行的灯都能熄灭。矩阵中前四行的灯都能熄灭。q 只要对这只要对这26 种情况进行判断就可以了：如果按照其中的某个种情况进行判断就可以了：如果按照其中的某个press对矩对矩阵中的按钮进行操作后，第五行的所有灯也恰好熄灭，则找到了答案阵中的按钮进行操作后，第五行的所有灯也恰好熄灭，则找到了答案。(0 0)(0 1)(0 2)(0 3)(0 4)(0 5)(0 6)(0 7)(1 0)(1 1)(1 2)(1 3)(1 4)(1 5)(1 6)(

34、1 7)(2 0)(2 1)(2 2)(2 3)(2 4)(2 5)(2 6)(2 7)(3 0)(3 1)(3 2)(3 3)(3 4)(3 5)(3 6)(3 7)(4 0)(4 1)(4 2)(4 3)(4 4)(4 5)(4 6)(4 7)(5 0)(5 1)(5 2)(5 3)(5 4)(5 5)(5 6)(5 7)bool guess() int c, r; for ( r = 1; r 5; r+ ) for ( c = 1; c 7; c+ ) pressr+1c = (puzzlerc + pressrc + pressr-1c + pressrc-1 + pressrc+1

35、) % 2; for(c=1; c7; c+) if ( (press5c-1 + press5c + press5c+1 + press4c) % 2 != puzzle5c ) return(false); return( true );熄灯问题熄灯问题void enumate( ) int c; bool success; for ( c = 1; c 1 ) press1c = 0; c+; press1c+; 熄灯问题main()int cases, i, r, c;scanf(%d, &cases);for ( r = 0; r 6; r+ ) pressr0 = pres

36、sr7 = 0;for ( c = 1; r 7; r+ ) press0c = 0;for ( i = 0; i cases; i+ ) for ( r = 1; r 6; r+ ) for ( c = 1; c 7; c+ ) scanf(%d, &puzzlerc); enumate(); printf(PUZZLE #%dn, i+1); for ( r = 1; r 6; r+ ) for ( c = 1; c 3)，如果，如果 (Xi, Yi) 位于稻田之内，则位于稻田之内，则(Xi, Yi)上的水稻必被青蛙踩踏。上的水稻必被青蛙踩踏。讨厌的青蛙q struct PLANT

37、 /描述一棵被踩踏的水稻描述一棵被踩踏的水稻int x; /水稻的行号水稻的行号int y; /水稻的列号水稻的列号q 从被踩踏的水稻中选择两棵从被踩踏的水稻中选择两棵(X1, Y1)、(X2, Y2)。判断它们是否能够作为。判断它们是否能够作为一条青蛙路径上最先被踩踏的两颗水稻。一条青蛙路径上最先被踩踏的两颗水稻。q (X1, Y1)、(X2, Y2)唯一确定了蛙跳的方向和步长，从唯一确定了蛙跳的方向和步长，从(X2, Y2)开始，沿着开始，沿着这个方向和步长在稻田内走。这个方向和步长在稻田内走。q 每走一步，判断所到达位置上每走一步，判断所到达位置上(X, Y)的水稻是否被踩踏，直到走出稻

38、田的水稻是否被踩踏，直到走出稻田为止。为止。q 如果在某一步上，如果在某一步上，(X, Y) 没有被踩踏，则表明没有被踩踏，则表明(X1,Y1)、(X2, Y2)是一条青是一条青蛙路径上最先被踩踏的两颗水稻的假设不成立。蛙路径上最先被踩踏的两颗水稻的假设不成立。q 这个判断的算法在问题求解过程中要反复使用，它的效率成为决定整个这个判断的算法在问题求解过程中要反复使用，它的效率成为决定整个计算效率的关键。计算效率的关键。(用二分法查找用二分法查找)讨厌的青蛙int r, c, n;struct PLANT int x, y;PLANT plants5001;PLANT plant;int myC

39、ompare( const void *ele1, const void *ele2 );int searchPath(PLANT secPlant, int dX, int dY);讨厌的青蛙main()int main( )int i, j, dX, dY, pX, pY, steps, max = 2; scanf(%d%d, &r, &c); scanf(%d, &n); for ( i = 0; i n; i+ ) scanf(%d %d, &plantsi.x, &plantsi.y); qsort(plants, n, sizeof(PLA

40、NT), myCompare);/找最长路径，见下页找最长路径，见下页if ( max = 2 ) max = 0; printf(%dn, max); return 0;讨厌的青蛙main()for ( i = 0; i n - 2; i+ )for ( j = i + 1; j n - 1; j+ ) dX = plantsj.x - plantsi.x; dY = plantsj.y - plantsi.y; pX = plantsi.x - dX; pY = plantsi.y - dY; if ( pX = 1 & pY = 1 ) continue; if ( plants

41、i.x + max * dX r ) break; pY = plantsi.y + max * dY; if ( pY c | pY max ) max = steps;讨厌的青蛙int myCompare( const void *ele1, const void *ele2 ) PLANT *p1, *p2; p1 = (PLANT*) ele1; p2 = (PLANT*) ele2; if ( p1-x = p2-x )return( p1-y - p2-y );return ( p1-x - p2-x );讨厌的青蛙int searchPath( PLANT secPlant, i

42、nt dX, int dY ) PLANT plant; int steps; plant.x = secPlant.x + dX; plant.y = secPlant.y + dY; steps = 2; while ( plant.x = 1 & plant.y = 1 ) if ( !bsearch(&plant, plants, n, sizeof(PLANT), myCompare) ) steps = 0; break; plant.x += dX; plant.y += dY; steps+; return( steps );奥数问题q 问题描述问题描述ABBD

43、E_ABCCC = BDBDE 在这个式子中，每个字母可以用一个数字在这个式子中，每个字母可以用一个数字（0-9）替换，相同字母只能用同一个数字替换，不同字母用不同数字）替换，相同字母只能用同一个数字替换，不同字母用不同数字替换。可以用替换。可以用“+”、“-”、“*”或者或者 “”，填补中间的空白。，填补中间的空白。问有多少种方案，使得等式成立。字母只有问有多少种方案，使得等式成立。字母只有“A”，“B”，“C”，“D”，“E”五种，式子中的三个数，每个都不超过五种，式子中的三个数，每个都不超过8位。位。输入样例输入样例 输出样例输出样例 2A A ABCD BCD B572奥数问题q 除数

44、为除数为 0 的情况要避免。的情况要避免。q 题目要求等式里出现的数不能有前导题目要求等式里出现的数不能有前导 0。q 这里的除法，结果不应该将小数点后面的部分去掉。这里的除法，结果不应该将小数点后面的部分去掉。q 某个字母可能在式子里并不出现。比如式子可能是某个字母可能在式子里并不出现。比如式子可能是A_A=A，那么应该，那么应该有有 5 种解法，如果枚举的时候简单地应用五重循环枚举，没有考虑枚种解法，如果枚举的时候简单地应用五重循环枚举，没有考虑枚举的某个字母根本没有上，那么算出来的结果多于正确答案。举的某个字母根本没有上，那么算出来的结果多于正确答案。奥数问题#define MAXN 1

45、00char xMAXN, yMAXN, zMAXN;/ 在选中字符替换方案后，求字母在选中字符替换方案后，求字母 p 所代表的数值所代表的数值int num(char p, int a, int b, int c, int d, int e) if(p=A) return a; else if(p=B) return b; else if(p=C) return c; else if(p=D) return d; else return e; 奥数问题/ 检查式子中的三个数是否都是没有前导检查式子中的三个数是否都是没有前导 0 的数的数int check(int a, int b, int

46、c, int d, int e) if(strlen(x)1 & num(x0, a, b, c, d, e)=0) return 0; if(strlen(y)1 & num(y0, a, b, c, d, e)=0) return 0; if(strlen(z)1 & num(z0, a, b, c, d, e)=0) return 0; return 1; 奥数问题/ 求字符串求字符串 x 所代表的数值所代表的数值int get(char *x, int a, int b, int c, int d, int e) int i , s = 0; int l = s

47、trlen(x); for(i = 0; i l; +i) s = s*10 + num(xi, a, b, c, d, e); return s; 奥数问题/ 检查字母检查字母 cc 在式子里是否出现在式子里是否出现int app(char cc) int i; for(i = 0; xi; +i) if (cc=xi) return 1; for(i = 0; yi; +i) if (cc=yi) return 1; for(i = 0; zi; +i) if (cc=zi) return 1; return 0; int a, b, c, d, e, p, q, r, i;int ans

48、, t;scanf(%d, &t);while(t-) scanf(%s, x);scanf(%s, y);scanf(%s, z);/下一行计算几个字母在式子里没有出现过下一行计算几个字母在式子里没有出现过int noapp = 5 - (app(A) + app(B) + app(C) + app(D) + app(E);/ 进行计算，见下页进行计算，见下页for(i = 1; i = noapp; +i)/考虑有的字母没有用到的情况考虑有的字母没有用到的情况ans /= (i+5);printf(%dn, ans); 奥数问题main()奥数问题main()ans = 0;for

49、(a = 0; a 10; +a) /用五重循环枚举所有字母替换方案用五重循环枚举所有字母替换方案 for(b = 0; b 10; +b) if(a!=b) for(c = 0; c 10; +c) if(a!=c & b!=c) for(d = 0; d 10; +d) if(a!=d & b!=d & c!=d)for(e = 0; e 10; +e) if(a!=e & b!=e & c!=e & d!=e) if(check(a, b, c, d, e) p = get(x, a, b, c, d, e); q = get(y, a,

50、b, c, d, e); r = get(z, a, b, c, d, e); if(p+q=r) +ans; if(p-q=r) +ans; if(p*q=r) +ans; if(q!=0 & p%q=0 & p/q=r) +ans; 3x+1q 从任意一个正整数开始，重复对其进行下面的操作：如果这个数是偶从任意一个正整数开始，重复对其进行下面的操作：如果这个数是偶数，把它除以数，把它除以 2 ；如果这个数是奇数，则把它扩大到原来的；如果这个数是奇数，则把它扩大到原来的 3 倍后再倍后再加加 1 。序列是否最终总会变成。序列是否最终总会变成 4, 2, 1, 4, 2, 1,

51、 的循环？的循环？q 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, q 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377,

52、1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5,

53、 16, 8, 4, 2, 1, 4, 2, 1, q 编程验证。编程验证。黑洞q 茫茫茫茫宇宙宇宙之中，存在着这样一种极其神秘的之中，存在着这样一种极其神秘的天天体体叫叫“黑洞黑洞”（black hole）q 黑洞的物质密度极大，黑洞的物质密度极大，引力引力极强，任何物质经极强，任何物质经过它的附近，都要被它吸引进去，再也不能出过它的附近，都要被它吸引进去，再也不能出来，包括来，包括光线光线也是这样，因此是一个不发光的也是这样，因此是一个不发光的天体黑洞的名称由此而来。天体黑洞的名称由此而来。q 由于不发光，人们无法通过肉眼或观测仪器发由于不发光，人们无法通过肉眼或观测仪器发觉它的存在，而只

54、能理论计算或根据觉它的存在，而只能理论计算或根据光线光线经过经过其附近时产生的弯曲现象而判断其存在。其附近时产生的弯曲现象而判断其存在。q 虽然理论上说，虽然理论上说，银河系银河系中作为中作为恒星恒星演化终局的演化终局的黑洞总数估计在几百万到几亿个之间，但至今黑洞总数估计在几百万到几亿个之间，但至今被科学家确认了的黑洞只有被科学家确认了的黑洞只有天鹅座天鹅座 X-1、大麦、大麦哲伦云哲伦云 X-3、AO602-00 等极有限的几个。等极有限的几个。证证认认黑洞成为黑洞成为 21 世纪的科学难题之一。世纪的科学难题之一。西西弗斯串西西弗斯串q 设定一个任意数字串，数出这个数中的偶设定一个任意数字串，数出这个数中的偶数个数数个数、奇数个数，及这个数中所包含的奇数个数，及这个数中所包含的所