排序算法：輸出

我面臨的一個網站上的這個問題，我很不能理解輸出，請幫助我理解它： -排序算法：輸出

BOGO排序，是一個愚蠢的算法隨機打亂，直到它的排序順序。但是在這裏我們已經調整了一些，所以如果在最後一次洗牌後，幾個第一個元素結束在正確的位置，我們將修復它們，並且不要再洗牌這些元素。如果他們在正確的位置，我們也會爲最後的元素做同樣的事情。例如，如果初始序列是（3,5,1,6,4,2），並且在一次洗牌之後，我們得到（1,2,5,4,3,6），我們將保留1,2和6並繼續與排序（5，4，3）使用相同的算法。計算改進算法的預計洗牌數量，以排序前n個自然數的序列，因爲最初沒有元素位於正確的位置。

輸入：

2 
6 
10

輸出：

2 
1826/189 
877318/35343

對於每組測試輸出所需的改進算法混洗的預期量來在形式的第一n個自然數的序列進行排序不可簡化的分數。我無法理解輸出。

來源

2012-06-17 potato man

輸入怎麼樣？初始序列是（2，6，10）？這已經排序... –

@SimeonVisser：這裏的2意味着輸入將包含前2個自然數，但未排序的offcourse類似6意味着前6個自然數 –

輸出值可能是有理數？也就是說，爲了使[1,2,3,4,5,6]成爲秩序所需的修改後的發動機數的預期數是186/189〜= 9.66次？我想不出計算這些期望值的好方法，所以我不能測試這個意思，但是第一個值2是序列[1,2]的正確答案（它是'1 + sum（1/n^2 for n in 1..infinity）'）。 – Blckknght

被認爲是我假設你發現這個問題上CodeChef。有一個Bogosort問題here的答案的解釋。

來源

2012-06-17 12:02:48

是安德斯，我在Codechef發現了這個問題，感謝您的鏈接:) –

好吧，我想我找到了答案，這裏還有一個類似的問題https://math.stackexchange.com/questions/20658/expected-number-of-shuffles-to-sort-the-cards/21273，而這個問題可以作爲擴展

來源

2012-06-17 12:01:28

排序算法：輸出

回答

相關問題