第3章数 学 广 角 本章的设计灵感来自于小学数学教材中的“数学广角”“你知道吗”等栏目，案例来源于人教版、北师大版等小学数学教材。通过选取学生熟悉的数学内容作为编程教学案例，在使用数学方法解决问题的基础上，讲授使用编程方式解决问题，从而扩展学生解决复杂问题的方法和能力。 在编程中，模拟策略、枚举策略、递推策略等基本的算法思想有着非常广泛的应用。本章结合小学数学应用题中“木桶蓄水”等较为常见的工程问题，讲授使用模拟策略编程解决问题； 通过破解“宝箱密码”问题，讲授枚举策略在编程中的应用； 在解决“细胞分裂”问题中，比较了利用等比数列知识求解和使用递推策略编程求解的异同。这些数学问题难度不大，数据规模较小，通过纸笔演算就可以快速求解。但是，当问题的规模变大，计算机具有强大运算能力的优势就发挥出来了。 本章依托基本的算法策略，还介绍了使用编程方式解决排列组合问题、探索概率问题和极限问题，以及用筛选法求素数、验证哥德巴赫猜想、更相减损术、二进制数转换等。现在，就让我们踏上妙趣横生的数学探秘之旅吧！ 3.1木桶蓄水 问题描述 大文豪托尔斯泰对数学也很感兴趣，他喜欢的一道数学题是这样的。 一个木桶的上方有两根水管，如果单独打开其中一根，则24分钟可以注满水桶； 如果单独打开另一根，则15分钟可以注满。在木桶底部还有一个小孔，水可以从小孔中流出，一满桶水2小时可流完。如果同时打开两根水管注水，并且小孔也同时放水，那么多长时间才能将水桶注满？ 编程思路 这道蓄水题在小学应用题中很常见，属于工程问题，利用算式“工作时间=工作总量÷工作效率”可以轻松求解，即： 工作时间=1÷124+115-1120 这里把工作总量看作“1”，工作效率是工作时间的倒数(它表示单位时间内完成工作总量的比例)。由于注水的同时也在放水，因此工作效率=注水效率-放水效率。 如果用编程方式求解该问题，可以采用模拟策略。所谓模拟策略策略就是编写程序模拟现实世界中事物的变化过程，从而完成相应任务的方法。模拟法对算法设计的要求不高，只需要按照问题描述的过程编写程序，使程序按照问题要求的流程运行，就能求得问题的解。 在编程求解木桶蓄水问题时，可以将时间作为主线，在一个循环结构中，让时间以分钟为单位逐渐增加，同时不断累加工作效率(即注水、放水)。当工作总量大于或等于1时(即木桶注满水)结束循环，即可求得工作时间。 编程实现 Scratch程序清单(见图31) 运行程序得到答案： 注满水桶需要10分钟。 图31“木桶蓄水”Scratch程序清单 Python程序清单 def main(): '''木桶蓄水''' time = 0 barrel = 0 while barrel 1:#注满水桶 time += 1#增加时间 barrel += (1/24 + 1/15)#两根水管同时注水 barrel -= 1/120#小孔放水 print(time, barrel, sep=': ') print('注满水桶需要%d分钟' % time) if __name__ == '__main__': main() C++程序清单 #include bits/stdc++.h using namespace std; //木桶蓄水 int main() { int time = 0; float barrel = 0; while (barrel 1) {//注满水桶 time += 1;//增加时间 barrel += (1.0/24 + 1.0/15);//两根水管同时注水 barrel -= 1.0/120;//小孔放水 cout time ": " barrel endl; } cout "注满水桶需要" time "分钟" endl; return 0; } 拓展练习 请使用模拟策略编程求解下列问题。 (1) 小明用手机玩游戏没电了，赶紧接上一个大容量充电宝充电。已知手机玩游戏3分钟掉2%的电量，用充电宝5分钟可充5%的电量，请问小明用手机一边玩游戏一边充电需要多久可以充满电？ (2) 父亲和儿子一起出去玩，儿子带了一条小狗先出发，10分钟后父亲出发。父亲刚一出门，小狗就向他跑过来，到了父亲身边后马上又返回到儿子那里，就这样往返跑着。如果小狗每分钟跑500米，父亲每分钟跑200米，儿子每分钟跑100米，那么从父亲出门到追上儿子的这段时间里，小狗一共跑了多少米？ (3) 警察追击一个逃窜的小偷，小偷在16点开始从甲地以每小时10千米的速度逃跑。警察在22点接到命令，以每小时30千米的速度开始从乙地追击。已知甲乙两地相距60千米，问警察几个小时可以追上小偷? 3.2宝箱密码 问题描述 你能根据以下的线索找出百宝箱的密码吗？ (1) 密码是一个六位数。 (2) 这个六位数在800000与900000之间，并且千位上是0，十位上是4，百位数和个位数相同。 (3) 密码的十万位、万位、千位上的数字组成的三位数除以百位、十位上的数字组成的两位数，商是35。 编程思路 根据题目中给出的线索，可以知道密码的十万位、万位、千位上的数字组成的三位数是“**0”，百位、十位上的数字组成的两位数是“*4”，三位数除以两位数的商是35。据此，用35和两位数进行试乘，就可以求出三位数，并最终破解宝箱密码。 如果用编程方式求解该问题，可以采用枚举法。所谓枚举法，又称为穷举法，它是将解决问题的可能方案全部列举出来，并逐一验证每种方案是否满足给定的检验条件，直到找出问题的解。 在宝箱密码这个问题中，可以通过一个循环结构逐个列举出800000与900000之间的六位数，然后根据题目中给出的线索进行判断，如果某个数符合要求，则找到该问题的解。 编程实现 Scratch程序清单(见图32) 运行程序得到答案： 宝箱密码是840242。 图32“宝箱密码”Scratch程序清单 图32(续) Python程序清单 def main(): '''宝箱密码''' for n in range(800000, 900000): d1 = n % 10 d2 = n // 10 % 10 d3 = n // 100 % 10 d4 = n // 1000 % 10 d5 = n // 10000 % 10 d6 = n // 100000 % 10 if d4 == 0 and d2 == 4 and d3 == d1: if (d6 * 100 + d5 * 10 + d4) / (d3 * 10 + d2) == 35: print('宝箱密码是', n) if __name__ == '__main__': main() C++程序清单 #include bits/stdc++.h using namespace std; //宝箱密码 int main() { int d1, d2, d3, d4, d5, d6; for (int n = 800000; n 900000; n++) { d1 = n % 10; d2 = n / 10 % 10; d3 = n / 100 % 10; d4 = n / 1000 % 10; d5 = n / 10000 % 10; d6 = n / 100000 % 10; if (d4 == 0 and d2 == 4 and d3 == d1) if ((d6 * 100 + d5 * 10 + d4) / (d3 * 10.0 + d2) == 35) cout "宝箱密码是" n endl; } return 0; } 拓展练习 请使用枚举法编程求解下列问题。 (1) 在图33中的○里分别填上3、4、5、6、7，使每条线上的三个数相加都得12。 (2) 在图34中的○里分别填上21、22、23、24、25，使每个条线上的3个数相加都得69。 图33练习题(1)图 图34练习题(2)图 (3) 有一个算式： ABCD-CDC=ABC。其中，A、B、C、D均为1位正整数。问A、B、C、D的值分别是什么？ 3.3细胞分裂 问题描述 有一种细胞分裂的速度非常快，在最初1分钟，由原来的1个分裂为2个,再过1分钟，已经分裂的2个又各自分裂成2个，一共就有4个。按照这个速度，45分钟产生的细胞就可以充满一个瓶子。请问最后共有细胞多少个？ 编程思路 在这个问题中，细胞分裂的个数构成一个数列： 1，2，4，8，16，32……规律是后一个数是前一个数的2倍。这是一个等比数列，其定义是： 如果一个数列从第2项起，每一项与它的前一项的比等于同一个常数，这个数列就叫作等比数列。这个常数叫作等比数列的公比，公比通常用字母q表示。 当q=1时，求和公式为Sn=na1； 当q≠1时，求和公式为Sn=a1(1-qn)1-q。 在细胞分裂这个问题中，数列的公比q=2，项数n=45,首项a1=1，则利用求和公式可计算出细胞的总个数。 等比数列是高中阶段学习的内容，对于低年级学生来说不容易理解，那么我们换一种方法，通过编程的方式求解这个细胞分裂的问题。 在编程时可以采用递推策略。所谓递推策略，就是根据已知条件，利用计算公式进行若干步重复的运算，最终求得答案的一种方法。根据推导问题的方向，可将递推算法分为顺推法和逆推法。所谓顺推法，就是从问题的起始条件出发，由前往后逐步推算出最终结果的方法。逆推法与之相反，它是从问题的最终结果出发，由后往前逐步推算出问题的起始条件。逆推法是顺推法的逆过程。 细胞分裂这个问题可以采用顺推法进行编程。变量“细胞”用于记录每次细胞分裂的数量，变量“总数”用于累加每次细胞分裂的数量，这两个变量的初始值都设为1，表示在最初的1分钟只有一个细胞。然后在一个循环结构中，依次累加每次细胞分裂的数量，经过44次迭代计算，即可求得细胞的总数量。 编程实现 Scratch程序清单(见图35) 运行程序得到答案： 细胞数量是35184372088831。 图35“细胞分裂”Scratch程序清单 Python程序清单 def main(): '''细胞分裂''' cells = 1 total = 1 for i in range(44): cells = 2 * cells total += cells print('细胞数量是%d' % total) if __name__ == '__main__': main() C++程序清单 #include bits/stdc++.h using namespace std; //细胞分裂 int main() { long long cells = 1; long long total = 1; for (int i = 0; i 44; i++) { cells = 2 * cells; total += cells; } cout "细胞数量是" total endl; return 0; } 拓展练习 请使用递推策略编程求解下列问题。 (1) 一个小朋友要把100颗糖装到纸盒里，他在第1个盒子放1颗，第2个盒子放2颗，第3个盒子放4颗，第4个盒子放8颗……照这样放下去，直到放满7个盒子。问这100颗糖够不够？ (2) 老王卖瓜，自卖自夸。第1个顾客来了，买走他所有西瓜的一半又半个； 第2个顾客来了，买走他余下西瓜的一半又半个……当第9个顾客来时，他已经没有西瓜可卖了。问老王原来有多少个西瓜？ (3) 一个8×8规格的国际象棋棋盘有64个格子，假设棋盘无限大，在第1格放1粒麦子，第2格放2粒麦子，第3格放4粒麦子，第4格放8粒麦子……依此类推，直到在第64格放上麦子。问整个棋盘全部64格共放了多少粒麦子？ 3.4早餐搭配 问题描述 在下列早餐中，饮料和点心只能各选1种，问共有多少种不同的搭配？ 饮料： 豆浆、牛奶 点心： 蛋糕、油条、饼干、面包 请编写一个程序，列出所有的搭配方案。 编程思路 这是一道排列组合题，有两种方法求解答案。根据题目提供的信息可以将这些早餐分成饮料和点心两类，饮料2种，点心4种，并且饮料和点心只能各选1种。 (1) 分类相加法： 第1类(选豆浆)有4种搭配方案，第2类(选牛奶)也有4种搭配方案。所以，搭配方案共有4+4=8(种)。 (2) 分步相乘法： 搭配早餐分两步，第一步选饮料，有2种选择； 第2步选点心，有4种选择。所以，搭配方案共有2×4=8(种)。 在编程时，将饮料和点心分别存放在两个列表中，然后通过两重循环列举出它们的组合，并存放在“方案”列表中。 编程实现 Scratch程序清单(见图36) 运行程序得到答案： 在“方案”列表中列出了8种不同的早餐搭配方案。 图36“早餐搭配”Scratch程序清单 Python程序清单 def main(): '''早餐搭配''' drinks = ［'豆浆', '牛奶'］ foods = ［'蛋糕', '油条', '饼干', '面包'］ for j in range(2): for i in range(4): print(drinks［j］, foods［i］, sep=' + ') if __name__ == '__main__': main() C++程序清单 #include bits/stdc++.h using namespace std; //早餐搭配 int main() { string drinks［］ = {"豆浆", "牛奶"}; string foods［］ = {"蛋糕", "油条", "饼干", "面包"}; for (int j = 0; j 2; j++) for (int i = 0; i 4; i++) cout drinks［j］ " + " foods［i］ endl; return 0; } 拓展练习 请编程求解下列问题。 (1) 唐僧、孙悟空、猪八戒、沙僧四人站成一排，一共有多少种站法？具体怎么站？ (2) 用0、3、7、6可以组成多少个没有重复数字的两位数？具体是哪些？ (3) 一个口袋里放了12个球，其中有3个红色的球、3个白色的球和6个黑色的球，从中任取8个球，请问共有多少种不同的颜色搭配？具体是哪些？ 3.5骰子赛车 问题描述 骰(tóu)子又叫色(shi)子。它是一个正立方体，有6个面，每个面分别有1~6个点，其相对两面的数字之和都是7。下面利用骰子玩一个有趣的骰子赛车游戏。 游戏规则： 由两名玩家参与游戏，分为A、B两队，A队以骰子的5、6、7、8、9点为幸运数字，B队以骰子的2、3、4、10、11、12为幸运数字。两名玩家同时各投掷一枚骰子，当骰子之和是哪一队的幸运数字时，该队的赛车前进一步，赛车先到达终点的一队获胜。