m*****n
发帖数: 5245 | 1 ☆─────────────────────────────────────☆
pawn (无嗔) 于 (Thu Dec 18 14:11:34 2008) 提到:
这道题看似不很难，但俺硬是答不上来，唉！
给一个数组a[1]到a[n]，现在随机生成a的一个排列b[1]到b[n]，问对所有1《i《n，a[i] ！= b[i]的概率是多少？也就是说a和b在每一位上都不相同，假设a本身没有重复的数。
☆─────────────────────────────────────☆
jingoshine (jingo) 于 (Thu Dec 18 14:19:36 2008) 提到:
f(n) = (n-1)*(f(n-1)+f(n-2)), f(n)为可能的排列数。
假定数组就是1...n,n可以放在位置1...n-1,共n-1种可能。假定n放在了m(1<=m
那么m放的位置有两种可能，a)是m放在位置n，b)m不放在位置n
a) m和n的位置定了，其他n-2位置不定，共f(n-2)种可能
b) 这时可以把第n个位置看成是第m个位置，而数m |
|
