3.4.2　求解“韓信點兵”問題

相傳西漢名將韓信的打仗水平了得，他帶領(lǐng)千軍萬馬攻無不克、戰(zhàn)無不勝。漢高祖劉邦曾經(jīng)問韓信：“你看我能指揮多少士兵？”韓信回答：“陛下能夠率領(lǐng)十萬兵馬。”劉邦又問：“那你能帶多少？”韓信答道：“臣多多益善。”意思是韓信認(rèn)為自己能指揮很多兵馬，越多越好。

韓信的自信不靠吹不靠蒙，而是在實戰(zhàn)中鍛煉出來的。話說韓信有次帶兵遭遇楚軍，好不容易打退了這股楚軍，又來一隊楚軍前來增援，在此千鈞一發(fā)之際，應(yīng)當(dāng)繼續(xù)迎戰(zhàn)還是撤退？這取決于我方還有多少人馬，若兵力損耗較大，無疑走為上策。只見韓信立即命令士兵先后以三人一排、五人一排、七人一排地變換隊形，每次變完隊形，他瞄一眼隊尾不足一排的士兵人數(shù)。幾次隊形變換之后，韓信已經(jīng)知曉己方的剩余兵力，發(fā)現(xiàn)我軍足堪一戰(zhàn)，于是馬上布好陣型，一舉殲滅了新來的楚軍。原來韓信是一位數(shù)學(xué)天才，在部隊轉(zhuǎn)換隊形之時，他的腦海便建立了對應(yīng)的方程式，迅速心算求出了士兵的數(shù)量。

“韓信點兵”的故事流傳已久，可惜未有“韓信兵法”這樣的兵書存世，導(dǎo)致如今無從考證韓信的數(shù)學(xué)造詣。后世的《孫子算經(jīng)》倒是記載了類似的算術(shù)問題，題目是“有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問物幾何？”，翻譯成白話文便是：“現(xiàn)在有一個數(shù)字，除以三得到的余數(shù)是二，除以五得到的余數(shù)是三，除以七得到的余數(shù)是二，請問這個數(shù)字是多少？”該題不同于尋常的加減乘除方程式，因為它用到了取余數(shù)運算，而余數(shù)運算存在無數(shù)多個解，例如五除以三可得余數(shù)二，八、十一、十四等數(shù)字除以三也能得到余數(shù)二。既然取余數(shù)運算會找到多個解，那么如何快速找到“物不知數(shù)”問題的答案呢？

顯然“物不知數(shù)”問題無法通過N元一次方程組求解，它實際上屬于一元線性同余方程組，詳細(xì)的方程組形式如圖3-2所示。

圖3-2　一元線性同余方程組

方程組里面的mod表示求余數(shù)運算，m₁、m₂、m₃分別表示每次的除數(shù)3、5、7，而a₁、a₂、a₃分別表示每次的余數(shù)2、3、2，至于x則為同余方程組的解。當(dāng)每次的除數(shù)和余數(shù)都確定的時候，《孫子算經(jīng)》給出了該問題的一種解法：除以三余二，則記個數(shù)字一百四十；除以五余三，則記個數(shù)字六十三；除以七余二，則記個數(shù)字三十；把三個記數(shù)相加得到二百三十三，再減去二百一十，最終得到二十三就是同余方程組的一個解。

可是這個解法太高深了，令人一時不明就里，后來南宋數(shù)學(xué)家秦九韶在著作《數(shù)書九章》中提出“大衍求一術(shù)”，對“物不知數(shù)”問題給出了完整的解答。當(dāng)然，專業(yè)的“大衍求一術(shù)”不易為常人所理解，于是明朝數(shù)學(xué)家程大位將具體解法編成一首《孫子歌訣》，歌曰：

三人同行七十稀，五樹梅花廿一支。

七子團(tuán)圓正半月，除百零五使得知。

歌訣表達(dá)的算法是：將除以3得到的余數(shù)乘以70，將除以5得到的余數(shù)乘以21，將除以7得到的余數(shù)乘以15，把前面3個乘積相加，再減去105的倍數(shù)，其結(jié)果便是同余方程組的最小解。由于中國數(shù)學(xué)家對同余方程組的解法貢獻(xiàn)甚大，因此國際上將“物不知數(shù)”問題的求解算法稱作“中國剩余定理”，國內(nèi)則叫它“孫子定理”。

按《孫子歌訣》固然能夠正確求解“物不知數(shù)”問題，可是歌訣提到的幾個數(shù)字為什么是70、21、15、105呢？原來70是5跟7的最小公倍數(shù)35的兩倍（此時除數(shù)為3），21是3跟7的最小公倍數(shù)（此時除數(shù)為5），15是3跟5的最小公倍數(shù)（此時除數(shù)為7），105是3、5、7三者的最小公倍數(shù)。那么疑問又來了，為什么第一個要用70而不用35，大家都取最小公倍數(shù)豈不更好？這是因為35除以3得到的余數(shù)是2，所以要給35乘以2得到70作為第一項乘法的系數(shù)；以此類推，21除以5得到的余數(shù)是1，21乘以1仍舊是21；同理，15除以7得到的余數(shù)是1，15乘以1仍舊是15。故而歌訣采用的3項乘數(shù)分別是70、21和15，最后減去105的倍數(shù)，相當(dāng)于以105為除數(shù)做取余數(shù)運算。

然而“孫子定理”的解法實在奇妙，呆頭呆腦的計算機(jī)程序不懂其中的奧妙，況且Java代碼的運算符很有限，一時半會實現(xiàn)不了復(fù)雜的算法。好在如今的計算機(jī)跑得快，有時簡單的解法反而更有效，就“物不知數(shù)”問題而言，它的整數(shù)解不會很大，在數(shù)字1000之內(nèi)便可能找到多個解。那么通過窮舉法對1到1000之間的整數(shù)逐個驗證，檢查是否滿足“除三余二、除五余三、除七余二”的條件，只要某個整數(shù)符合這個校驗條件，就表示它是“物不知數(shù)”問題的解。

鑒于窮舉法很可能會找到該問題的多個解，因此需要引入數(shù)組變量來保存所有的整數(shù)解，據(jù)此可編寫如下的算法代碼（完整代碼見本章源碼的src\com\control\SunziDingli.java）：

        // 有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問物幾何？
        int count=0;  // 數(shù)組的容量計數(shù)
        int[] numbers=new int[0];  // 符合條件的整數(shù)都放在這個數(shù)組
        for (int i=1; i < 1000; i++) {  // 查找1000以內(nèi)所有符合要求的整數(shù)
            if (i%3==2 && i%5==3 && i%7==2) {  // 找到了一個滿足條件的整數(shù)
                count++;  // 計數(shù)加1
                numbers=Arrays.copyOf(numbers, count);  // 數(shù)組容量增大一個
                numbers[count-1]=i;  // 往數(shù)組末尾填入剛才找到的整數(shù)
            }
        }
        for (int number : numbers) {  // 遍歷并打印所有找到的整數(shù)解
            System.out.println("符合孫子定理的整數(shù)number=" + number);
        }

運行上述的“物不知數(shù)”問題求解代碼，觀察到以下的程序日志：

符合孫子定理的整數(shù)number=23

符合孫子定理的整數(shù)number=128

符合孫子定理的整數(shù)number=233

符合孫子定理的整數(shù)number=338

符合孫子定理的整數(shù)number=443

符合孫子定理的整數(shù)number=548

符合孫子定理的整數(shù)number=653

符合孫子定理的整數(shù)number=758

符合孫子定理的整數(shù)number=863

符合孫子定理的整數(shù)number=968

由日志可見，在1～1000之間一共找到了“物不知數(shù)”問題的10個解，其中最小的整數(shù)解即為《孫子算經(jīng)》給出的答案23。