[中譯] ProjectEuler 367 bozo sort

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 (-858993460)時間14年前 (2012/01/15 06:51)推噓3(3推 0噓 2→)

留言5則, 2人參與討論串1/1

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)