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咖啡馆》某篇文章有感触想写几句，或者对今后连载的题材有什么要求，首先请注册为网志用户，然后就能够登陆并且发言了。等待你的参与。