ys1937

、
12d" />您老这杆子把大家都扫回“万恶的旧社会”鸟。就当给秀艺“忆苦思甜”吧
老程 发表于 2012-11-7 08:49

**

    该死该死，认错了！
    自罚停止发言一天。
    嘻嘻！

老程

**

    该死该死，认错了！
    自罚停止发言一天。
    嘻嘻！
ys1937 发表于 2012-11-7 09:17

自罚停言不行，积极参与才是正着。这楼没您老和晓梦是盖不高滴。

金秋

燕坛以前是文科生的地盘，现在风水轮流转，文科生都靠边站了哈。

ys1937

    第N+1个箱子也能打开的条件是，其钥匙不在自己肚子里。这个概率是 N/（N+1）。所以，打开全部N+1个箱子的概率是，打开N个箱子的概率乘以最后那个箱子的钥匙不在自己肚子里的概率。即，（K/N） * N/（N+1）。 也就是 K/（N+1）。
晓梦 发表于 2012-11-7 03:58

**

    这一证明似乎不够全面。
    第 N+1 个箱子也能打开，要分二种导体况：
    1、 其钥匙不在自己肚子里，而且，早先的 N 个箱子全都能打开——这是晓梦讨论的情况；
    2、 其钥匙在自己肚子里，而且，在打开 K 个箱子时，这 K 个箱子里正好有一个就是第 N+1 个箱子。


    回师太：昨天您老喝了多少山西老陈醋？怎么说出的话酸溜溜滴。

老程

2、 其钥匙在自己肚子里，而且，在打开 K 个箱子时，这 K 个箱子里正好有一个就是第 N+1 个箱子。

ys1937 发表于 2012-11-8 07:59

斗胆插一句：我是这样理解的，这N+1不是特指的哪个箱子，而是箱子总数比N个多了1。
纯属多嘴，Ys老提出的疑问，晓梦必会答复，我还是继续围观。

showcraft

晓梦101楼得归纳法证明，用的条件概率，没有问题，ys老说的不全面其实是多余了。
这道题目用归纳法当然可以，只是本质的内容，我还没想明白，似乎是和n元对称群的k重置换有关。

ys1937

**

    把晓梦的证明严格起来：
    1、 N = K 时，已经把所有的箱子全部打开了，因此这种做法的概率是（K/N） = 1。
    下面的讨论是在 K 小于 N 的情况下进行的。
    2、 N = 2 时，K = 1，即二个箱子打开一个，这时，很容易看出能够同时打开二个箱子的概率是（1/2），假设成立。
    3、 假设 N 个箱子中打开 K 个后可以打开所有箱子的概率是：K/N。
    4、 加上第 N + 1 个箱子后，出现两种可能：
    （1） 先打开的 K 个箱子里有第 N + 1 个箱子；
    （2） 先打开的 K 个箱子里没有第 N + 1 个箱子。
    下面分开进行讨论。
    （明天再写了，要睡了。）

showcraft

ys老多虑了。
K/N代表的是打破n个箱子中的k个，已经把所有n个箱子打开了，所以第n+1个箱子的钥匙只要不在自己肚子里，就行了，而这个概率是n/(n+1)，两者相乘就是条件概率，没有问题。

ys1937

    K/N代表的是打破n个箱子中的k个，已经把所有n个箱子打开了，所以第n+1个箱子的钥匙只要不在自己肚子里，就行了，而这个概率是n/(n+1)，两者相乘就是条件概率，没有问题。
showcraft 发表于 2012-11-8 23:50

**

    我没有认为晓梦的证明“有问题”（即“错”了），而是想给这一证明“严格化”、“补漏洞”。

    继续：
    5、 “先打开的 K 个箱子里有第 N + 1 个箱子”，这时，不防假设不在 K 个之列的是第一个箱子。
    对第一个箱子而言，要打开它的充要条件是这箱子里放的不给是它自已有钥匙。因此，可打开的概率是（K/N） * N/（N+1）。 也就是 K/（N+1）。
    6、 “先打开的 K 个箱子里没有第 N + 1 个箱子”，这时，要能够打开它的充要条件是第 N + 1 个簟子里放的不是自已的钥匙。同样可打开的概率是（K/N） * N/（N+1）。 也就是 K/（N+1）。

    7、 这上证明还有一个“漏洞”需要补上，这个漏洞是：
    举例说明：当 N  = 2 时，K 、 1，2，也不是说，进入 N = 3时，用这一方法能够证明的是 K = 1，2 的情况，而 K = 3 是需要“另行证明”的——而这实际上就是上面在第一点上所述及的。

    上面，重点在五、六两条，而这也是晓梦证明的核心，我是“照搬”过来了。

showcraft

由于精力有限，此书没能继续读下去。最近一段时间梳理了下线性代数，接下来应该重温微积分，估计要等到明年才能go on了，呵呵。

showcraft

新题目来了。
把长度为1的线段按任意方式折成三段，求他们能构成三角形的概率。

showcraft

晓梦兄确实高手，佩服。

psyzjs

晓梦兄确实高手，佩服。
showcraft 发表于 2013-3-25 00:18

这题目其实不难，设三角形任意2边长度和为X，则第3边长度为（1-X），根据三角形的边长关系，必符合X＞（1-X），即X＞1/2，此外X＜1.

进一步的，设这两边的长度为a和（X-a），进一步可推出a的测度是m（X）/2，而三角形周长的测度是1，X的测度是1/2（因为1/2＜X＜1），不难推出这样的三角形存在的概率是1/4.

psyzjs

119# psyzjs

>>>>>   设这两边的长度为a和（X-a），进一步可推出a的测度是m（X）/2

这句话看不懂。m（X）是什么？ m（X）/2 又是什么？ 如何推出的？ 能否详细讲讲。 否则看不懂m（X），“不难推出这样的三角 ...
晓梦 发表于 2013-3-26 20:24

m(X) 是X的测度函数。m（X）/2是m(X)这个测度函数值的1/2.

老程

少了ys1937少了不少精彩。

showcraft

少了ys1937少了不少精彩。
老程 发表于 2013-3-26 21:48

深以为然啊。

showcraft

发一道昨天花了不少时间解决的排列组合题，当然思路是计算机科学的动态规划，纯组合学上的通用的closed from的答案目前还是没办法找到。

http://www.douban.com/note/269136472/
DP解决一道排列组合（湫秋系列故事——安排座位）
2013-03-30 20:33:28
http://acm.hdu.edu.cn/showproblem.php?pid=4532
湫秋系列故事——安排座位
Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 143    Accepted Submission(s): 38Problem Description
　　为了给腾讯公司找到更多优秀的人才，HR湫秋最近去某高校组织了一次针对该校所有系的聚会，邀请了每个系的一些优秀学生来参加。　　作为组织者，湫秋要安排他们的座位。这并不是一件很简单的事情，因为只有一排位置，并且位置总数恰好等于参加聚会的人数。为了促进交流，两个来自相同系的同学不可以座位相邻。湫秋现在希望知道有多少种不同的合理安排座位的方法（任意两个合理的安排方法，只要有一个位置的同学不同，都被认为是不同的）。


Input
输入第一行为T，表示有T组测试数据。每组数据一个N开始，表示一共有多少个系。下面的一行包含N个整数Ai，表示每个系的到场人数。[Technical Specification]1. 1 <= T <= 472. 1 <= N, Ai <= 473. 1 <= Sum(Ai) <= 447


Output
对每组数据，先输出为第几组数据，然后输出结果。由于结果可能很大，输出对1,000,000,007 取余后的结果。


Sample Input
3 2 1 2 2 1 3 3 1 2 3


Sample Output
Case 1: 2 Case 2: 0 Case 3: 120


Source
2013腾讯编程马拉松复赛第一场（3月29日）


Recommend
liuyiding

我的思路：
这道题目是组合学的范畴，如果纯从组合角度考虑，利用容斥原理，也不是不能解决，只是会相当繁琐，布鲁迪《组合数学》第六章的习题17是一道类似的变例，当然这道题目与之还有区别，因为前者只需要同一个系学生的不全部连续排列即可，而这道题目需要同一系的学生两两分开。既然是算法题目，那就换种思路，用动态规划，DP来解决吧。
这里有n个系，按照最终人数由少到多排列为a1，a2，...，an
令N（c，b1，b2，...，bn）表示在{b1，b2，...，bn}人数情况下同系学生两两分隔的排列数，其中c=b1+b2+...+bn
那么现在来了第c+1位第x系的童鞋，不妨设x=n，现在的问题就是N（c+1，b1，b2，...，bn+1）如何递归推导出来？
首先任意一种原先c位已经排好序的序列中，共有c+1个空格可供我们的第c+1位童鞋排入，而他不能与其中的bn位系友相邻，因而只有c+1-2bn种位置。值得注意的是，这只是符合条件的一种情况，即新插入的同学插入到满意的位置，而该位置左右包括他本人在内，三位同学来自三个不同的系。
另外不能遗漏的一种情况是他插入到某个位置，该位置左右两位同学来自他不同的某个系。这种情况下，需要对n系之外的n-1个系逐一检查，如果这n-1个系中任何一个系有大于等于2个学生来参加聚会，则都应予以考虑。
综上，递归式如下
N（c+1，b1，b2，...，bn+1）=N（c，b1，b2，...，bn）*（c+1-2bn）+2[N（c-1，b1-1，b2，...，bn）+N（c-1，b1，b2-1，...，bn）+...+N（c-1，b1，b2，...，bn-1，bn）]
之所以第二种情况需要乘以2，是因为在考虑过程中将排在C同学前后的两位同系学生比如A和B，等价为A来考虑，但在具体情况下，A，C，B与B，C，A是两种不同情况。
很明显，边界条件为N（c，1，1，...，1）=c!，且N中任意一项若小于等于0，则N为0。
以N（6,1,2,3）来举例说明：
N（3,1,1,1）=3!=6,
N(4,1,2,1)=N（3,1,1,1）(4-2)=12=N(4,1,1,2)
需要说明的一点是，任意非递增序列的N数值上与递增序列相等，即N(4,1,2,1)=N(4,1,1,2)，但要保持序列的对应关系。这点计算上的技巧接下来就会碰到。
N(5,1,2,2)=N(4,1,2,1)（5-2）+2*N（3,1,1,1）=12*3+2*6=48
N(6,1,2,3)=N(5,1,2,2)（6-2*2）+2*N(4,1,1,2)=48*2+2*12=120
OK，至此，整个dp的思路应该说的比较清楚了。具体code我就不写了，毕竟数年没有coding，生疏的不成样子，呵呵。
这两天还在着手写《具体数学》的读书笔记，Stay tuned！