3.4.2 求解“韩信点兵”问题
相传西汉名将韩信的打仗水平了得，他带领千军万马攻无不克、战无不胜。汉高祖刘邦曾经问韩信：“你看我能指挥多少士兵？”韩信回答：“陛下能够率领十万兵马。”刘邦又问：“那你能带多少？”韩信答道：“臣多多益善。”意思是韩信认为自己能指挥很多兵马，越多越好。
韩信的自信不靠吹不靠蒙，而是在实战中锻炼出来的。话说韩信有次带兵遭遇楚军，好不容易打退了这股楚军，又来一队楚军前来增援，在此千钧一发之际，应当继续迎战还是撤退？这取决于我方还有多少人马，若兵力损耗较大，无疑走为上策。只见韩信立即命令士兵先后以三人一排、五人一排、七人一排地变换队形，每次变完队形，他瞄一眼队尾不足一排的士兵人数。几次队形变换之后，韩信已经知晓己方的剩余兵力，发现我军足堪一战，于是马上布好阵型，一举歼灭了新来的楚军。原来韩信是一位数学天才，在部队转换队形之时，他的脑海便建立了对应的方程式，迅速心算求出了士兵的数量。
“韩信点兵”的故事流传已久，可惜未有“韩信兵法”这样的兵书存世，导致如今无从考证韩信的数学造诣。后世的《孙子算经》倒是记载了类似的算术问题，题目是“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”，翻译成白话文便是：“现在有一个数字，除以三得到的余数是二，除以五得到的余数是三，除以七得到的余数是二，请问这个数字是多少？”该题不同于寻常的加减乘除方程式，因为它用到了取余数运算，而余数运算存在无数多个解，例如五除以三可得余数二，八、十一、十四等数字除以三也能得到余数二。既然取余数运算会找到多个解，那么如何快速找到“物不知数”问题的答案呢？
显然“物不知数”问题无法通过N元一次方程组求解，它实际上属于一元线性同余方程组，详细的方程组形式如图3-2所示。
图3-2 一元线性同余方程组
方程组里面的mod表示求余数运算，m1、m2、m3分别表示每次的除数3、5、7，而a1、a2、a3分别表示每次的余数2、3、2，至于x则为同余方程组的解。当每次的除数和余数都确定的时候，《孙子算经》给出了该问题的一种解法：除以三余二，则记个数字一百四十；除以五余三，则记个数字六十三；除以七余二，则记个数字三十；把三个记数相加得到二百三十三，再减去二百一十，最终得到二十三就是同余方程组的一个解。
可是这个解法太高深了，令人一时不明就里，后来南宋数学家秦九韶在著作《数书九章》中提出“大衍求一术”，对“物不知数”问题给出了完整的解答。当然，专业的“大衍求一术”不易为常人所理解，于是明朝数学家程大位将具体解法编成一首《孙子歌诀》，歌曰：
三人同行七十稀，五树梅花廿一支。
七子团圆正半月，除百零五使得知。
歌诀表达的算法是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，把前面3个乘积相加，再减去105的倍数，其结果便是同余方程组的最小解。由于中国数学家对同余方程组的解法贡献甚大，因此国际上将“物不知数”问题的求解算法称作“中国剩余定理”，国内则叫它“孙子定理”。
按《孙子歌诀》固然能够正确求解“物不知数”问题，可是歌诀提到的几个数字为什么是70、21、15、105呢？原来70是5跟7的最小公倍数35的两倍（此时除数为3），21是3跟7的最小公倍数（此时除数为5），15是3跟5的最小公倍数（此时除数为7），105是3、5、7三者的最小公倍数。那么疑问又来了，为什么第一个要用70而不用35，大家都取最小公倍数岂不更好？这是因为35除以3得到的余数是2，所以要给35乘以2得到70作为第一项乘法的系数；以此类推，21除以5得到的余数是1，21乘以1仍旧是21；同理，15除以7得到的余数是1，15乘以1仍旧是15。故而歌诀采用的3项乘数分别是70、21和15，最后减去105的倍数，相当于以105为除数做取余数运算。
然而“孙子定理”的解法实在奇妙，呆头呆脑的计算机程序不懂其中的奥妙，况且Java代码的运算符很有限，一时半会实现不了复杂的算法。好在如今的计算机跑得快，有时简单的解法反而更有效，就“物不知数”问题而言，它的整数解不会很大，在数字1000之内便可能找到多个解。那么通过穷举法对1到1000之间的整数逐个验证，检查是否满足“除三余二、除五余三、除七余二”的条件，只要某个整数符合这个校验条件，就表示它是“物不知数”问题的解。
鉴于穷举法很可能会找到该问题的多个解，因此需要引入数组变量来保存所有的整数解，据此可编写如下的算法代码（完整代码见本章源码的src\com\control\SunziDingli.java）：
// 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
int count=0; // 数组的容量计数
int[] numbers=new int[0]; // 符合条件的整数都放在这个数组
for (int i=1; i < 1000; i++) { // 查找1000以内所有符合要求的整数
if (i%3==2 && i%5==3 && i%7==2) { // 找到了一个满足条件的整数
count++; // 计数加1
numbers=Arrays.copyOf(numbers, count); // 数组容量增大一个
numbers[count-1]=i; // 往数组末尾填入刚才找到的整数
}
}
for (int number : numbers) { // 遍历并打印所有找到的整数解
System.out.println("符合孙子定理的整数number=" + number);
}
运行上述的“物不知数”问题求解代码，观察到以下的程序日志：
符合孙子定理的整数number=23
符合孙子定理的整数number=128
符合孙子定理的整数number=233
符合孙子定理的整数number=338
符合孙子定理的整数number=443
符合孙子定理的整数number=548
符合孙子定理的整数number=653
符合孙子定理的整数number=758
符合孙子定理的整数number=863
符合孙子定理的整数number=968
由日志可见，在1～1000之间一共找到了“物不知数”问题的10个解，其中最小的整数解即为《孙子算经》给出的答案23。