ProjectEuler 367 bozo sort - 拼圖

367. bozo sort

http://projecteuler.net/problem=367

所謂的 bozo sort（不要把它和效率稍微差一點的 bogo sort 搞混），

是一個排序演算法，當序列不是已排好時就隨機交換兩個元素，直到排好為止。


若考慮前四個自然數的 4! 種排列，各自計算其期望排序完成的交換次數再加以平均，

這個平均次數是 24.75 次。

已排好的那一串視為需要 0 次交換。


這個題目裡考慮一個 bozo sort 的變種：

當序列不是已排好時，隨機選出三個元素並隨機打亂它們直到排好為止。

打亂三個元素的 3! = 6 種可能是均勻隨機出現的。

同樣的已排好的那一串視為需要 0 次操作。

對前四個自然數的 4! 種排列各自計算期望完成的次數後加以平均，

這個平均次數是 27.5 次。

若對前 11 個自然數的 11! 種排列進行相同的計算，問這個平均次數是多少？


答案四捨五入至整數。

--
補充：題目中說的那個「效率稍微差一點」的 bogo sort 和 bozo sort 只差在一點

當序列是沒排好時是全部洗牌而不僅是交換隨機兩個元素

這題看起來好像有機關在裡面的樣子 = =+

--
有人喜歡邊玩遊戲邊上逼；
也有人喜歡邊聽歌邊打字。
但是，我有個請求，
選字的時候請專心好嗎？
-- 改編自「古 火田 任三郎」之開場白

--