內容簡介

本書將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

精彩書摘

第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“梅森素數”程序清單

前言/序言

Scratch是由MIT媒體實驗室為青少年開發的圖形化編程工具，用於創作交互式故事、動畫、遊戲和其他程序，憑藉其良好的界麵交互設計，幾乎所有年齡的人都能使用Scratch。作為一種新型的程序設計語言，Scratch具有高級編程語言的許多特性，如對象、事件、綫程、同步、子程序、函數、數組、關係運算和邏輯運算等。Scratch采用高度模塊化封裝設計，屏蔽瞭各種低級的編譯錯誤，使人得以專注於編程邏輯本身，在中小學計算機編程教育領域越來越受歡迎，甚至在一些大學，也開設Scratch課程作為編程教育的入門課程。

本書精心挑選和設計的100個妙趣橫生的編程案例，涵蓋瞭數字黑洞、分形圖、麯綫方程、圓周率、趣味自然數、古算趣題、邏輯推理、數學遊戲、玩撲剋學算法等方麵的內容，為廣大中小學生提供瞭一本編程進階的參考教材。

我國的詩詞文化源遠流長，古代數學傢文理兼修，為考生齣的“應用題”也是那麼富有詩意。比如，這道“詩”題——

　　遠望巍巍塔七層，紅燈點點倍加增；

　　共燈三百八十一，請問尖頭幾盞燈？

像這樣的古算詩題，直到今天讀起來依然朗朗上口，理解起來又淺顯易懂。本書也收集瞭一些妙趣橫生的古算詩題，與讀者一起分享和感受這份數學的詩意。

在浩瀚的宇宙中有能吞噬一切的神秘黑洞，連光也無法逃脫。而在數學上也有類似奇特的現象，人們稱之為“數字黑洞”，它們會按照自身的規則“吞噬”掉一切數字。本書將帶讀者領略這些妙趣橫生的數字黑洞，比如西西弗斯黑洞，它會將一切數字轉換為123，並無限重復下去；而被稱為“冰雹猜想”的數字黑洞，它會把任意自然數最終變換為1，而且它的變換過程有時簡直“驚心動魄”。

宇宙間萬物極其復雜，而其構成卻是簡單的細胞、原子、分子等極其微小的事物。在數學中，一條綫段、一個三角形、一個四邊形或是一個六邊形等看似簡單無比的幾何圖形，按一定規則重復之後，卻能産生令人稱奇的復雜圖案。本書將帶領讀者創造齣美麗的雪花、勾股樹、二叉樹以及謝爾賓斯基三角形等神奇的分形圖。

算法是程序的靈魂，但學起來卻不容易。我們都知道學習編程最重要的是動手實踐，但是在學習算法原理時，明明感覺自己懂瞭，而當編程實現時卻又無從下手或是不得要領。本書將帶領讀者不用編程就能學習排序算法，通過撲剋遊戲領悟排序算法原理，反復練習就能掌握它們，之後再編程自然倍感簡單，小學生也能輕鬆掌握。

此外，本書還將帶領讀者感受數學之美，隻要一個簡潔的麯綫參數方程，就能一筆畫齣妙趣橫生的麯綫圖案，比如笛卡兒心形綫、玫瑰麯綫、蝴蝶麯綫、外擺綫等；還將帶領讀者觸摸“數學皇冠上的明珠”，編程驗證被稱為世界近代三大數學難題之一的“哥德巴赫猜想”……

一言以蔽之，本書通過100個妙趣橫生的編程案例，激發學生的求知欲望，引導學生嚮數學和算法領域前進。

本書不是零起點教材，適閤受過Scratch入門教育的中小學生和編程愛好者使用。如果讀者之前學過使用Scratch編寫小遊戲，已經掌握瞭Scratch軟件的基本操作，那麼本書將非常適閤讀者進一步提升編程能力。

好瞭，讓我們一起開始妙趣橫生的Scratch編程之旅吧！

謝聲濤2018年1月

不錯。。。

此用戶未填寫評價內容

此用戶未填寫評價內容

此用戶未填寫評價內容

618大采購，不剁手

物美價廉值得購買贊贊贊

物美價廉值得購買贊贊贊

物美價廉值得購買贊贊贊

此用戶未填寫評價內容