Re: [理工] DS 101台大
比一次
比較
/ \
Y / \ N
/ \
結果1 結果2
比兩次
比較 比較
/ \ / \
Y / \ N Y / \ N
/ \ / \
比較 結果3 or 結果1 比較
/ \ / \
Y / \ N Y / \ N
/ \ / \
結果1 結果2 結果2 結果3
比三次
比較
/ \
/ \
Y / \ N
/ \
/ \
比較 比較
/ \ / \
Y / \ N Y / \ N
/ \ / \
結果1 結果2 結果3 結果4
單純暴力法 ... XD
接下來用數學歸納法應該可以推得 k+1
※ 引述《jeremy4849 (yang)》之銘言：
: 1. Assume that the elements are pairwise distinct. Answer the following questions on sorting algorithms.
: (2)A single comparison between two elements can distinguish up to 2 permutations. How many permutations can be distinguished using k comparisons?
: 我的答案：(k+1)!
: 不知道這題的意思是什麼，我的假設是在k+1個數之下做 k comparisons，如果有3個數做2 comparisons 應該可以有 3!個組合，因為每種組合似乎都可以用最多兩次交換就可以得到。
: 這題之前有人討論過，看完還是不解，不知道大家的想法如何。感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.40.173
推
02/19 18:51, , 1F
02/19 18:51, 1F
推
02/20 01:36, , 2F
02/20 01:36, 2F
→
02/20 01:37, , 3F
02/20 01:37, 3F
→
02/20 01:38, , 4F
02/20 01:38, 4F
推
02/21 20:58, , 5F
02/21 20:58, 5F
討論串 (同標題文章)