Java咖啡館——Java語言基礎(chǔ)（4）

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

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

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

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

　　設(shè)這個數(shù)字是x，把題目寫成方程式就是這樣:

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

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

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

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

　　當(dāng)n=-2時，便得到x=23這個最小解。

　　Just do it

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

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

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

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

四、小結(jié)

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

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