※ 引述《wisdom7676 ()》之铭言： : Q:假设有N个人交换礼物 大家把礼物放在一堆 : 抽礼物的时候可以拿到自己的礼物 : 开奖的时候至少有一对人是互相拿到对方礼物的机率 : A: : 1 2 3 4 5 6 ... N : 口口口口口口... 口 : 上排为人 下排空格填上数字则为拿到的礼物编号 当然编号n的人他提供的礼物编号也给n : 在N个空格填上1~N且不重复总共有N!种填法 : 以下是题目的重点: : 至少有一对人互相拿到对方礼物 : 若是我强制指定其中两个人互拿对方礼物 : 则剩下N-2个人无论怎麽把剩下数字填入 : 都一定符合"至少一对人互相拿到对方礼物" : 因为那一对拿到彼此礼物的两人早就已经被指定了 : 剩下的人是否还有人彼此拿到对方的礼物已经无所谓 : 因此剩下N-2个数字填入N-2个格子总共有(N-2)!种填法 : 而最初的时候强制指定任两人必须填入对方的数字则有C(N,2)种指定的方法 : 因此符合条件的总共有[C(N,2)]x(N-2)! = N!/2种 : 但是此N!/2种会重复计算同时有两对以上互相拿到对方礼物的状况 : 也就是指定1和4号互拿对方礼物的时候5和8号可能也互拿 : 但是指定5和8号互拿的时候又算了一次1和4互拿 这两种情况是同一件事情 : 因此接下来就是要用排容原理把同时两对人互拿的情况扣掉 : 然後补回三对人同时互拿 扣掉四对人同时互拿 $%@&#!^& : 另外一种算法 : P(至少有一对互拿对方礼物) = 100% - P(完全没有人互拿对方礼物) : 以上不管哪种算法都让人不想算下去... 囧 : 不过真的要算应该就是这样算了吧 : 最简单解：叫电脑跑比较快 : Edit:方法1试算化简了一下 答案就是上面那一篇给的公式 : 两对 => C(N,2)xC(N-2,2)x(N-4)!/2! = N!/[(2^2)x2!] : k对 => C(N,2)xC(N-2,2)x...xC(N-2k)x(N-2k-2)!/k! = N!/[(2^k)x(k!)] ^^^^^A ^^^^^^B ＊有点小bug，订正一下： A应改为 N-2k+2，即 A = N-2k+2 B应改为 N-2k，因为 B = A-2 = N-2k ＊LPH66 po的公式化简如下，即为机率公式 floor(n/2) (-1)^k 　　　　－ Σ -------- k=1 2^k * k! ＊附上matlab code，画图，横轴n为人数，纵轴p为机率。(机率趋近0.393...) n=linspace(1,100, 100); tmp=0; for k = 1:100 tmp = tmp + (-1)^k/2^k/factorial(k); p(1,k) = -tmp; end plot(n,p); ＊附上c# code，用来算机率 using System; namespace SwithPresents { class Program { static void Main() { Console.WriteLine("请输入人数(不要超过100，太大会爆掉)"); string numberStr = Console.ReadLine(); long number = Int32.Parse(numberStr); double possibility = 0; // 简化版 for (long k = 1; k <= Math.Floor(number / 2.0); k++) { possibility += -1 * Math.Pow(-1, k) / Math.Pow(2, k) / (double)factorial(k); } Console.WriteLine("{0}", possibility); } static long factorial(long t) { if (t == 1) return t; else return t * factorial(t - 1); } } } ＊本来想写个乱数模拟程式，今天太忙了，心血来潮再来补上 orz 以上有错请指正" : 按排容原理补上正负号以後全部加起来最後就变成上一篇的公式 : 因此机率 = 上篇公式/N! : ※ 编辑: wisdom7676 来自: 122.120.40.166 (12/18 05:30) : ※ 编辑: wisdom7676 来自: 122.120.40.166 (12/18 05:31) : → east101010:看来你离散学的很好~我叫老师帮你加分XD 12/18 05:47 : → wisdom7676:其实我没学过离散..XD 高中时学的数学的应用而已 12/18 05:54 : 推 east101010:高中已经教过排容原理了吗＠＠？ (惊) 12/18 06:00 : 推 chenyuhung:排容是什麽啊？我也是以为用高中学得来解就可以了 12/18 08:22 : 推 teves:高中本来就有教排容啊,看来你高中数学没认真听XD 12/18 10:32 : → east101010:囧~~~我以为这是大学才会提到的名词~ 12/18 20:06 : → east101010:高中的时候应该已知道相关概念~但是或许不知道叫排容? 12/18 20:07 : 推 euleramon:这篇真是经典.. 就算只用到高中数学，也是很经典 12/18 23:09 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 59.120.13.162