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 只差在一點
當序列是沒排好時是全部洗牌而不僅是交換隨機兩個元素
這題看起來好像有機關在裡面的樣子 = =+
--
有人喜歡邊玩遊戲邊上逼；
也有人喜歡邊聽歌邊打字。
但是，我有個請求，
選字的時候請專心好嗎？
-- 改編自「古 火田 任三郎」之開場白
--
All Comments