“中國剩余定理”算法解析

經全國中小學教材審定委員會2004年初審通過普通高中課程標準實驗教科書《數(shù)學》(北師大版)第三冊的“概率與統(tǒng)計”部分加進了“第二章，算法初步”內容。其中初步地教授學生，用計算機的程序化語言設計，來解決數(shù)學問題。

在中國的漫長的歷史中，數(shù)學已有許多重要的發(fā)展。我國古代的數(shù)學家們，在數(shù)學的很多問題及其解法，早已居世界領先地位。如《孫子算經》中提到的“物不知其數(shù)”問題的解法，即是解決數(shù)學剩余問題的較早的記錄，這便是“中國剩余定理”的雛形。如此類的古代數(shù)學問題的解法，用當今信息化技術，有了更為先進的手段。如今飛速發(fā)展的高科技高信息技術，把我們的社會推到了數(shù)學技術的新時代。而高技術的關鍵是軟件，軟件的核心是數(shù)學方法、數(shù)學技術。當前教育形式由此提出了更高更新的要求，要將信息化技術融入到數(shù)學教學中去，從而使數(shù)學成為更快捷、更方便、更體現(xiàn)其科學性、實用性與價值的一門基礎學科。

在新教材中，涉及的算法，即是將信息化技術與數(shù)學解法相結合，將高新技術運用于數(shù)學，打破數(shù)學解法的傳統(tǒng)形式，展示數(shù)學在當前信息化時代下，方法與理念的優(yōu)化與創(chuàng)新。

一、算法

算法是為求解問題而設計的方法。對問題的任意一個實例，算法都應該能求出其相應的解來。算法不是公式，也不是運算法則，而是解決問題的方法。而算法的思想是:為解決問題而設計的一系列計算機程序化的語言步驟。

在算法的運用過程中，按照一定的計算機語言邏輯法則，設計出一套適用數(shù)學特定問題的計算機程序語言，使此數(shù)學問題具有量身定作的一套計算機程序運算平臺，從而套用此平臺，解決更多更復雜的與此數(shù)學問題同類的數(shù)學難題。

1.算法與BASIC語言

算法可以用自然語言和框圖來描述，在計算機上，《數(shù)學》(北師大版)中，基本以BASIC語言為主要計算機語言，使算法在計算機上實現(xiàn)。

2.算法的表述

標準的BASIC語句只有17種。下面通過一簡單實例，用條件語句來求解一道數(shù)學中的分段函數(shù)的求值問題。展示BASIC程序對于此類問題的設計框架。下面用一個簡例分別闡述算法的三種表述方式:自然語言表述、框圖表述及BASIC語言表述。

【例】根據(jù)輸入x的值，計算y的值。

y=x+1，x≤2.5;x-1，x>2.5.

分析理解:這是一個分段函數(shù)的求值問題。計算之前，應對自變量進行判斷，自然語言描述可以表述為:

(1)輸入x;(2)如果x≤2.5，則y=x+1;(3)如果x>2.5，則y=x-1;(4)輸出y.

用算法的條件語句表述上述(2)、(3)為:

If x≤2.5 Then

y=x+1

Else

y=x-1

End If

用框圖來描述條件語句的一般性，如下圖:

以上框圖所表示的條件算法語句的格式，都可以寫成:

If條件Then

語句1

Else

語句2

End If

那么凡是符合條件算法語句的數(shù)學問題，都可套用上述語句，在計算機上實現(xiàn)快速運算。

二、“中國剩余定理”

我國的數(shù)學文化歷史悠久。我們的祖先從上古末開化時代開始，經過許多世代，通過大量的生產實踐和生活實際的研究，創(chuàng)造了許多寶貴的數(shù)量文獻。《孫子算經》(大約公元四世紀、晉朝時期成書)中的“物不知其數(shù)”問題的解法是中國數(shù)學領先于世界的一個典型例子。它便是最早的“中國剩余定理”。

1.《孫子算經》，最早的“中國剩余定理”

“物不知其數(shù)”問題:今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何?答曰:二十三。書中問題的奇妙解法是:三三數(shù)之剩二，置一百四十;五五數(shù)之剩三，置六十三;七七數(shù)之剩二，置三十。并之得二百三十三，以二百一十減之即得二十三。

該算法用口訣表達是:“三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得知。”意思是:每3個一數(shù)最后剩1個就取5和7的公倍數(shù)70，那么“三三數(shù)之剩二個”，就取二倍個70得140;每5個一數(shù)最后剩1個就取3和7的公倍數(shù)21，那么“五五數(shù)之剩三個”，就取三倍個21得63;每7個一數(shù)最后剩1個就取3和5的公倍數(shù)15，那么“七七數(shù)之剩二個”，就取二倍個15得30。最后把140，63，30三數(shù)相加的和再減去3、5、7的公倍數(shù)105×2，即得符合條件的最小數(shù)為23。于是就有:70×2+21×3+15×2-105×2=23。

這便是最早的“中國剩余定理”的內容，它是用常用語言來表述“物不知其數(shù)”問題的解法。

2.“中國剩余定理”的由來

“中國剩余定理“名稱本來并不存在。在定理本身出現(xiàn)數(shù)千年后，德國數(shù)學家高斯(1777～1855)通過獨立研究，于公元1801年出版的《算術探究》上發(fā)表了著名的高斯定理。公元1852年，英國基督教士偉烈亞力(1815～1827)將《孫子算經》中的“物不知其數(shù)”問題的解法傳到歐洲。公元1874年，馬蒂生指出:孫子的解法完全符合高斯的定理。而此時，高斯定理已比《孫子算經》中的“物不知其數(shù)”問題的解法晚一千五百多年。從此，在西文的數(shù)學史上將“物不知其數(shù)”問題稱為“中國剩余定理”或“孫子定理”。“中國剩余定理”由此得名。

3.“中國剩余定理”的方程解法

這道在《孫子算經》中所講的“物不知其數(shù)”問題，在人教版的中師《代數(shù)與初等函數(shù)》第二冊，用不定方程來解:

設N被3、5、7除所得的整數(shù)商分別為x、y、z依題意得3x+2=5y+3=7z+2=N于是有3x-5y=15y-7z=-1，解方程組，得通解式為x=7-35ty=4-21tz=3-15t(t∈z)。三式中任意一個代入得“物不知其數(shù)”問題的通解N=23-105t，當t=0時，N=23是最小的正整數(shù)解。

三、“中國剩余定理”與算法

由此可見，列方程解如“中國剩余定理”這樣古老的數(shù)學問題，是現(xiàn)代數(shù)學教學中的傳統(tǒng)解法，亦是相對較繁復的解法。任何一個做數(shù)學題的人，在審題后，若無特定運算方法的情況下，都會如此這般采取列方程組的方式解題。而在算法語言中，通過計算機程序語言的編程設計，如此繁復的解題過程可以簡化成若干行固定簡明的數(shù)字符號。以最大的效率，解決數(shù)學問題。

“中國剩余定理”的又一典型例子，即“韓信點兵”問題:

“有兵一隊，若列成三行縱隊，則末行多兩人;成五行縱隊，則末行多三人;成七行縱隊，則末行多四人。求兵數(shù)。”

即是說:有一個數(shù)被3除余2，被5除余3，被7除余4;求這個數(shù)的最小值。

這里有3個條件，為了使最小值盡快找到，所以我們從最后一個條件，用自然語言開始設計一個最佳算法。

1.首先確定最小的除以7余4的正整數(shù):4;

2.依次加7就得到所有除以7余4的正整數(shù):

4，11，18，25，32，39，46，53，60，……

3.在第二步得到的一列數(shù)中確定最小的除以5余3的正整數(shù):18;

4.然后依次加上35，得到

18，53，88，……

5.在第四步得到的一列數(shù)中找出最小的滿足除以3余2的正整數(shù):53.

這便是與計算機語言相對應的自然語言的表述形式。

四、展望

普通高中課程標準實驗教科書《數(shù)學》(北師大版)中出現(xiàn)的算法，僅僅是用計算機來解決數(shù)學問題的一個開始。計算機本身就是數(shù)學與電子技術結合的產物，它的出現(xiàn)與應用，對數(shù)學的發(fā)展產生了巨大的影響，并為數(shù)學的應用開辟了極廣闊的天地。隨著信息時代，高科技發(fā)展的日新月異，將計算機程序語言代入到數(shù)學教學中去，是人類社會文明發(fā)展的必然，對全民素養(yǎng)的提升具有不可限量的作用。算法既重視“算則”，更重視“算理”。算法由此而必然具有發(fā)展的廣闊空間。

參考文獻

[1] 錢寶琮.中國數(shù)學史(第1版).北京:科學出版社?熏1964.

[2] 嚴士健，王尚志.數(shù)學(第5版).北京:北京師范大學出版社，2008.

(責任編輯楊子)