2019獨角獸企業重金招聘Python工程師標準>>>

原文

記得當年搞NOIp時，我犯過一個相當嚴重的錯誤：錯誤地把Floyd算法的i, j, k三層循環的位置順序搞顛倒了。直到準備省選時我才突然意識到，Floyd算法應該最先枚舉用于松馳操作的那個“中間變量”k，表示只經過從1到k的頂點的最短路；而我卻一直習慣性地以為i, j, k應該順次枚舉。令人驚訝的是，這個錯誤跟了我那么久我居然從來都沒有注意到過。后來，我發現有我這種經歷的人不止一個。慣性思維很可能會讓你接受一些明顯錯誤的算法，并且讓你用得坦坦蕩蕩，一輩子也發覺不了。
??? 假使你需要把一個數組隨機打亂順序進行重排。你需要保證重排后的結果是概率均等、完全隨機的。下面兩種算法哪一種是正確的？其中，random(a,b)函數用于返回一個從a到b（包括a和b）的隨機整數。

1. for i:=1 to n do swap(a[i], a[random(1,n)]);
2. for i:=1 to n do swap(a[i], a[random(i,n)]);

??? 如果不仔細思考的話，絕大多數人會認為第一個算法才是真正隨機的，因為它的操作“更對稱”，保證了概率均等。但靜下心來仔細思考，你會發現第二種算法才是真正滿足隨機性的。為了證明這一點，只需要注意到算法的本質是“隨機確定a[1]的值，然后遞歸地對后n-1位進行操作”，用數學歸納法即可輕易說明算法的正確性。而事實上，這段程序一共將會產生n*(n-1)*(n-2)*...*1種等可能的情況，它們正好與1至n的n!種排列一一對應。
???? 有人會問，那第一種算法為什么就錯了呢？看它的樣子多么對稱美觀啊……且慢，我還沒說第一種算法是錯的哦！雖然第一種算法將產生比第二種算法更多的可能性，會導致一些重復的數列，但完全有可能每種數列重復了相同的次數，概率仍然是均等的。事實上，更有可能發生的是，這兩種算法都是正確的，不過相比之下呢第一種算法顯得更加對稱美觀一些。為此，我們需要說明，第一種算法產生的所有情況均等地分成了n!個等價的結果。顯然，這個算法將會產生n^n種情況，而我們的排列一共有n!個，因此n^n必須能夠被n!整除才行（否則就不能均等地分布了）。但是，n!里含有所有不超過n的質數，而n^n里卻只有n的那幾個質因子。這表明要想n^n能被n!整除，n的質因子中必須含有所有不超過n的質數。這個結論看上去相當荒唐，反例遍地都是，并且直覺上告訴我們對于所有大于2的n這都是不成立的。為了證明這一點，只需要注意到2是質數，并且根據Bertrand-Chebyshev定理，在n/2和n之間一定還有一個質數。這兩個質數的乘積已經大于n了。搞了半天，第一種看似對稱而美觀的算法居然是錯的！

轉載于:https://my.oschina.net/darkness/blog/802125

總結

以上是生活随笔為你收集整理的随机洗牌：哪一种算法是正确的？的全部內容，希望文章能夠幫你解決所遇到的問題。

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