作者LPH66 (-858993460)
看板puzzle
標題[中譯] ProjectEuler 367 bozo sort
時間Sun Jan 15 06:50:57 2012
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 只差在一點
當序列是沒排好時是全部洗牌而不僅是交換隨機兩個元素
這題看起來好像有機關在裡面的樣子 = =+
--
有人喜歡邊
玩遊戲邊
上逼；
也有人喜歡邊
聽歌邊
打字。
但是，我有個請求，
選字的時候請
專心好嗎？
-- 改編自「古 火田 任三郎」之開場白
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.230.62
※ 編輯: LPH66 來自: 140.112.230.62 (01/15 06:51)
1F：推 utomaya:我猜是馬可夫鍊的問題 應該不難寫, 可是, 目前才一人解出? 01/15 07:17
2F：→ LPH66:我是也有想到這個方向 不過 11 個數需要 56 個狀態... 01/15 07:48
3F：推 utomaya:想來想去 好像也只有馬可夫鍊可以解 01/15 07:58
4F：→ LPH66:暴力法萬歲...感謝 Mathematica 的 Combinatorica` package 01/15 08:35
5F：推 utomaya:第7! L大好強! 01/15 08:37