Java咖啡馆(5)——Java语言基础

一、黄蓉难倒瑛姑的数学题

　　看过《射雕英雄传》的朋友，一定被黄蓉的机灵鬼怪、冰雪聪明深深打动。比如黄蓉遇上神算子瑛姑，给她出的三道题目中有一题是这样的:今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？也就是说，有一个未知数，这个数除以三余二，除以五余三，除以七余二，问这个数是多少？在一部武侠巨著中巧妙嵌入中国古代数学精粹，金老先生果真才高八斗啊！

　　小提示

　　快去尝鲜Eclipse 3 Release

　　经过几近吊胃口的n长时间的测试迭代，Eclipse.org终于按时放出正式版，对于Java爱好者而言，不谛是夏日的盛大礼物。

　　Eclipse 3的新功能非常多，增加了许多体贴的细节功能。赶快阅读Eclipse 3.0 New and Noteworthy:http://download.eclipse.org/downloads/drops/R-3.0-200406251208/eclipse-news-R3.html，亲自品味一下这个新版本！

二、Java v.s. 神算子

　　可惜宋朝没有Java，否则英姑一定不会被黄蓉难倒。

　　打开Eclipse，新建一个Java项目，名称叫做“黄蓉的题目”。然后新建一个Java类，名字叫做JavaCalc，记得在“public static void main(String[] args)”选项前打上勾。按照图1所示输入Java程序，共五行代码(图1)。

　　运行程序，你就会得到如图2所示结果(图2)。

　　通过验算，23果然就是满足题意的一个解。程序编写的具体操作步骤不再赘述了，如果你还不熟悉，赶快翻翻前几期的《Java咖啡馆》好好复习一下吧！

　　短短五行程序就解决号称神算子英姑挠破头皮都没想出来的问题，是不是很神奇呢？其实，这些代码包含了许多Java语言特性，比如变量、操作符、流程控制语句。或许这些代码对你而言还有些神秘，结合这道题，再看看下面的介绍，马上就会领悟到其中奥妙。

　　1.变量(variable)

　　变量是用标识符表示的(拥有名字)用来存储值(拥有内涵)的物体。代码:

int X;

　　就是一个变量声明语句，宣告X是一个int类型的变量。

　　为了声明一个变量，你必须明确提供这个变量的类型和名称。

　　变量的类型是用来确定变量可以存储的数据类型和可以对该变量进行的操作。比如上面代码中，X是int类型，即一个整数，只能够把整数赋给这个变量，比如X＝0。你也只能对X进行算术运算，比如加、减、乘、除以及取余数等。

　　Java的变量分为“原始类型(primitive type)”及“引用类型(reference type)”两大类。其中“原始类型”的变量保存的是拥有特定大小和类型的简单数据，比如一个整数、一个字符、一个布尔值(以逻辑学家Geogre Boole命名的变量类型，只有两种值——真或假，属于经典的二值逻辑)等。与“原始类型”不同，“引用类型”是一个参照的概念，指向内存中某个具体对象(的地址)(见图3)(图3＋4  左侧为“原始类型”，右侧为“引用类型”，通过对比，我们可以看到它们的不同)。

　　我们现在接触“原始类型”比较多，足够完成复杂任务。“引用类型”在面向对象概念中起了重要作用。

　　为什么Java语言中要这么分两种变量类型呢？这是出于对执行效率的考虑。“引用类型”服务于对象，是面向对象的基础设施，用面向对象的方法构架和设计系统很漂亮，但是“引用类型”的执行效率远不及“原始类型”。从而，Java实际上是“原始类型”和“引用类型”结合使用的计算机语言，从这点上讲，Java并非纯粹的面向对象语言。当然，Java提供了与int类型(原始类型)遥相呼应的Java类——Integer类型(引用类型)，它们可以互相转换，新版本的Java还提供了自动转换的功能，这是后话了，暂且不提。

　　Java的原始类型列举如下：

　　值得一提的是，Java语言明确规定了变量类型的大小，为跨平台铺平道路。

　　变量名就是变量的名字，你是通过变量名访问实际变量的，所以变量名有严格的规定。在Java中，变量名必须是:

　　★标识符，即符号开头的字符串。
　　★不能是关键字、布尔值(true或者false)以及保留字null。
　　★在作用域内惟一，即一个作用域内变量名必须惟一。

　　看起来规矩很多，其实也很合理。比如给小孩起名字，总是以百家姓作为姓氏，如果名字叫做“￥皓”，别人一定认为是开玩笑或者是奇怪的网名。当然，小孩的名字也不能叫做“总统”、“皇帝”之类的关键词，以免引起误会。说到作用域惟一，也很好理解:中国叫做吴宗宪的人太多了，学校里(一个作用域)会用学号惟一标识你的身份，而不会逼迫你改名为吴宗宪2004等。

　　虽然合法的都能够成为变量名，但给变量起一个有意义的名字，是一个良好的素质，免得阅读代码时，别人看不懂，自己也看不懂。举个例子，给变量起变量名正如起暗号，最好不要起“打死我也不说”这样的暗号，不然，有你好受的……

　　最后说说作用域。作用域是指变量在程序内部能够被访问到的区域。比如我们的程序中，变量X在整个main方法中都能够被访问到，非常直观。你可以借助Eclipse的力量体验一下这个概念:如果作用域不对，Eclipse会毫不犹豫地警告你。

　　定义了变量就能够通过“=”给它赋值，正如程序中所做的。

　　2.运算符

　　运算符用来进行函数运算。Java中的运算符可以分为算术运算符、关系运算符、条件运算符、位移与逻辑运算符、赋值运算符以及其他一些运算符组成。

　　下面，用“(X % 3 == 2) && (X % 5 == 3) && (X % 7 == 2)”来理解Java运算符的概念。

　　刚才已经说过了，“X”是一个变量，“%”是取模的算术运算符，“X % 3”即X模3，就是X除以3的余数;“==”是关系运算符，当“==”两边相等时返回true，否则就是false。从而，“X % 3 == 2”的意思就很明白了——如果X除以3的余数是2，则这个表达式的值就是true，否则为false。一对“()”是用来表示运算的优先级，即括号里面的表达式首先被计算，然后才是括号外的。“&&”读作and，是条件运算符，是逻辑运算里面的合取，即当且仅当“&&”两边都是true的时候，表达式为true，否则为false。现在回过头看上面这个表达式的意思就是:X除以3余2并且X除以5余3并且X除以7余2，表达式的结果显然是一个布尔值，不是true就是false。

　　3.流程控制

　　程序是以文件形式保存在磁盘上的。如果没有流程控制，Java解释器将从顶向下、从左到右执行语句。而用流程控制语句，你可以选择性地执行部分语句，重复执行一些语句，或者改变语句的顺序流程，从而完成千变万化的工作。

　　首先介绍if流程控制语句。if语句允许你选择性地执行某些语句，跟“如果怎样则如此这般”的意思一样。比如，我们的程序是这样写的:

if ((X % 3 == 2) && (X % 5 == 3) && (X % 7 == 2)) { 
   System.out.print("这个数字是:"); 
   System.out.print(X);
}

　　联系上面关于运算符的知识，很明显，这句话的意思是:如果“X除以3余2并且X除以5余3并且X除以7余2”，则“把这个数字打印出来”，是不是跟日常生活的语法非常接近？

　　下面看看外层的for流程控制语句。for语句是循环语句，用来遍历一段数值。基本语法形式如下:

for (初始化; 终止判断; 增量) {
    执行语句
}

　　在循环执行前，初始化部分将首先被执行。比如我们的代码中，初始化语句是:X = 0，表示把0赋给变量X，即从0开始测试是否满足题意。之后，执行语句将被调用，即上面的if语句——若当前的X(这时是0)满足题意便打印出来。然后，增量语句将被执行，即X++，意思是把X的值增加1，即我们要尝试1是否满足题意的解。最后，终止判断语句将被执行，这里是“X < 100”，表示若X小于100则重复以上步骤，否则停止循环，执行后面的代码。

　　可以看到，控制整个循环的主要部分是增量和终止判断，没有增量的变化，就无法达到依次尝试0到99这些数字是否满足题意;如果没有终止判断，循环就无法停止，可能进入所谓的死循环甚至死机——吓唬你的，有Eclipse在，即使写出造成死循环的豆腐渣代码，按下Eclipse中的停止按钮，照样安然无事。可惜我们的防汛工作却没有这样的救命按钮，必须脚踏实地，来不得半点马虎。
OK，现在真相已经大白了！我们的Java代码不过是从0到99依次尝试，看看是否“三三数之剩二，五五数之剩三，七七数之剩二”，如果是则把该数字打印出来。借助电脑几近暴力的速度，从而在短短1秒内解开黄蓉的谜题！黄老邪估计也不得不悄悄地低头买下有《Java咖啡馆》连载的《电脑爱好者》杂志闭门修炼大脑，哈哈哈……

三、阳春白雪

　　其实，这道题目颇有渊源。

　　相传，春秋战国时，云梦山鬼谷洞中住了一个奇人名曰鬼谷子，精通天文、地理、兵法、算术，是兵家之府库，纵横家之鼻祖——孙膑、庞涓、苏秦、张仪、毛遂等都是他的学生。鬼谷子称自己的算术研究为鬼谷算，又叫隔墙算。这道题目便是鬼谷算中比较著名的题目之一，后现于《孙子算经》，又称为韩信点兵、秦王暗点兵、剪管术、大衍求一术等等。

　　我国宋代学者对这类题目钻研已颇为精深，总结出了“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，去百零五便得知”这样的口诀，意思是说“以三三数之，余数乘以七十;五五数之，余数乘以二十一;七七数之，余数乘十五。三者相加，如不大于一百零五，即为答数;否则须减去一百零五或其倍数。”这样，很快就能知道答案为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咖啡馆》某篇文章有感触想写几句，或者对今后连载的题材有什么要求，首先请注册为网志用户，然后就能够登陆并且发言了。等待你的参与。