算法与程序实践习题解答7(枚举)
《算法与程序实践》习题解答7——枚举
枚举是基于已有的知识进行答案猜测的一种问题求解策略。在求解一个问题时，通常先建立一个数学模型，包括一组变量，以及这些变量需要满足的条件。问题求解的目标就是确定这些变量的值。根据问题的描述和相关的知识，能为这些变量分别确定一个大概的取值范围。在这个范围内对变量依次取值，判断所取的值是否满足数学模型中的条件，直到找到（全部）符合条件的值为止。这种解决问题的方法称作“枚举”。
例如“求小于N的最大素数”。其数学模型是：一个整型变量n，满足：
（1）n不能够被[2，n）中的任意一个素数整除；
（2）n与N之间没有素数。
利用已有的知识，能确定n 的大概取值范围{2} {2*i+1|1<=i,2*i+1 枚举是用计算机求解问题最常用的方法之一，常用来解决那些通过公式推导、规则演绎的方法不能解决的问题。而且，枚举也是现代科学研究和工程计算的重要手段，因为科学研究是在发现问题的规律之前解决问题，然后再寻找不同问题之间的共同规律。在采用枚举的方法进行问题求解时，要注意3个方面的问题。 ●建立简洁的数学模型。数学模型中变量的数量要尽量少，它们之间相互独立。这样问题 解的搜索空间的维度就小。反应到程序代码中，循环嵌套的层次少。模型中的每个条件要反应问题的本质特征。“求小于N 的最大素数”中的条件（1）是“n不能够被[2，n）中的任意一个素数整除”，而不是“n不能够被[2，n）中的任意一个整数整除”。这个条件极大的降低了判断n是否是素数的计算开销。 ●减小搜索的空间。利用已有的知识缩小数学模型中各个变量的取值范围，避免不必要的 计算。反应到程序代码中，循环体被执行的次数就少。除2 之外的其它素数都是奇数，因此“小于N 的最大素数”一定在集合{2，2*i+1|1<=i，2*i+1 ●采用合适的搜索顺序。对搜索空间的遍历顺序要与数学模型中的条件表达式一致。例如 在“求小于N 的最大素数”中，在判断n是否是素数时，需要用到比n小的全部素数。 因此，在程序代码中，应该对搜索空间{2，2*i+1|1<=i，2*i+1 CS71：生理周期（简单枚举） （来源：https://www.wendangku.net/doc/2115007568.html, 2977，程序设计导引及在线实践（李文新）例8.2 P176） 问题描述： 人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。 输入： 输入四个整数：p, e, i和d。p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或i。所有给定时间是非负的并且小于365, 所求的时间小于21252。 输出： 从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。 样例输入： 0 0 0 0 0 0 0 100 5 20 34 325 4 5 6 7 283 102 23 320 203 301 203 40 -1 -1 -1 -1 样例输出： Case 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 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. 解题思路： 假设从当年的第一天开始数，第x天时三个高峰同时出现。符合问题要求的x必须大于 d、小于等于21252，并满足下列三个条件： 1) (x-p) % 23 = 0 2) (x-e) % 28 = 0 3) (x-i) % 33 = 0 在搜索空间[d+1，21252]中，对每个猜测的答案都进行三个条件的判断，开销很大，也没有必要。首先从搜索空间[d+1，21252]中找到符合条件1)的全部时间，然后从这些时间中寻找符合条件2)、3)的时间，可以将对条件2)、3)的判定次数减少为原来的1/23。用同样的办法，可以继续减少对条件3)的判定次数。 对每一组数据，分别执行下列算法： 1)读入p, e, i, d 2)从d+1循环到21252，找到第一个满足条件1)的时间a、并跳出循环 3)从a循环到21252，找到第一个满足条件2)的时间b、并跳出循环 4)从b循环到21252，找到第一个满足条件3)的时间x、并跳出循环 5)输出x-d 参考程序： #include int main() { int p,e,i,d,j,no=1; scanf("%d%d%d%d",&p,&e,&i,&d); while(p != -1 && e != -1 && i != -1 && d != -1) { for(j=d+1;j<21252;j++) { if((j-p) % 23 == 0) break; } for(;j<21252;j=j+23) if((j-e)%28 == 0) break; for(;j<21252;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,&d); no++; } return 0; } 实现技巧： 在问题的数学模型中，有多个条件需要满足时，可以采用逐步减小搜索空间的方法提高计算的效率。依次按照条件一、条件二、……、进行搜索。在最初的搜索空间上，按条件一进行判定。除最后一次外，每次搜索都找到符合当前条件的全部答案，将它们作为下一个条件判定的搜索空间。 CS72：完美立方（搜索解空间中解不唯一） （来源：https://www.wendangku.net/doc/2115007568.html, 2810，程序设计导引及在线实践（李文新）例8.4 P181） 问题描述： a 3 = b 3 + c 3 + d 3 为完美立方等式。例如12 3 = 6 3 + 8 3 + 10 3 。编写一个程序，对任给 的正整数N (N≤100)，寻找所有的四元组(a, b, c, d)，使得a 3 = b 3 + c 3 + d 3 ，其中1 c, d ≤N。 输入： 正整数N(N≤100)。 输出： 每行输出一个完美立方，按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则依次按照b、c、d进行非降升序排列输出，即b值小的先输出、然后c值小的先输出、然后d值小的先输出。 样例输入： 24 样例输出： Cube = 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) 解题思路： 此题的思路非常简单：给定4个整数的四元组(a 、b 、c 、d)，判断它们是否满足完美立方等式a 3 = b 3 + c 3 + d 3 。对全部的四元组进行排序，依次进行判断。如果一个四元组满足完美立方等式，则按照要求输出。先判断a 值小的四元组；两个四元组的a 值相同，则先判断b 值小的；两个四元组的a 值和b 值分别相同，则先判断c 值小的。关键是解决两个方面的问题： 1.确定全部需要判断的四元组，并对它们进行排序。稍作分析不难发现，在这个序列中，任意一个四元组(a 、b 、c 、d)：(1) a ≥6，因为a 最小必须是5，才能使得b 、c 、d 分别是3个大于1的不同整数，但(5、2、3、4)不满足完美立方等式的要求；(2) 1< b < c < d ，否则该四元组在序列中的位置就要向前移；(3) 如果(a 、b 、c 、d)满足完美立方等式，则b 、c 、d 都要比a 小。 2.避免对一个整数的立方的重复计算。[2，N]中的每个整数i ，在整个需要判断的四元组序列中都反复出现。每出现一次，就要计算一次它的立方。在开始完美立方等式的判断之前，先用一个数组保存[2，N]中的每个整数的立方值。在判断四元组(a 、b 、c 、d)是否满足完美立方等式的要求时，直接使用存储在数组中的立方值。 参考程序： #include #include int main() { int n,a,b,c,d; long int cube[101]; int i; scanf("%d",&n); for(i=1;i<=n;i++) { cube[i]=i*i*i; } for(a=6;a<=n;a++) for(b=2;b { if(cube[a] for(c=b+1;c { if(cube[a] for(d=c+1;d if(cube[a]==cube[b]+cube[c]+cube[d]) printf("Cube = %d, Triple = (%d,%d,%d)\n",a,b,c,d); } } return 0; } 实现技巧： ●用一个数组来保存1~N的立方，这样在判断四元组(a, b, c, d)是否是完美立方时，不 需要重复计算a 3 、b 3 、c 3 、d 3 。 ●在对b循环时，如果a3 ●在对c循环时，如果a3 请思考：在最内层循环中，使用条件a 3 3 + c 3 + d 3 判断是否要终止循环，能否带来性能上 的提高？ CS73：数字方格 （来源：https://www.wendangku.net/doc/2115007568.html, 2747，程序设计导引及在线实践（李文新）练习2 P195） 问题描述： 如上图，有3个方格，每个方格里面都有一个整数a1，a2，a3。已知0 <= a1, a2, a3 <= n，而且a1 + a2是2的倍数，a2 + a3是3的倍数， a1 + a2 + a3是5的倍数。你的任务是找到一组a1，a2，a3，使得a1 + a2 + a3最大。 输入： 输入的第一行是一个数t，表示测试数据的数目。接下来的t行，每行给出一个n (0 <= n <= 100)的值。 输出： 对于每一个n的值，输出a1 + a2 + a3的最大值。 样例输入： 2 3 样例输出： 5 参考程序： #include int main() { int t,n; int a,b,c,max; scanf("%d",&t); while(t--) { scanf("%d",&n); max=0; for(a=0;a<=n;a++) { for(b=0;b<=n;b++) { if((a+b)%2!=0) continue; for(c=0;c<=n;c++) { if((b+c)%3!=0) continue; if((a+b+c)%5!=0) continue; if(a+b+c>max) max=a+b+c; } } } printf("%d\n",max); } return 0; } CS74：切换状态（Switch） （来源：ZOJ 1622，程序设计方法及在线实践指导（王衍等） P146） 问题描述： 有N盏灯，排成一排。给定每盏灯的初始状态（开或关），你的任务是计算至少要切换多少盏灯的状态（将开着的灯关掉，或将关着的灯开起来），才能使得这N盏灯开和关交替出现。 输入： 输入文件中包含多个测试数据，每个测试数据占一行。首先是一个整数N，1<=N<=10000，然后是N个整数，表示这N盏灯的初始状态，1表示开着，0表示关着。测试数据一直到文 件尾。 输出： 对每个测试数据，输出占一行，表示至少需要切换状态的灯的数目。 样例输入： 9 1 0 0 1 1 1 0 1 0 3 1 0 1 样例输出： 3 解题分析： 本题可以采取不同的枚举思路求解。 （1）N盏灯，每盏灯都有两种状态：1和0，则N盏灯共有2N种状态，从0 0 … 0到1 1 … 1，可以枚举这2N种状态，每种状态都判断一下是否是开和关交替出现，如果是，则还要统计从初始状态转换到该状态需要切换的灯的数目。但这种枚举策略势必要花费很多时间，因为N最大可以取到10000，而210000的数量级是103010。 （2）要使得N盏灯开和关交替出现，实际上只有两种可能：奇数位置上的灯是开着的，或者偶数位置上的灯是开着的。只要分别计算从N盏灯的初始状态出发，切换到这两种状态所需要切换灯的数目，取较小者即可。例如，样例输入中的第1个测试数据对应的初始状态为：1 0 0 1 1 1 0 1 0，奇数位置上的灯开着：1 0 1 0 1 0 1 0 1，偶数位置上的灯开着：0 1 0 1 0 1 0 1 0。如果将这9盏灯切换到奇数位置上的灯是开着的，需要切换6盏灯；若要切换到偶数位置上的灯是开着的，需要切换3盏灯。因此，至少需要切换3盏灯。 （3）注意到上述分析中3+6=9,9就是灯的数目N。稍加分析就可以得到以下结论：如果将N盏灯调整成奇数位置上的灯是开着的，需要调整灯的数目为numo，则将N盏灯调整为偶数位置上的灯是开着的，需要调整灯的数目nume=N-numo。因此只需要判断numo是否小于N/2，如果是，则取numo；否则取N-numo。这种思路只要枚举一种状态即可。 参考程序： #include int main() { int N,i; int numo; int lights[10001]; while(scanf("%d",&N)!=EOF) { numo=0; for(i=1;i<=N;i++) scanf("%d",&lights[i]); for(i=1;i<=N;i++) { if(i%2==1 && lights[i]==0) numo++; //奇数位置上为0，需要调整 if(i%2==0 && lights[i]==1) numo++; //偶数位置上为1，需要调整} printf("%d\n",numo } return 0; } CS75：几何问题变得简单了 （来源：ZOJ 1241，程序设计方法及在线实践指导（王衍等） P148） 问题描述： 如果你有一台计算机，那么数学问题会变得简单。例如，在直角三角形中，三条边的长 度a、b和c（其中c为斜边，如图所示）满足勾股定理：a*a+b*b=c*c。在本题中，已知两条边的长度，要求第3条边的长度。 输入： 输入文件包含了多个直角三角形的数据。每个三角形的数据占一行，为3个整数a、b 和c，表示三角形3条边的长度。这3个整数中仅有一个整数为-1，代表长度未知的边，而其他两个整数都为正整数。输入文件的最后一行为3个0，表示输入数据结束。 输出： 对输入文件中的每个三角形，首先输出三角形的序号，如样例输出所示。然后，如果这3条边不能构成三角形，输出Impossible，否则输出第3条边的长度，保留小数点后3位有效数字。每个三角形的输出之后有一个空行。 样例输入： 3 4 -1 -1 2 7 5 -1 3 0 0 0 样例输出： Triangle #1 c = 5.000 Triangle #2 a = 6.708 Triangle #3 Impossible. 解题分析： 用a、b和c来读入三条边的长度，依次对a、b和c进行枚举，看哪条边需要求。 谈谈用枚举算法解决问题的编程思路与步骤方法 一．问题 上海市普通高中在信息科技学科中开展《算法与程序设计》教学，教材中有一章名为“算法实例”的内容，其中有一节介绍“枚举算法”。教材中关于枚举算法的描述：有一类问题可以采用一种盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不合要求的，保留那些符合要求的。这种方法叫做枚举算法（enumerative algorithm）。 枚举法就是按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若是，我们采纳这个解，否则抛弃它。在列举的过程中，既不能遗漏也不应重复。 生活和工作中，人们经常会不经意间运用“枚举算法”的基本原理，进行问题的解决。比如，让你用一串钥匙，去开一把锁，但是不知道具体是用哪一把钥匙，你就会一把一把地挨个地逐个尝试，最终打开锁为止。又如，要对1000个零件，进行合格检验，等等。 二．用枚举算法的思想编写程序的思路与步骤 枚举算法，归纳为八个字：一一列举，逐个检验。在实际使用中，一一列举；采用循环来实现，逐个检验：采用选择来实现。 下面，通过一个问题的解决来说明这一类问题的解决过程的方法与步骤； 例1：在1—2013这些自然数中，找出所有是37倍数的自然数。 这个问题就可以采用枚举算法来解决： 1)．一一列举；采用循环来实现； 循环需要确定范围：本循环控制变量假设用i，起始值是1，终止值是2013。 2)．逐个检验：采用选择来实现； 选择需要列出判断的关系表达式：i Mod 37 = 0 这样，就可以写出整个求解的VB代码： Dim i As Integer For i = 1 To 2013 If i Mod 37 = 0 Then Print i End If Next i 说白了，用枚举算法解决问题，其实是利用计算机的高速度这一个优势，就好比上题完全可以使用一张纸和一支笔，采用人工的方法完成问题的解，从1开始，一一试除以37，这样计算2013次，也可以找到问题的答案。 在教学中，问题的求解往往是针对数学上的问题，下面举一些相关的例子，来巩固与提高采用枚举算法进行程序设计的技能。 三．枚举算法举例： 1：一张单据上有一个5位数的编号，万位数是1，千位数是4，百位数是7，个位数、十位数已经模糊不清。该5位数是57或67的倍数，输出所有满足这些条件的5位数的个数。（147□□） 1)．一一列举；采用循环来实现； 实验五常用算法：枚举法递推法迭代法 一、实验目的 掌握枚举法，递推法、迭代法这3种常用算法。 二、实验内容 1.编程求和： [提示] 令各项为b0,b1,b2,…bn 则b0 = a b1 = b0×10+a b2 = b1×10+a… 即每一项由前一项乘以10加a递推得到，然后求和。 2.编程求出所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其 各位数字的立方和等于该数本身，例如153是一个“水仙花数”，因为153＝ 13+53+33。要求采用枚举法。 3. 范例：设函数f(x)定义在区间[a,b]上，f(x)连续且满足f(a) ×f(b)<0,求f(x)在[a,b]上的根。采用割线法，迭代公式为： x i+1= x i+( x i-1- x i)/(f(x i)-f(x i-1))*f(x i) 其代换规律为：首先用两端点函数值的绝对值较大者的对应点作为x i-1，较小者 作为x i，即如果|f(a)|<|f(b)|，则将a赋给x i-1，将b赋给x i。用迭代公式得出x i+1， f(x i+1)。 误差定义为： ⊿x =( x i-1- x i)/(f(x i)-f(x i-1))*f(x i) 当⊿x<ε或f(x i+1)==0则结束运算。否则用(x i,f(x i))代替(x i-1,f(x i-1))，(x i+1,f(x i+1))代替(x i,f(x i))，继续迭代。 求解方程：x*lg(x)=1的实根的近似值，误差不超过0.001。 [提示]令 f(x)=xlgx-1,则f(2)≈-0.398<0,而f(3)≈0.431>0，由此可知根 在2与3之间。 #include 枚举算法（2课时） 一、教学目标 1．知识目标：（1）通过具体实例的求解，让学生了解什么是枚举算法； （2）让学生亲身体验并理解枚举算法解决问题的基本思想； （3）用流程图形式来表示枚举算法解决问题的思路； （4）拓展：通过学习，解决日常实际问题； 2．能力目标：（1）“摆事实，讲道理”，通过具体例子分析，让学生理解如何用3步法来解决实际问题（提出问题——分析问题——解决问题）； （2）通过自主学习过程体验，合作探究画流程图的学习方式，提高学生的信息素养。 3．情感目标：（1）通过情景创设，激发学生学习兴趣； （2）通过3步法，让学生更能结合其他学科的学习方法，激发学生善 于思考问题，解决问题的能力； （3）通过小组合作，增进学生间的学习交流，培养合作能力，激发学生学习能动性； 二、重点与难点 1．重点：通过对涂抹数据的猜想，让学生理解枚举算法的思想，初步培养学生解决实际问题的能力； 2．难点：理解多种控制结构的嵌套； 枚举算法思想的理解与实现（流程图转化为代码并上机实践） 三、教学模式 1．教师教法：情景创设法、演示法、讨论法 2．学生学法：自主学习、合作探究学习 四、课前准备 1．上课环境：多媒体电脑房； 2．上课工具：幻灯片（枚举算法.ppt课件）；辅助教学软件（flash动画，过程体验）； 一件校服 五、教学过程 （一）、创设情景，引入问题（引导学生概括枚举算法的概念）（引入主题） 幻灯片展示：这是我的校服吗？ 教师：各位同学，在我们上课之前，先请7位同学表演一段试衣情景！（要求：某一列的学生起立，由第1位同学开始试穿上衣，然后脱掉后传给第2位， 第2位试穿后传给第3位，依次……） 试衣结束后教师提出问题：同学们，请问，看了此情景后，你们觉得这件校服是谁的呢？ 学生一答：是甲的，也可能是乙的。 学生二答：谁也不是，我觉得。 教师问：那么依照学生二回答，难道就找不到这件校服的主人了吗？ 学生二补充：老师，你可以给其他同学再试试啊，也许有适合的哦。 学生们：对对对…… 教师小结：很好，那么我们从刚才的小情景中可以看出，如果要找到一个问题的真正解，必须要把所有可能的解都先列出来，然后再一一进行检验， 看看是否有符合条件的。那么我们把这样的一种算法称为“枚举算法”（二）、学习新课（认知主题） 幻灯片展示：枚举算法：按问题本题的性质，一一列举出该问题所有可能的解， 并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若 是，就采纳这个解，否则就抛弃它。 教师问：请问各位同学，在看了枚举算法这个概念后，你们觉得这个算法的最关键的要求是什么？ 学生三答：一一列举，检验 教师问：那么在列举过程中，我在刚才范了一个怎么样的错误呢？ 学生们：你没列举出所有的解，只试了一部分同学啊…… 三年级枚举法练习题题库 （思维突破）姓名： 例1、一个三位数，每一位上的数字都是0、1、2中的一个，且数字不重复，请问：一共有多少个满足条件的三位数？ 练1、一个三位数，每一位上的数字都是1、2、4中的一个，且数字不重复，请问：一共有多少个满足条件的三位数？ 例2、一个四位数，每一位上的数字都是0、1、2中的一个，并且相邻的两个数字不同，请问：一共有多少个满足条件的四位数？ 练2、一个三位数，每一位上的数字都是5、6、7中的某一个，并且相邻的两个数字不同，请问：一共有多少个满足条件的三位数？ 例3、小高、墨莫和萱萱玩传球游戏，每次持球人都可以把球传给另外两人中的任何一人。先由小高拿球，经过4次传球之后，球又回到了小高手里。请问：一共有多少种不同的传球过程? 练3、有A、B、C三片荷叶，青蛙“呱呱”在荷叶A上，每次它都会从一片荷叶跳到另一片荷叶上，结果它跳了3次之后，不在荷叶A上。请问：它一共有多少种不同的跳法？ 例4、一个两位数，十位比个位大，个位不小于5且不大于7，请问：这样的两位数一共有多少个？ 练4、王老师有一个带密码锁的公文包，但是他忘记了密码，只记得密码是一个两位数。这个两位数的个位数字比十位数字大，并且没有比4大的数字，试问：王老师最多需要试多少次就肯定能打开这个公文包？ 课后作业： 1、一个两位数，每一位上的数字都是1、 2、3中的一个，且数字不重复，请问：一共 有多少个满足条件的两位数？ 2、一个三位数，每一位上的数字都是6、7、8中的一个，且数字不重复，请问：一共有多少个满足条件的三位数？ 3、粗心的卡莉娅忘记了日记本的三位密码，只记得密码是由1、2、7三个数字中的某些数字构成的，且相邻的两个数字不一样。那么卡莉娅最多试几次就一定能打开日记本？ 4、由1、2、7能组成多少个各位数字不重复的三位数？ 5、由1、2能组成多少个三位数？（数字不必都用上） 6、由2、3、4各一个组成三位数。要求：百位不是2，十位不是3，个位不是4，则符合三位数有多少个？ 7、一个三位数，百位比十位小，十位比个位小，百位不小于6.那么这样的三位数一共有多少个？ 8、松鼠宝宝出去摘松果，每次出去都会摘回来1个松果或2个松果。那么松鼠宝宝恰好采4个松果有多少种不同的过程？ 9、甲、乙、丙三个人传球，从甲开始传球，每次拿球的人都把球传给剩下两个人中的一人，传了3次后球在丙的手上，那么一共有多少种可能的传球过程？ 10、甲、乙、丙三个人传球，从甲开始传球，每次拿球的人都把球传给剩下两个人中的一人，传了3次后球不在丙的手上，那么一共有多少种可能的传球过程？ 1.用50元钱兑换面值为1元、2元、5元的纸币共25张。每种纸币不少于1张，求出有多少种兑换方案？每种兑换方案中1元、2元、5元的纸币各有多少张？ 假设面值为1元、2元、5元的纸币分别是x、y、z张，兑换方案有k种，从题意可得出x、y、z满足的表达式为 x+y+z=25 x+2y+5z=50 解决此问题的Visual Basic程序如下，在(1)和(2)划线处，填入合适的语句或表达式，把程序补充完整。 Private Sub Command1_Click() Dim k As Integer Dim x As Integer, y As Integer, z As Integer k = 0 List1.Clear For y = 1 To 23 For z = 1 To 9 x = 25 - y - z If (1) Then List1.AddItem "1元" + Str(x) + "张 2元" + Str(y) + "张 5元" + Str(z) + "张" ____(2)___________ End If Next z Next y Label1.Caption = "共有" + Str(k) + "种兑换方案" End Sub 程序中划线处(1)应填入_____________ 程序中划线处(2)应填入_____________ 2.以下Visual Basic程序的功能是：计算表达式1+2+22+23+24+25+26+27+28+29+210的值，并在文本框Text1中输出结果。为了实现这一功能，程序中划线处的语句应更正为_____________。 Private Sub Command1_Click() Dim i As Integer,s As Long s = 0 k = 2 For i= 1 To 10 s = s + k k = k * 2 Next i Text1.Text=Str(s) End Sub 枚举算法教学设计教案《枚举法》 教学目标： 1、知识和技能----理解枚举法的概念和注意点，能用枚举法来解决实际问题。 2、方法和过程----通过对知识的探究和实际问题的解决，自学探究能力、解决问题能力和归纳概括能力得以提高。 3、情感态度和价值观----创设情境，激发学生兴趣，培养学生学习的主动性和积极性；构建研究的环境，培养学生良好的学习习惯和探索研究的科学态度。 知识点：计数器的概念、伪代码、多重For循环、List1box控件的使用、枚举算法 教学重点：用枚举法解决问题、培养学生自主学习探索知识的能力 教学难点：多重For循环的理解、培养学生自主学习、探索获取知识的学习方法 教学方法：启发式 教学过程： 一、理解枚举概念 A．将一箱苹果中烂的苹果挑出来。 B．工厂检验每件产品质量 枚举算法的基本思想：把问题所有的可能解，逐一罗列出来并加以验证，若是问题的真正解，就予以采纳，否则就抛弃它。 关键点：列举、检验 难点：多重For 循环的理解 （1）从最内层开始运行， （2）从循环次数角度理解 注意点：不遗漏、不重复 二、案例讨论(进一步理解枚举的概念) 在前1000个奇自然数中，计算恰好有三位为1的二进制数的个数（例如，19对应的二进制数10011，是一个符合题目要求的数字，而23对应的二进制数10111，则不符合本题目要求）代码：(穿插伪代码、计数器的概念) Private Sub Form_Load() Dim K(1 To 11) As Integer '定义数组下标最大为11, 2^11=2048>1999 Dim a, b, c As Integer Dim i, j, w As Integer Form1.Show c = 0 For i = 1 To 1000 a = 0 '采用除2取余法将十进制数化二进制数，结果存放在数组K中 j = i * 2 - 1 Do While j > 0 a = a + 1 K(a) = j Mod 2 j = j \ 2 Loop w = 0 '统计数组K中1的个数,结果存放在变量w中 For b = a To 1 Step -1 If K(b) = 1 Then w = w + 1 Next b If w = 3 Then c = c + 1 ‘统计二进制数中恰好有三位1的个数 Next i Print "在前1000个奇自然数中,恰好有三位为1的二进制数的个数有"; c; "个。" End Sub 小学奥数枚举法题及答案【三篇】 导读：本文小学奥数枚举法题及答案【三篇】，仅供参考，如果觉得很不错，欢迎点评和分享。 【篇一】枚举法问题 在一个圆周上放了1个红球和1994个黄球。一个同学从红球开始，按顺时针方向，每隔一个球，取走一个球；每隔一个球，取走一个球；……他一直这样操作下去，当他取到红球时就停止。你知道这时圆周上还剩下多少个黄球吗？ 答案与解析： 根据题中所说的操作方法，他在第一圈的操作中，取走的是排在黄球中第2、4、6、……1994位置上的黄球，这时圆周上除了一个红球外，还剩下1994÷2=997个黄球。 在第二圈操作时，他取走了这997个黄球中，排在第1、3、5、7、……995、997位置上的黄球，这时圆周上除了一个红球外，还剩下997—(997+1)÷2=498个黄球。 他又要继续第三圈操作了，他隔过红球，又取走了这498个黄球中，排在第1、3、5、……495、497的位置上的黄球，这时圆周上除了一个红球外，还剩下498÷2=249个黄球。 因为在上一圈操作时，排在这498个黄球中最后一个位置上的黄球没有被取走，所以他再进行操作时，第一个被取走的就是那个红球，这时，他的操作停止，圆周上剩下249个黄球。【篇二】 在一个圆周上放了1个红球和1994个黄球。一个同学从红球开始，按顺时针方向，每隔一个球，取走一个球;每隔一个球，取走一个球;……他一直这样操作下去，当他取到红球时就停止。你知道这时圆周上还剩下多少个黄球吗? 答案与解析： 根据题中所说的操作方法，他在第一圈的操作中，取走的是排在黄球中第2、4、6、……1994位置上的黄球，这时圆周上除了一个红球外，还剩下1994÷2=997个黄球。 在第二圈操作时，他取走了这997个黄球中，排在第1、3、5、7、……995、997位置上的黄球，这时圆周上除了一个红球外，还剩下997—(997+1)÷2=498个黄球。 他又要继续第三圈操作了，他隔过红球，又取走了这498个黄球中，排在第1、3、5、……495、497的位置上的黄球，这时圆周上除了一个红球外，还剩下498÷2=249个黄球。 因为在上一圈操作时，排在这498个黄球中最后一个位置上的黄球没有被取走，所以他再进行操作时，第一个被取走的就是那个红球，这时，他的操作停止，圆周上剩下249个黄球。【篇三】 枚举算法题目及其代码 的计数算法及其代码的标题由李利添 1，权重[问题描述] 有1g，2g，3g，5g，10g，XXXX年后，欧拉证明了欧几里得定理的逆命题:每一个偶数完全数都是欧几里得形式例如，6 = 2(2–1)*(2 2–1)，28 = 2(3–1)*(2 3–1) 是一个罕见的完全数。到1975年，只找到了24个满分，前四个是6，28，496，8128对应的p是2，3，5，7， ，给你一些整数p(不一定是质数)请判断2(p-1)*(2p-1)是否是一个完全数最高满分不超过2 33分[输入格式] 输入文件只有一行，即p[输出格式] 输出\或\注意情况)。[输入样本]编号2 [输出样本]编号2 [参考程序] 常量最大值= 131071； var pr:array[1..最大值]的布尔值；p:字节； 程序埃拉托斯；var i，j:word；begin fillchar(pr，sizeof(pr)，true)；公关[1]:=假； 表示i:=2至最大div 2，如果pr[i]则 表示j:=2至最大div i，则pr[I * j]:= false；结束；{埃拉托} begin{main}埃拉托； 赋值(输入，“number . in”)；重置(输入)； 2 赋值(输出，“number . out”)；重写(输出)；read ln(p)； if(pr[p)和(pr[trunc(exp(p*ln(2)))-1])则writeln(“是”)否则writeln(“否”)； 关闭(输入)；关闭(输出)；结束。 3，苹果采摘陶陶[问题描述] 说苹果去年被陶陶采摘后非常生气，他们用最先进的克隆技术克隆了许多陶陶的复制品，然后挂在树上采摘。 的规则是，一个苹果只能摘一个陶陶，而且只有最高的陶陶低于它能摘的高度(即小于关系)，如果它不能摘，它只能沮丧地走开。给出苹果的数量、每个苹果能达到的高度和每个陶陶的高度，并问摘下苹果后还剩多少陶陶。？[输入格式] 的第一行有两个数字:苹果的数量n和陶陶的数量m (n，m0然后开始[最佳]:= false；12月(tot)；结束；结束；结束；{ work } 程序打印；开始 分配(输出，“apple . out”)；重写(输出)；write ln(tot)；关闭(输出)；结束；{打印}开始{主}初始化；工作；打印；结束。 4 4，顶级卡特彼勒编号(编号。[问题描述] 顶猫非常喜欢研究数字，尤其是质数一天，top cat发现有些数字可 二年级奥数题及答案：枚举法 二年级奥数题及答案：枚举法 1.一个长方形的周长是22米，如果它的长和宽都是整米数，问： ①这个长方形的面积有多少可能值? ②面积最大的长方形的长和宽是多少? 2.有四种不同面值的硬币各一枚，它们的形状也不相同，用它们共能组成多少种不同钱数? 3.三个自然数的乘积是24，问由这样的三个数所组成的数组有多少个?如(1，2，12)就是其中的一个，而且要注意数组中数字相同但顺序不同的算作同一数组，如(1，2，12)和(2，12，1)是同一数组. 4.小虎给3个小朋友写信，由于粗心，把信装入信封时都给装错了，结果3个小朋友收到的都不是给自己的信，请问小虎错装的情况共有多少种可能? 5.一个学生假期往A、B、C三个城市游览.他今天在这个城市，明天就到另一个城市.假如他第一天在A市，第五天又回到A市.问他的游览路线共有几种不同的方案? 6.下图中有6个点，9条线段，一只甲虫从A点出发，要沿着某几条线段爬到F点.行进中甲虫只能向右、向下或向右下方运动.问这只甲虫有多少种不同的走法? 7.小明有一套黄色数字卡片、、，有一套蓝色数字卡片、、.一天他偶然用卡片做了下面的游戏：把不同色的卡片交叉配对，一次配成3对，然后把每对卡片上的黄蓝数字相乘之后再相加求和，你知道他共找到了多少种配对相乘求和的方式吗?比如说下面是其中一种： 黄蓝黄蓝黄蓝 8.五个学生友1，友2，友3，友4，友5一同去游玩，他们将各自的书包放在了一处.分手时友1带头开了个玩笑，他把友2小朋友的书包拿走了，后来其他的小朋友也都拿了别人的书包.试问在这次玩笑中故意错拿书包的情形有多少种不同方式? 习题解答 1.解：这个长方形的长和宽之和是22÷2=11(米)，由长方形的面积=长×宽，可知： 由上表可见面积最大的长方形的长是6米、宽是5米，面积是30平方米. 猜想：由本讲的例1和习题1这两题来看，周长一定的所有长方形中，长和宽相等或相近 常用算法——穷举搜索法 二、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。 【问题】将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。 程序引入变量a、b、c、d、e、f，并让它们分别顺序取1至6的证书，在它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。细节见下面的程序。 【程序1】 # include 3.1解析算法及程序实现 1.计算长方体体积的算法描述如下： ①输入长方体的长(z)、宽(w)、高(h) ②计算长方形体积 v = z * w * h ③输出结果 ④结束 上述算法属于（ ） A. 枚举算法 B. 排序算法 C. 解析算法 D. 递归算法 2.下列问题适合用解析算法求解的是（ ） A.将十三张纸牌按从小到大进行排列 B.统计100内偶数的各位数字之和恰好为10的个数 C.计算一辆车行驶100公里的油耗 D.寻找本年级身高最高的同学 3.有如下问题： ①已知圆锥的半径r 和高度h ，使用公式V= 3 1πh r 2求出此圆锥体的体积。 ②已知班级每位同学的其中成绩总分s ，按照s 的值从大到小进行成绩排名。 ③已知圆的周长s ，利用公式r=s/(2*3.14)求出圆的半径。 ④已知“水仙花数”的定义，找出1～10000范围内所有的水仙花数。 用计算机解决上述问题时，适合用解析算法的是（ ） A. ①② B. ①③ C. ③④ D. ②④ 4.出租车计价规则：3公里以内，10元；超出3公里每公里增加2元。假定公里数为x,金额为y.解决此问题的公式和流程图如下图所示： 流程图加框处部分的算法属于：（ ） A.解析算法 B.排序算法 C.枚举算法 D.递归算法 5.现要求编写VB程序实现如下功能：分别 在文本框Text1、Text2、和Text3中输入 三条线段的长度，单击“判断”按钮Command1 后，在标签Label1中显示判断结果。程序 运行界面如图： 按此要求编写的程序如下： Private Sub Command1_Click() Dim a As Single ,b As Single Dim c As Single ,st As String a=Val(Text1.Text) b=Val(Text2.Text) c=Val(Text3.Text) If Not (a + b > c And b + c > a And c + a > b) Then st = “这三条线不能构成一个三角形” ElseIf a * a + b * b = c * c Or a * a + c * c = b * b Or b * b + c * c = a * a Then st = “可以构成一个直角三角形” ElseIf ① Then st = “可以构成一个等边三角形” Else st = “可以构成一个不等边的斜三角形” End If Label1.Caption = ② End Sub 划线处应填写正确的语句是： （1）划线处① （2）划线处② 6.下列VB程序段实现计算s=1+1/2+2/3+3/4+…+99/100的值。请将下面划线处代码补充完整。 Private Sub Command1_Click() Dim i As Integer Dim s As Double s=1 For i=2 To 100 s= Next i Text1.Text=Str(s) End Sub 程序划线处应填入的内容是 第1页共1页 专题2解析和枚举算法及VB程序实现（专项练习）（参考答案）1. 【答案】（1）500（2）①False②Label1.Caption=Str(c) ③开始 【解析】（1）计时器timer的interval属性表示时钟频率，其单位为毫秒。题干中的频率为0.5秒，故答案为500。 （2）①根据题意可知，按钮标题变为“开始”的同时，计时器停止工作，故答案为false。②根据题意可知，每次产生的抽奖号码都要显示在label1中，故答案为Label1.Caption=Str(c)。 （3）初始时为“开始”，单击一次后变为“停止”，单击两次后变为“开始”，以此类推可知，单击奇数次后为停止，单击偶数次后为开始。故答案为开始。 2. 【答案】（1）Com1（2）①n = Val(Text1.Text) ②Str(2*(n-i)+1) ③Text2.Text = s 【解析】（1）代码中第一行的“Com1_Click”是事件驱动过程名，由对象名和事件名组成，故答案为Com1。（2）①变量n为正整数，类型为整型，其值通过文本框text1输入，故答案为n = Val(Text1.Text)。②代码中for循环的功能是逐个推理数字串中的数据，数字串前半段为依次递增2，后半段为依次递减2，else解决的就是后半段数据的计算，s为字符串型，故答案为Str(2*(n-i)+1)。③最终的结果存储在变量s中，需要通过文本框text2输出，故答案为Text2.Text = s。 3. 【答案】（1）Caption（2）①n = Val(Text1.Text) ②y * 10 + x Mod10③Str(sum) 【解析】（1）窗体类对象的标题显示内容由Caption属性来决定，故填Caption。 （2）①变量n表示回文数，类型为长整型，其值通过text1来输入，故答案为n = Val(Text1.Text)。②返回个位数，将原有的y扩大10倍。故y * 10 + x Mod10。③变量sum表示某区间内回文数的总个数，其值为长整型，通过标签Label2输出时，需要现转换为字符类型，故答案为Str（sum） 4. 【答案】①Step7 ②c = s Mod10③a=1or b=1or c=1 【解析】①循环变量s的初值为105，而105是三位数中最小的且能被7整除的数，那么下一个能被7整除的数字必然105+7，为了使枚举算法更加高效，步长值应为7，故答案为step7。②变量c表示一个三位数s的个位，最直接且最常用的表达式为c = s Mod10，本题答案也可以是c= s-a*100-b*10。③题干中要求“至少有一位数为1”，该数为一个三位数，a表示百位，b表示十位，c表示个位，故答案为a=1or b=1or c=1。 五年级思维训练7 枚举法 1. 今年是2002年，把2002年这样的年份称为“对称年”（年份的个位数字和千位数字相同，百位数字和十位数字相同），从2000年～2999年之间共有个“对称年”。 2. 在所有的三位数中，满足其数字和等于12的共有个。 3. 下边的加法运算，答案824正好和上面的加数428数字顺序相反，如果选出另外一个三位数加上396后，答案也正好和所选的三位数的数字顺序相反的话，可以选出若干个这样的三位数，这样的三位数还有（除去428）个。 428 +396 824 4. 从1、2、3、4、5、6、7、8、9中选出7个数，使得它们的和是3的倍数，共有种不同选法。 5. 一次，齐王与大将田忌赛马。每人有四匹马，分为四等。田忌知道齐王这次比赛马的出场顺序依次为一等、二等、三等、四等，而且还知道这八匹马跑得最快的是齐王的一等马，接着依次为自己的一等，齐王的二等，自己的二等，齐王的三等，自己的三等，齐王的四等，自己的四等。田忌有种方法安排自己的马的出场顺序，保证自己至少能赢两场比赛。 6. 小珊到邮局购买5张邮票，并要求这些邮票的式样都要相同且全部都要互相连接在一起（两张邮票之间只有顶点与顶点相连不算相连在一起）。现在邮局只存最后的9张邮票。如下图所示，为满足小珊的要求，请问邮局的职员有多少种不同的撕邮票的办法？ 7. 给定三种重量的砝码（每种数量都有足够多个）3kg、11kg、17kg，将它们组合凑成100kg 有种不同的方案（每种砝码至少有一块）。 8. 将下图中20张扑克牌分成10对，每对红心和黑桃各一张。问：你能分出几对这样的牌，使两张牌上的数的乘积除以10的余数是1？（将A看成1） 9. 有五种价格分别为2元、5元、8元、11元、14元的礼品以及五种价格分别为1元、3元、 常用算法设计方法 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0； （2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)；/*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)； 枚举算法题目及其代码 By LYLtim 1、砝码称重(Weight) 【问题描述】 设有1g，2g，3g，5g，10g，20g的砝码各若干枚（其总重≤1000g）。【输入格式】 a1 a2 a3 a4 a5 a6(表示1g砝码有a1个，2g砝码有a2个，..20g砝码有a6个) 【输出格式】 Total=N (N表示用这些砝码能称出的不同重量的个数，不包括一个砝码也不用的情况) 【输入样例】weight.in 1 1 0 0 0 0 【输出样例】weight.out Total=3，表示可以称出1g，2g，3g三种不同的重量 【参考程序】 var i,a1,a2,a3,a4,a5,a6,s:word; a:array[1..6]of word; b:array[0..1000]of boolean; begin assign(input,'weight.in');reset(input); assign(output,'weight.out');rewrite(output); fillchar(b,sizeof(b),false); s:=0; for i:=1 to 6 do read(a[i]); for a1:=0 to a[1] do for a2:=0 to a[2] do for a3:=0 to a[3] do for a4:=0 to a[4] do for a5:=0 to a[5] do for a6:=0 to a[6] do if not b[a1+a2*2+a3*3+a4*5+a5*10+a6*20] then begin b[a1+a2*2+a3*3+a4*5+a5*10+a6*20]:=true; inc(s); end; writeln('Total=',s-1); close(input);close(output); 《实用的枚举算法》教案 上课时间：班级：技术1班授课教师：徐飞翔 一、教学目标： 1、知识与技能： （1）理解枚举算法的概念。 （2）通过枚举算法，理解循环中嵌套分支的结构特点，执行过程。 （3）在理解流程图的基础上，初步实现VB代码的编写，并上机用VB语言实现程序的功能。 2、过程与方法： （1）培养同学自主探索研究、解决问题的能力。 （2）能通过实际问题的分析、求解过程，尝试归纳出利用枚举算法解决问题的思路和方法。 （3）培养同学用计算机程序解决问题的思维能力。 3、情感态度与价值观： （1）通过解决任务，培养同学勇于尝试，不怕困难的精神。 （2）积极参与、主动探究；合作学习，体验成功。 二、教学设计思想： 《学科教学指导意见》中对枚举算法的教学目标是使学生能了解枚举算法的概念，并用枚举算法来解决实际问题。根据这两次信息技术选考考试的难度，此课例不要求同学独立地画出流程图，而仅要求学生在理解枚举算法设计思想的基础上，读懂循环中嵌套分支的流程图，并完成主程序关键处的选择或填空（其中填空比选择对学生思维的要求又高一些）。 三、学情分析： 通过前几个章节的学习与实践，VB中几个相关的函数已经讲解并上机实践过了，对于3种基本控制结构大部分同学已理解，对于用流程图描述算法也非常熟悉，VB上机操作已有一定的实践，为本节内容的学习提供了良好的基础。 对于简单的程序段也有一定的认知意识，那么在本课中学生会觉得设计思想比较容易掌握。困难之处在于如何将题目的设计思想转化为流程图，根据流程图写出相应的代码，并通过自己编制程序上机实践来体验。那么在课堂分析过程中学生将从听课--理解--体验--探究，这些过程中全面掌握枚举算法的设计思想，并能用此算法来解决日常生活问题及与其他学科有所关联的一些简单问题。 四、教学重点： 理解枚举算法的概念和基本特征。 五、教学难点： a)熟练掌握循环结构、分支结构的嵌套使用。 b)枚举算法思想的理解与实现（流程图转化为VB代码并上机实践）。 六、教学准备： 计算机机房、教学课件（枚举算法.ppt） 七、教学过程： （一）新课导入 小明不小心把寝室门钥匙丢了，他去寝室管理员那里去找钥匙开门。寝室管理员那里总共有100把钥匙，其中配套的钥匙有若干把，但钥匙上只有1到100的编号没有寝室编号，请问小明如何才能找出能开自己寝室门的所有钥匙？ 设计算法画出流程图。 （二）学习新课 1.枚举算法：按问题本题的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若是，就采纳这个解，否则就抛弃它。 计数枚举法例题讲解 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】 计数枚举法经典例题讲解 例1一本书共100页，在排页码时要用多少个数字是6的铅字（适于三年级程度）解：把个位是6和十位是6的数一个一个地列举出来，数一数。 个位是6的数字有：6、16、26、36、46、56、66、76、86、96，共10个。 十位是6的数字有：60、61、62、63、64、65、66、67、68、69，共10个。 10+10=20（个） 答：在排页码时要用20个数字是6的铅字。 例2 从A市到B市有3条路，从B市到C市有两条路。从A市经过B市到C市有几种走法（适于三年级程度） 解：作图3-1，然后把每一种走法一一列举出来。 第一种走法：A ① B ④ C 第二种走法：A ① B ⑤ C 第三种走法：A ② B ④ C 第四种走法：A ② B ⑤ C 第五种走法：A ③ B ④ C 第六种走法：A ③ B ⑤ C 答：从A市经过B市到C市共有6种走法 例3 9○13○7=100 14○2○5=□ 把+、-、×、÷四种运算符号分别填在适当的圆圈中（每种运算符号只能用一次），并在长方形中填上适当的整数，使上面的两个等式都成立。这时长方形中的数是几（适于四年级程度） 解：把+、-、×、÷四种运算符号填在四个圆圈里，有许多不同的填法，要是逐一讨论怎样填会特别麻烦。如果用些简单的推理，排除不可能的填法，就能使问题得到简捷的解答。 先看第一个式子：9○13○7=100 如果在两个圆圈内填上"÷"号，等式右端就要出现小于100的分数；如果在两个圆圈内仅填"+"、"-"号，等式右端得出的数也小于100，所以在两个圆圈内不能同时填"÷"号，也不能同时填"+"、"-"号。 要是在等式的一个圆圈中填入"×"号，另一个圆圈中填入适当的符号就容易使等式右端得出100。9×13-7=117-7=110，未凑出100。如果在两个圈中分别填入"+"和"×"号，就会凑出100了。 9+13×7=100 再看第二个式子：14○2○5=□ 上面已经用过四个运算符号中的两个，只剩下"÷"号和"-"号了。如果在第一个圆圈内填上"÷"号，14÷2得到整数，所以： 14÷2-5=2 即长方形中的数是2。 例4 印刷工人在排印一本书的页码时共用1890个数码，这本书有多少页（适于四年级程度）解：（1）数码一共有10个：0、1、2……8、9。0不能用于表示页码，所以页码是一位数的页有9页，用数码9个。 基础算法（一）枚举（穷举）法 无论什么类型的试题，只要能归纳出数学模型，我们尽量用解析方法求解，因为一个好的数学模型建立了客观事物间准确的运算关系。 在一时找不出解决问题的更好途径时，可以根据问题中的约束条件，将所有可能的解全部列举出来，然后逐一验证是否符合整个问题的求解要求。 一、枚举法的基本思想: 从可能的解集合中一一穷举各元素，用题目给定的检验条件判定哪些是有用的，哪些是无用的，能使命题成立的，即为其解。 这种思维方法主要是基于计算机运算速度快的特点。 二、枚举法解题思路： 1、对命题建立正确的数学模型； 2、根据命题确定数学模型中各变量的变化范围（即可能解的范围）； 3、利用循环语句、条件判断语句逐步求解或证明。 三、枚举法的特点： 算法简单，但运算量大。 对于可能确定解的范围，又一时找不到更好的算法时，可以采用枚举法。 1、求满足表达式A+B=C的所有整数解，其中A、B、C为1～3之间的整数。 2、鸡兔同笼问题（在同一个笼子里有鸡和兔子若干只，从上面看，能看到 20个头，从下面看，能看到60只脚，问鸡兔各有多少只？） 3、百钱百鸡问题（一百块钱要买一百只鸡，这一百只鸡必须包含母鸡、公 鸡和小鸡，其中，公鸡5元一只，母鸡3元一只，小鸡1元三只，问有哪些购买方案？） 4、水仙花数问题（ABC=A3+B3+C3,列出所有的整数ABC） 5、一根29厘米长的尺子，只允许在上面刻7个刻度，要能用它量出1～29 厘米的各种长度，试问刻度应该怎样选择？ 6、猴子选大王：有M个猴子围成一圈，每个有一个编号，编号从1到M。 打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一个开始，每隔N个，数到的猴子出圈，最后剩下来的就是大王。 要求：从键盘输入M，N，编程计算哪一个编号的猴子成为大王。 参考程序： 计数枚举法经典例题讲解 例1一本书共100页，在排页码时要用多少个数字是6的铅字?(适于三年级程度） 解：把个位是6和十位是6的数一个一个地列举出来，数一数。?个位是6的数字有：6、１6、26、３6、46、５６、66、76、86、96，共10个。 十位是6的数字有：60、61、62、63、6４、65、66、67、68、６9,共10个。?１０+１0=2０（个）答:在排页码时要用20个数字是６的铅字。 例2 从A市到B市有３条路,从B市到C市有两条路。从A市经过B市到C市有几种走法？(适于三年级程度） 解：作图３-1，然后把每一种走法一一列举出来。 第一种走法：A ① B ④ C?第二种走法:A ① Ｂ⑤ C 第三种走法：Ａ② B ④ Ｃ?第四种走法:Ａ② B ⑤ C?第五种走法：Ａ③ B④ C 第六种走法：Ａ③ Ｂ⑤ C 答：从A市经过B市到Ｃ市共有6种走法 例3９○1３○7=1０0?14○２○5=□?把+、-、×、÷四种运算符号分别填在适当的圆圈中（每种运算符号只能用一次），并在长方形中填上适当的整数,使上面的两个等式都成立。这时长方形中的数是几?（适于四年级程度）?解：把+、－、×、÷四种运算符号填在四个圆圈里,有许多不同的填法，要是逐一讨论怎样填会特别麻烦。如果用些简单的推理,排除不可能的填法,就能使问题得到简捷的解答。 先看第一个式子:9○13○7＝100 如果在两个圆圈内填上＂÷＂号，等式右端就要出现小于100的分数；如果在两个圆圈内仅填"＋＂、＂-"号，等式右端得出的数也小于１0０,所以在两个圆圈内不能同时填"÷＂号,也不能同时填"+"、"－"号。 要是在等式的一个圆圈中填入"×"号，另一个圆圈中填入适当的符号就容易使等式右端得出1０0。9×13-7=1１７－7=110，未凑出100。如果在两个圈中分别填入＂+"和"×＂号，就会凑出100了。 9+13×7=100 再看第二个式子：１4○２○5=□ 上面已经用过四个运算符号中的两个,只剩下"÷"号和"-"号了。如果在第一个圆圈内填上"÷"号, 14÷2得到整数,所以：?14÷2-５=2?即长方形中的数是2。 例4 印刷工人在排印一本书的页码时共用１８9０个数码，这本书有多少页？(适于四年级程度）解:(1)数码一共有1０个：０、1、2……8、9。0不能用于表示页码，所以页码是一位数的页有9页,用数码9个。?（2)页码是两位数的从第１0页到第99页。因为99-9＝90，所以,页码是两位数的页有90页,用数码:?2×9０=18０（个) （3)还剩下的数码:? 1８9０-9－1８０＝1７01(个) （4）因为页码是三位数的页，每页用3个数码,１00页到9９9页,999-９9=９00,而剩下的1701个数码除以3时,商不足6０0，即商小于900。所以页码最高是3位数,不必考虑是4位数了。往下要看１701个数码可以排多少页。?1７01÷３=567（页)?（5)这本书的页数: ９+90＋5６７=66６(页) 答略。 例5 用一根80厘米长的铁丝围成一个长方形,长和宽都要是5的倍数。哪一种方法围成的长方形面积最大？(适于四年级程度）谈谈用枚举算法解决问题的编程思路与步骤方法
常用算法枚举法
算法(枚举)
三年级数学枚举法练习题题库
枚举算法 练习题
枚举算法教案
(完整版)小学奥数枚举法题及答案【三篇】
枚举算法题目及其代码
一年级数学 奥数试题 枚举法(扫描版)
常用算法(二)——穷举搜索法
VB解析算法及程序实现
专题02 解析和枚举算法及VB程序实现(专项练习)(参考答案)
五年级思维专项训练7 枚举法(原卷+解析版)全国通用
算法设计与分析(详细解析(含源代码)
枚举算法题目及其代码
实用的枚举算法教案
计数枚举法例题讲解
基础算法(一)枚举法
计数枚举法经典例题讲解