Java咖啡館——Java語言基礎（4）

　　其實，這道題目頗有淵源。

　　相傳，春秋戰國時，云夢山鬼谷洞中住了一個奇人名曰鬼谷子，精通天文、地理、兵法、算術，是兵家之府庫，縱橫家之鼻祖??孫臏、龐涓、蘇秦、張儀、毛遂等都是他的學生。鬼谷子稱自己的算術研究為鬼谷算，又叫隔墻算。這道題目便是鬼谷算中比較著名的題目之一，后現于《孫子算經》，又稱為韓信點兵、秦王暗點兵、剪管術、大衍求一術等等。

　　我國宋代學者對這類題目鉆研已頗為精深，總結出了“三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，去百零五便得知”這樣的口訣，意思是說“以三三數之，余數乘以七十;五五數之，余數乘以二十一;七七數之，余數乘十五。三者相加，如不大于一百零五，即為答數;否則須減去一百零五或其倍數。”這樣，很快就能知道答案為23。

　　不得不承認，跟上面的那些古人的方法相比，我們的程序雖然能夠比他們更快地得到23這個解，但是嚴格來講，我們的程序并不能算作是一個算法，不過是小學生級別的“暴力破解”而已。學習編程不能夠僅僅停留在這種程度，讓我們開動大腦，玩玩智慧游戲。

　　設這個數字是x，把題目寫成方程式就是這樣:

3a + 2 = x
5b + 3 = x
7c + 2 = x

　　你看，三個聯立方程四個變量，不定方程肯定有無窮答案，23只是100以內惟一的一個解。
心算快的朋友一下子就可以這樣得到答案:除以三和除以七都余二，則這個數字除以二十一必定也是余二，二十三除以二十一余二，而且二十三除以五恰好余三，問題解決了。不過，如果不是3、5、7等小數字，心算再快也不夠用啊。

　　其實，早在春秋年間，已經有了解題的算法，也就是西方數學家所謂的中國剩余定理(Chinese Remainder Theory)。具體的推理過程涉及太多抽象代數的知識，這里只寫出最后的通解公式:

x = 70 * 2 + 21 * 3 + 15 * 2 + 105 * n

　　當n=-2時，便得到x=23這個最小解。

　　Just do it

　　試試看把中國剩余定理的算法用Java編寫出程序，打印前1000個滿足題意的數字;然后用我們最初的算法打印前1000個滿足題意的程序(提示:只要改變for語句的終止判斷，到104918結束)，比較兩者之間的速度差別。

　　再擴展開去，中國剩余定理在符號計算中起著重要作用。比如我們都知道2/3，有理數是一種精確的表示。但用Java表示2/3就會變成0.6666667這樣的數值數，是不精確的表示。不過，符號計算會帶來巨大的復雜度，必須放到一個域中才能夠限制住難度，這就要用到中國剩余定理。老祖宗給我們留下豐厚的智慧遺產，有興趣的朋友可以看看計算代數這樣的課程，繼承并且發揚光大。

　　說了這么多看似無用的陽春白雪，東漸肯定又要給我衛生眼球看。實際上，我是想說明，學習Java編程和學習計算機科學有一個相通處，那就是我們追求的是優美算法，而計算機的高速只適合驗證，甚至有的問題，即使計算機速度增長得再快，也不及問題復雜度的增長速度，這就牽涉到計算復雜度的問題。從兩個程序的速度差別你就完全可以體會到。

　　好了，就此打住。金老先生看到他優美的武俠巨著在這里當做呆板的高等數學課程講解，一定痛心疾首找我打官司(求之不得啊，正好請他老人家簽名)。也罷，其實想不通道理也不必郁悶，畢竟這些東西弄得我一北大數學院在讀博士的哥們也頭疼腦熱得很。Java編程更偏向工科，以上的知識恐怕偌大一個Windows操作系統里面也只有安全部分用到了(Windows安全漏洞百出并非算法不好，而且程序沒有寫好哦)，所以Java愛好者能夠掌握Java的編程理念，通過嚴謹而優美的方法學打造工程奇觀，同樣雄偉得很。

四、小結

　　這回我們介紹了Java語言最最基礎的部分，限于篇幅，無法詳細展開，請讀者自行閱讀免費書籍Thinking in Java以及Java Tutorial里面的相關章節鞏固知識。如果想實踐，可以編寫一個求10000以內所有質數的小程序自我考察一下。

　　其實，金老先生的《射雕英雄傳》里面還有其他的數學謎題，有機會我們再介紹一些解法。
歡迎大家繼續到我的網志http://garychan.3322.org/進行交流。網志是一個共同學習的好方法，通過交流，互相取長補短，分享創新的思維，共同進步。如果你對《Java咖啡館》某篇文章有感觸想寫幾句，或者對今后連載的題材有什么要求，首先請注冊為網志用戶，然后就能夠登陸并且發言了。等待你的參與。