這是多年以前做的一道題目，原題來自軟件報或者電腦報?，我記不清了。解決這個題目有一個關鍵的步驟，就是要求一個整數在一個整數三角陣中的坐標。這篇blog就是討論這個求坐標的問題，不是討論那個報紙上的題目。現在將題目描述如下：

三角陣如下所示：

?????????????????????????? 1?????????????????????????

????????????????????? 2???????? 3???????????????????????????????????????????

?????????????????4???????? 5???????? 6???

??????????? 7??????? 8???????? 9??????? 10

??? 11?????? 12???????13?????? 14????????15

??????????????????????? ... ... ...

n???? n+1??? n+2???????????? ... ...???????????????n+k

三角陣中的每一個數字都有一個坐標對應，其中行是X軸，從右上往左下傾斜的邊是Y軸。比如：2的坐標是（2，1），9的坐標是（4，3），應該很容易理解吧。下面還是從最簡單的解法開始討論。先看X軸坐標的求法。我們需要逐步的減去整數的個數，第一次減去第一行的整數個數，第二次減去第2行的整數的個數，如此重復知道給定的整數不夠減而成為負數為止。這時將循環中當前使用的行數就是X軸的坐標，而不夠減的數值就是Y軸的坐標。現在的問題就是怎么個減法效率才能盡可能的高，因為給定的整數可能非常的大，這里考慮理想情況，不要考慮具體一個語言的對整數溢出的限制，否則討論算法的效率就沒有意義了。

第一個方法是寫一個第一項為1，公差為1的等差數列的求和函數，參數為n，返回值是前n項的和。然后開始從1循環，將返回值和給定整數比較，從而求得坐標。這個當然是最差的做法，效率幾乎是最低的。如果誰在我的項目中這樣寫代碼，那么這個月的工資會打折扣的。至少我們給出的解法應該是這樣的：不能用一個求和函數來做，而是應該利用循環，從前n項的和遞推出前n+1項的和，循環中應該有類似如下的遞推求和代碼：

??????????nCount = nCount + 1;?nSum = nSum + nCount;

由于整個計算過程使用加減完成，并且不存在回溯的情況，雖然整數有可能會很大，但是這個解法的效率應該是不會太差的，這個非常顯然。因為大O時間復雜度中最高的指數為1，效率是很高的了。所以這算是一個解法，如此寫代碼的話至少滿足使用要求，不扣工資了。

但是這個解法有一個問題，就是太過簡單。當然在很多時候簡單是一個非常好的特點，但是在這里不行，簡單的讓人覺得簡陋了。思考片刻后，我得到了又一個更好的解法。那就是在循環遞推前n項的和的時候，循環遞增的步長不設置為固定的1，而是可變長的，比如2的整數倍，也就是每次循環遞增一倍。這樣通過若干次循環后，我們可以發現給定的整數會落在前一次循環（假設此時nCount等于n）所求和，和本次循環（假設此時nCount等于2n）所求和的范圍之內。即便是對于一個很大的整數，由于循環的步長是2的幾何數量級的增長，所以可以很快的找到這個范圍。那么找到了這個范圍之后又如何呢？我們可以在腦海中假設一個數組，這個數組是這個等差數列的前n項和的數組。第一個元素是前一項的和，第二個元素是前兩項的和，如此，第n個元素就是前n項的和。那么我們知道了給定整數所落在的范圍，于是我們就可以使用折半查找的辦法來獲得X軸坐標。但是需要注意的是，這個前n項和的數組不是寫死的，需要在使用的時候動態計算出第n個元素的值。顯然從算法的角度看這個解法的效率遠比前面那個高。我一度為這個解法得意，但是在得意的同時又感到一點遺憾，就是感覺自己不是用算法解決的效率問題，而是用編程技巧解決的問題。我隱隱的感覺似乎還有一個完美的解隱藏著。

于是繼續思考，沒多久我終于找到了這個完美的解，找到了一個時間復雜度與給定整數大小幾乎沒有關系的算法。等差數列的求和公式是這樣的：S = n(n+1)/2。以前的思路都是從n求得S，然后做減法再接著判斷處理，在一個靈感的幫助下，我發現可以把給定的整數看做S，通過求和公式直接求得n。這時n的整數部分就是X坐標，然后減去X坐標值所表示的前若干項的和，就可以得到Y軸的坐標。

從結果看這是最好的算法，它的最優幾乎可以被證明。那么如此利用了求和公式而得到的解法能不能算是一個算法呢？當時我認為是，但是由于所用知識過于簡單，我不能肯定。直到2年后我自學了一本書，名字叫組合數學，其中有一章講到了母函數。這時我才明白，我在不自覺地情況下使用了母函數的思路解決了問題。只是這個求和公式比較簡單不需要求解特征方程等等相關的東西，所以我才作了出來。至此，我的疑問得到了解答，這是一個堂堂正正的算法。

總結

以上是生活随笔為你收集整理的一道解决的非常漂亮的算法题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。