ACMer程式員智力拾遺

       浏覽網頁偶得，遂記錄下來，每天進步一點點……

       部落格園真是個不錯的平台，今天我讓師姐也注冊了……

       學會分享吧，孩子們……

一、程式設計中無窮大量的設定

       如果問題中各資料的範圍明确，那麼無窮大的設定不是問題，在不明确的情況下，很多程式員都取0x7fffffff作為無窮大，因為這是32-bit int的最大值。如果這個無窮大隻用于一般的比較（比如求最小值時min變量的初值），那麼0x7fffffff确實是一個完美的選擇，但是在更多的情況下，0x7fffffff并不是一個好的選擇。

很多時候我們并不隻是單純拿無窮大來作比較，而是會運算後再做比較，例如在大部分最短路徑算法中都會使用的松弛操作：if (d[u]+w[u][v]<d[v]) d[v]=d[u]+w[u][v]; 我們知道如果u,v之間沒有邊，那麼w[u][v]=INF，如果我們的INF取0x7fffffff，那麼d[u]+w[u][v]會溢出而變成負數，我們的松弛操作便出錯了，更一般的說，0x7fffffff不能滿足“無窮大加一個有窮的數依然是無窮大”，它變成了一個很小的負數。

除了要滿足加上一個常數依然是無窮大之外，我們的常量還應該滿足“無窮大加無窮大依然是無窮大”，至少兩個無窮大相加不應該出現災難性的錯誤，這一點上0x7fffffff依然不能滿足我們。

       是以我們需要一個更好的家夥來頂替0x7fffffff，最嚴謹的辦法當然是對無窮大進行特别處理而不是找一個很大很大的常量來代替它（或者說模拟它），但是這樣會讓我們的程式設計過程變得很麻煩。在我讀過的代碼中，最精巧的無窮大常量取值是0x3f3f3f3f，我不知道是誰最先開始使用這個精妙的常量來做無窮大，不過我的确以前見到過南陽理工的同學用過，當時沒注意，今天再次看到，于是我自己也嘗試了一下，發現非常好用，而當我對這個常量做更深入的分析時，就發現它真的是非常精巧了。

0x3f3f3f3f的十進制是1061109567，也就是10^9級别的（和0x7fffffff一個數量級），而一般場合下的資料都是小于10^9的，是以它可以作為無窮大使用而不緻出現資料大于無窮大的情形。另一方面，由于一般的資料都不會大于10^9，是以當我們把無窮大加上一個資料時，它并不會溢出（這就滿足了“無窮大加一個有窮的數依然是無窮大”），事實上0x3f3f3f3f+0x3f3f3f3f=2122219134，這非常大但卻沒有超過32-bit int的表示範圍，是以0x3f3f3f3f還滿足了我們“無窮大加無窮大還是無窮大”的需求。

最後，0x3f3f3f3f還能給我們帶來一個意想不到的額外好處：如果我們想要将某個數組清零，我們通常會使用memset(a,0,sizeof(a))這樣的代碼來實作（友善而高效），但是當我們想将某個數組全部指派為無窮大時（例如解決圖論問題時鄰接矩陣的初始化），就不能使用memset函數而得自己寫循環了（寫這些不重要的代碼真的很痛苦），我們知道這是因為memset是按位元組操作的，它能夠對數組清零是因為0的每個位元組都是0，現在好了，如果我們将無窮大設為0x3f3f3f3f，那麼奇迹就發生了，0x3f3f3f3f的每個位元組都是0x3f！是以要把一段記憶體全部置為無窮大，我們隻需memset(a,0x3f,sizeof(a))。是以在通常的場合下，0x3f3f3f3f真的是一個非常棒的選擇。

二、全排列被8整除

       給定一個非負整數，問能否重排它的全部數字，使得重排後的數能被8整除。 輸入格式： 多組資料，每組資料是一個非負整數。非負整數的位數不超過10000位。 輸出格式 每組資料輸出一行,YES或者NO，表示能否重排它的全部數字得到能被8整除的數。注意： 重排可以讓0開頭。

       全排序方法在我之後審題中被抛棄了，因為這道題不能夠用全排序，裡面有個條件很苛刻。全排序方法在我之後審題中被抛棄了，因為這道題不能夠用全排序，裡面有個條件很苛刻。其實，這道題使用歸納法比較好，為什麼？題目有提示 非負整數的位數不超過10000位 ，這意味着什麼呢？非負整數的長度可能達到9999位，如果這麼大的數使用全排序，估計計算機要死了，更何況我家自用開發機是8年前的老古董，想的出這種馊主意，它肯定受不了了。是以要借助歸納法，為什麼可以用歸納法？呵呵，我猜的，别笑，我說得是實話，我猜測它可以使用歸納法，那麼就得找出它遵循什麼規律了，下面開始做一些假設過程：

三、結束語

       碰到問題，想都不想的去做，結果隻有一種，徒勞無功，倒不如什麼都不做。這道題我開始也是全排序，因為胸有成竹嘛，但是後來仔細看題後，發現問題不是那麼回事，有一個可能很難達到的要求，就是位數達到9999位怎麼計算？是以，最後我認真的分析了一下發現它似曾相識。呵呵。

       感謝大神的貢獻，我要站在巨人的肩膀上，不過現在隻能站在老王肩膀上了，嘻嘻……