算法中的數學經典問題

陸習曉

在數學的發展史上，很多經典的數學問題被人們所傳承.算法，是計算科學的重要組成部分，那么我們能否設計出一些合適的算法，用現代的科學技術幫我們解決這些經典的數學問題呢？下面給出幾例，予以展示，供大家參考.

1自守數

人的相貌可以遺傳，同樣數字也可以遺傳.例如：52=25，252=625，在這兩個等式中：5和它的平方25，最后一位數字一模一樣，25和它的平方625，最后兩位數字一模一樣，當然它們遺傳的都是“尾巴”，有沒有位數更多的遺傳現象呢？下面這串等式提供了三位、四位、五位和六位遺傳現象的例子：

6252=390625，06252=390625， 906252=8212890625，8906252=793212890625，

嚴格說來，0625不能算是四位數，只能看成四位密碼鎖上的一個號碼，但是它的平方確實把這四位號碼完全保留在平方數的尾部，況且，把0625也算在里面還有一個好處，就是保持了變化的連續性：上面這些等式左邊的數，按照位數從少到多，順次是5，25，625，0625，90625，890625.這是一個在平方運算下具有數字遺傳特性的家族，從這一列數中的每個數要得到它后面相鄰的數，只需在原數前面加上一個適當的數字；反過來，要得到這列數中某個數前面相鄰的數，只需劃去原數最前面一位的數字，只要記下這列數中有一個數是890625，把它的數字從前往后順次一個一個地劃掉，就得到前面幾個數了.

下面是另外一組有遺傳特性的數：62=36，762=5776，3762=141376，…，這些有遺傳特性的數我們稱它為自守數；如果一個數的平方的尾數等于該數，那么就稱這個數為自守數（automorphic number）.顯然5和6是一位自守數，25×25=625 ，76×76=5776，25和76是兩位自守數.

自守數有一個特性，以他為后幾位的兩個數相乘，乘積的后幾位仍是這個自守數.雖然0和1的平方的個位數仍然是0和1，但是他們太“平凡”了，研究他們沒有意義，所以不算自守數.三位自守數是625和376，四位自守數是0625和9376，五位自守數是90625和09376，……，我們可以看到，（n+1）位的自守數出自n位的自守數.由此得出，如果知道n位的自守數a，那么（n+1）位的自守數應當由a前面加上一個數構成.實際上，簡化一下，還能發現如下規律：5+6=11；25+76=101；625+376=1001；……，所以，兩個n位自守數，他們的和等于10n+1.如何設計一個算法，找出尾數取到三位的所有的自守數呢？

2兔子數列

一般而言，兔子在出生兩個月后，就有繁殖能力，一對兔子每個月能生出一對小兔子來.如果所有兔子都不死，那么一年以后可以繁殖多少對兔子？我們不妨拿新出生的一對小兔子分析一下：

第一個月小兔子沒有繁殖能力，所以還是一對；

兩個月后，生下一對小兔總數共有兩對；

三個月以后，老兔子又生下一對，因為小兔子還沒有繁殖能力，所以一共是三對；……；

依次類推可以列出下表：

表中數字：1，1，2，3，5，8，13，21，34，……，構成了一個數列，這個數列有十分明顯的特點：前面相鄰兩項之和，構成了后一項，這個數列是意大利中世紀數學家斐波那契在《算盤書》中提出的，即斐波那契數列，意大利數學家列昂納多·斐波那契（Leonardo Fibonacci，生于公元1170年，卒于1240年，籍貫大概是比薩），被人稱作“比薩的列昂納多”，他是第一個研究了印度和阿拉伯數學理論的歐洲人，他的父親被比薩的一家商業團體聘任為外交領事，派駐地點相當于今日的阿爾及利亞地區，列昂納多因此得以在一個阿拉伯老師的指導下研究數學，他還曾在埃及、敘利亞、希臘、西西里和普羅旺斯研究數學.

該數列有很多奇妙的屬性，下列這些花，它們的花瓣的數目就是斐波那契數：延齡草、野玫瑰、南美血根草、大波斯菊、金鳳花、耬斗菜、百合花、蝴蝶花；這個數列中相鄰兩項的比值交錯地大于或小于黃金比的值；它的第n項同時也代表了集合{1，2，…，n}中所有不包含相鄰正整數子集的個數.

2.1算法設計思想

根據題意可知，第一個月有 1 對小兔，第二個月有 1 對成年兔子，第三個月有兩對兔子，從第三個月開始，每個月的兔子對數是前面兩個月兔子對數的和.設第N個月有F對兔子，第N-1個月有S對兔子，第N-2個月有Q對兔子，則有F=S+Q.一個月后，即第 N+1個月時，式中變量 S 的新值應變第 N 個月兔子的對數（F 的舊值），變量 Q 的新值應變為第 N-1 個月兔子的對數（S 的舊值），這樣，用 S+Q 求出變量 F 的新值就是 N+1 個月兔子的對數，依此類推，可以得到一個數序列，數序列的第 12 項就是年底應有兔子對數，我們可以先確定前兩個月的兔子對數均為 1，以此為基準，構造一個循環程序，讓表示“第×個月的 I 從 3 逐次增加 1，一直變化到 12，最后一次循環得到的 F”就是所求結果.

2.2流程圖與偽代碼

我們只要改變一下算法中的輸出條件就可以得到二年后，三年后，……，n年后繁殖的兔子的對數.

猴子吃桃

猴子第一天摘下若干個桃子，當即吃了一半，還不過癮，又多吃了一個.第二天早上又將剩下的桃子吃掉一半，又多吃了一個，以后每天早上都吃前一天剩下的一半加一個，到第10天早上想吃時，見只剩一個桃子了.求第一天共摘了多少桃子？

3.1算法設計思想

采取逆向思考的方法，從后往前推斷.根據題意可知，第10天只剩一個桃子，第9天剩（1+1）*2=4個桃子，第8天剩（4+1）*2=10個桃子，以此類推，從第9天開始，每天的桃子數是后面一天的桃子數與1的和的2倍.設第 I天有桃子數為S個，則第I-1天有桃子數為（S+1）*2個.

3.2流程圖與偽代碼

采用這種逆向思考的方法，我們只需改變I的初始條件，就可實現對猴子吃桃問題的一般層面上的求解.

通過以上幾例數學經典問題的算法解決，使我們認識到利用算法機械統一的特征優勢，可以使這些數學經典問題從一般層面上獲得求解，而不再需要對同類型的問題分別思考求解.也使我們充分感悟到在數學學科中靈活與機械、經典與現代的辯證統一.