“编”玩边学：Scratch趣味编程进阶——妙趣横生的数学和算法

1、案例精彩、数量众多、涵盖面广。2、案例选择考究，富于趣味性、知识性、故事性。3、案例编程脚本以简短居多，易于理解消化。4、首创扑克牌学算法游戏，不用编程也能学算法。目前学校或培训机构的少儿编程课程多以趣味小游戏教学为主，有着对编程课程升级的需求，升级方向则是数学和算法等方面；而家长也希望学生能在受过游戏编程入门教育后，逐渐过渡到对升学有帮助的中小学信息学竞赛领域。本书正起到了编程课程升级、知识衔接的作用。如果你不再满足用Scratch编写小游戏、小动画，那么本书将带领你走进妙趣横生的数学和算法编程的新世界——带你求解古代“应用题”，感受古算题的那份诗意；带你探索“数字黑洞”，感受它“吞噬”一切数字的那份神秘；带你用简单图形创造出美丽的雪花和树，感受分形图的那份神奇；带你一笔画出美丽的玫瑰曲线和蝴蝶曲线，感受曲线方程的数学之美；带你玩扑克魔术游戏，不用编程就能学算法，等等。本书为你准备了100个精彩的编程案例，前方高能，一大波妙趣横生的Scratch程序正向你走来…… 

本书将Scratch作为一门程序设计语言看待，通过大量数学和算法方面的编程案例，为广大中小学生提供了一本编程进阶的参考教材。
本书根据案例类型分为12章，共有100个妙趣横生的编程案例，涵盖数字黑洞、数学游戏、古算趣题、逻辑推理、玩扑克学算法、分形图等数学内容。本书*的特点是案例丰富多彩，让人脑洞大开，是广大中小学生在受过Scratch编程入门教育之后进一步提高编程能力的编程宝典。通过阅读本书，将使读者更加热爱编程，更加热爱数学和算法，为广大中小学生打开一片新的数学编程天地。
本书不是零起点教材，适合已经过Scratch入门教育的广大中小学生、编程爱好者和参加中小学信息学竞赛的学生作为参考读物，也适合少儿编程培训机构作为课程设计的参考读物。

谢声涛，小海豚科学馆创始人，致力于线下和线上推广青少年科普教育和编程教育。曾在多家互联网公司工作，历任程序员、研发经理、架构师、技术总监等职，熟悉大规模网站架构设计，擅长复杂应用系统开发，在海量数据管理、搜索引擎技术等应用方面有丰富经验。

第1章数字黑洞11.1西西弗斯黑洞1

1.2冰雹猜想3

1.3圣经数5

1.4卡普雷卡尔黑洞6

1.5数字黑洞1和49

第2章趣味自然数112.1水仙花数11

2.2完全数13

2.3亲密数14

2.4回文数15

2.5勾股数16

2.6四方定理18

2.7尼科彻斯定理19

第3章趣味素数213.1厄拉多塞筛法21

3.2哥德巴赫猜想23

3.3梅森素数25

3.4孪生素数26

3.5回文素数27

3.6可逆素数28目录第4章公约数294.1辗转相除法29

4.2更相减损法30

4.3辗转相减法32

4.4Stein算法33

第5章圆周率355.1割圆术之周长法35

5.2割圆术之面积法37

5.3莱布尼茨级数39

5.4尼拉坎特哈级数40

5.5BBP公式41

5.6蒙特卡罗方法43

第6章曲线之美456.1笛卡儿心形曲线45

6.2桃心形曲线47

6.3玫瑰曲线48

6.4蝴蝶曲线50

6.5外摆线52

6.6自定义外摆线54

第7章神奇分形图567.1谢尔宾斯基三角形56

7.2谢尔宾斯基地毯58

7.3六角形雪花60

7.4二叉树62

7.5勾股树64

第8章古算趣题688.1浮屠增级69

8.2书生分卷70

8.3以碗知僧71

8.4牧童分杏72

8.5诵课倍增73

8.6李白沽酒74

8.7蜗牛爬树75

8.8百僧分馍76

8.9孔明统兵78

8.10千钱百鸡79

8.11酒有几瓶80

8.12日行几里82

8.13利滚利债83

8.14鸡鸭若干84

8.15客有几人85

8.16二果问价86

8.17隔沟算羊87

8.18红灯几盏88

第9章逻辑推理909.1肖像在哪里90

9.2认出五大洲92

9.3赛跑排名93

9.4如何分票95

9.5谁是杀手96

9.6谁是小偷97

9.7新郎和新娘98

9.8谁是雷锋100

9.9诚实族和说谎族101

9.10谁在说谎103

9.11黑与白105

9.12区分旅客国籍106

9.13她们在做什么109

第10章数学游戏11310.1吉普赛读心术113

10.2算术板球游戏115

10.3骰子赛车117

10.4十点半119

10.5抢十八121

10.6常胜将军123

10.7汉诺塔124

10.8兰顿蚂蚁125

第11章竞赛趣题12811.1雯雯摘苹果129

11.2国王发金币130

11.3三色球问题131

11.4小鱼有危险吗132

11.5狐狸找兔子133

11.6龟兔赛跑134

11.7守望者的逃离135

11.8找零钱136

11.9饮料换购137

11.10复制机器人138

11.11猴子选大王139

11.12微生物增殖140

11.13石头剪刀布141

11.14古堡算式143

11.15拦截导弹145

第12章玩扑克学算法14712.1冒泡排序147

12.2选择排序150

12.3插入排序152

12.4希尔排序154

12.5快速排序156

12.6顺序查找158

12.7二分查找159

参考文献162

Scratch是由MIT媒体实验室为青少年开发的图形化编程工具，用于创作交互式故事、动画、游戏和其他程序，凭借其良好的界面交互设计，几乎所有年龄的人都能使用Scratch。作为一种新型的程序设计语言，Scratch具有高级编程语言的许多特性，如对象、事件、线程、同步、子程序、函数、数组、关系运算和逻辑运算等。Scratch采用高度模块化封装设计，屏蔽了各种低级的编译错误，使人得以专注于编程逻辑本身，在中小学计算机编程教育领域越来越受欢迎，甚至在一些大学，也开设Scratch课程作为编程教育的入门课程。

本书精心挑选和设计的100个妙趣横生的编程案例，涵盖了数字黑洞、分形图、曲线方程、圆周率、趣味自然数、古算趣题、逻辑推理、数学游戏、玩扑克学算法等方面的内容，为广大中小学生提供了一本编程进阶的参考教材。

我国的诗词文化源远流长，古代数学家文理兼修，为考生出的“应用题”也是那么富有诗意。比如，这道“诗”题——

　　远望巍巍塔七层，红灯点点倍加增；

　　共灯三百八十一，请问尖头几盏灯？

像这样的古算诗题，直到今天读起来依然朗朗上口，理解起来又浅显易懂。本书也收集了一些妙趣横生的古算诗题，与读者一起分享和感受这份数学的诗意。

在浩瀚的宇宙中有能吞噬一切的神秘黑洞，连光也无法逃脱。而在数学上也有类似奇特的现象，人们称之为“数字黑洞”，它们会按照自身的规则“吞噬”掉一切数字。本书将带读者领略这些妙趣横生的数字黑洞，比如西西弗斯黑洞，它会将一切数字转换为123，并无限重复下去；而被称为“冰雹猜想”的数字黑洞，它会把任意自然数终变换为1，而且它的变换过程有时简直“惊心动魄”。

宇宙间万物极其复杂，而其构成却是简单的细胞、原子、分子等极其微小的事物。在数学中，一条线段、一个三角形、一个四边形或是一个六边形等看似简单无比的几何图形，按一定规则重复之后，却能产生令人称奇的复杂图案。本书将带领读者创造出美丽的雪花、勾股树、二叉树以及谢尔宾斯基三角形等神奇的分形图。

算法是程序的灵魂，但学起来却不容易。我们都知道学习编程重要的是动手实践，但是在学习算法原理时，明明感觉自己懂了，而当编程实现时却又无从下手或是不得要领。本书将带领读者不用编程就能学习排序算法，通过扑克游戏领悟排序算法原理，反复练习就能掌握它们，之后再编程自然倍感简单，小学生也能轻松掌握。

此外，本书还将带领读者感受数学之美，只要一个简洁的曲线参数方程，就能一笔画出妙趣横生的曲线图案，比如笛卡儿心形线、玫瑰曲线、蝴蝶曲线、外摆线等；还将带领读者触摸“数学皇冠上的明珠”，编程验证被称为世界近代三大数学难题之一的“哥德巴赫猜想”……

一言以蔽之，本书通过100个妙趣横生的编程案例，激发学生的求知欲望，引导学生向数学和算法领域前进。

本书不是零起点教材，适合受过Scratch入门教育的中小学生和编程爱好者使用。如果读者之前学过使用Scratch编写小游戏，已经掌握了Scratch软件的基本操作，那么本书将非常适合读者进一步提升编程能力。

好了，让我们一起开始妙趣横生的Scratch编程之旅吧！

 谢声涛2018年1月

第3章趣 味 素 数素数是数学中一个重要的基本概念，我们从小学就开始接触它。素数的定义是，一个大于1的自然数，如果只能被1和它自身整除，就叫作素数。任何一个大于1的自然数都可以分解成几个素数连乘积的形式，而且这种分解是的。可以说，素数是构成整个自然数大厦的砖瓦。在两千多年前，古希腊数学家欧几里得在《几何原本》这本著名的数学著作中对素数进行了详细的讨论，并巧妙地证明了“素数是无穷多个”的，但没有找到无穷多个素数的分布规律。公元前250年，古希腊数学家厄拉多塞创造了著名的古典筛法来寻找素数。在探索素数的征途中，费马、欧拉、狄里克雷、高斯、哥德巴赫、陈景润等数学家承前启后、乐此不疲地投入对素数的研究中，各种数学方法和理论被发展，素数定理、哥德巴赫猜想、黎曼假设、陈氏定理等不断地给数学界注入新鲜血液。随着技术进步和数学家不懈地探索，素数的神秘密码也被数学家一点点地破译，但是素数依然有着无穷的奥秘等着我们去发现。本章将介绍寻找素数的方法和寻找一些有趣的素数，内容如下： 厄拉多塞筛法 哥德巴赫猜想 梅森素数 孪生素数 回文素数 可逆素数3.1厄拉多塞筛法〖*4/5〗在两千多年前的古希腊，数学家厄拉多塞在写一本叫作《算术入门》的书。在写到“数的整除”部分时，他想： 怎样才能找到一种简单的、判断素数的方法呢？左思右想也没个结果，于是他就去郊外散步。他边走边思考，竟然走到了一家磨坊。磨坊的工人们正在忙碌着，有的搬运麦子，有的磨面，有的筛粉。厄拉多塞突然眼前一亮，是否可以用筛选的方法来挑选素数？把合数像筛粉一样筛掉，留下的肯定就是素数了。第3章趣味素数厄拉多塞受此启发创造了这样一种与众不同的寻找素数的方法： 先将2～n的各个自然数放入表中，然后在2的上面画一个圆圈，再划去2的其他倍数；个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的个数是5，将它画圈，并划去5的其他倍数……以此类推，直到所有小于或等于n的各数都画了圈或被划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 n的素数。这个简单而高效的寻找素数的方法被称作“厄拉多塞筛法”。请使用“厄拉多塞筛法”算法编写程序，找出自然数1000以内的所有素数。
寻找素数的厄拉多塞筛法易于理解，据此编写程序实现筛选1000以内的自然数中的所有素数。该程序由入口程序和厄拉多塞筛法、各数入表、删除合数等模块组成。该程序的核心是“厄拉多塞筛法”模块。在该模块中，先调用“各数入表”模块把待筛选的自然数放入“素数表”列表中，接着调用“删除合数”模块，把素数表中的合数都删除。如果当前要操作的素数的平方大于要筛选的数时，就可以结束筛选过程，因为当前素数后面没有被删除的数都是素数。
程序清单见图31和图32。图31 “厄拉多塞筛法”程序清单其中，模块“删除合数”用于删除某个素数的其他倍数，即删除素数表中的部分合数。我们从列表“素数表”中删除某个素数的倍数时，由后往前删除，直至遇到该素数为止。如果是由前往后删除，则列表中的元素会重新排列，从而导致程序不能实现想要的结果。该模块的代码见图32。图32“删除合数”模块单击绿旗运行程序，瞬间就能找出2～1000的素数。
通过修改“厄拉多塞筛法”模块的调用参数，寻找1000～2000的素数。3.2哥德巴赫猜想〖*4/5〗哥德巴赫猜想是指任何大于2的偶数都可以写成两个素数之和。例如，8＝3 5，12＝5 7，16＝3 13，……这是德国数学家哥德巴赫在1742年提出的一个猜想，它被称为世界近代三大数学难题之一。哥德巴赫自己无法证明这个猜想，曾写信请教赫赫有名的大数学家欧拉帮忙证明。但是终其一生，欧拉也没能给出严格的证明。哥德巴赫猜想被提出后吸引了全世界数学家和数学爱好者的目光，它被人们称为数学皇冠上一颗可望而不可即的“明珠”。时至今日，哥德巴赫猜想依然没有解决，目前好的成果(陈氏定理)是1966年由中国数学家陈景润取得的。请编写验证“哥德巴赫猜想”的程序，对“1000以内大于2的正偶数都能分解为两个素数之和”进行验证。
将一个偶数n分解为j和n-j两部分，再判断如果j和n-j都是素数，那么该偶数就验证通过。该程序的代码见图33。在该程序中，用到一个名为“是否素数”的模块(见图34)，它用于判断一个自然数是否为素数。在本章的其他程序中也用到这个判断素数的模块，将不再单独列出。
程序清单见图33和图34。图33“哥德巴赫猜想”程序清单图34“是否素数”模块单击绿旗运行程序，1000以内通过验证的正偶数被记录到“哥德巴赫猜想”列表中。
一个正偶数可能会有多种分解方法，该程序中只记录其中一种分解方法。另外，该程序中判断素数的方法不是高效的，在数据量少时尚可使用。如果你对此有兴趣，可以尝试先建立一个素数表，再通过素数表来判断一个数是否为素数，这样效率更高。请你试一试，使用上面的程序，继续验证1000～10000的正偶数是否符合“哥德巴赫猜想”。3.3梅森素数〖*4/5〗马林·梅森是一位法国科学家，他为科学事业做了很多有益的工作，被选为“100位在世界科学史上有重要地位的科学家”之一。由于梅森是早系统而深入地研究2p－1型数的人，因而数学界就把这种数称为 “梅森数”，并以Mp记之(其中M为梅森姓名的首字母)，即Mp=2p-1。如果梅森数为素数，则称之为“梅森素数”(即2p－1型素数)。已经证明了，如果2p-1是素数，则幂指数必须是素数；然而，反过来并不对，当p是素数时，2p-1不一定是素数。是否存在无穷多个梅森素数是数论中未解决的著名难题之一。目前仅发现49个梅森素数，的是 274207281－1(即2的74207281次方减1)，有22338618位数。由于这种素数珍奇而迷人，因此被人们誉为“数海明珠”。自梅森提出其断言后，人们发现的已知素数几乎都是梅森素数，因此寻找新的梅森素数的历程也就几乎等同于寻找新的素数的历程。请编写程序找出指数p在［2，20］中的梅森素数。
先以Mp=2p－1为模型求出梅森数，再判断该梅森数是否为素数。
程序清单见图35。图35“梅森素数”程序清单