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 |
|