首页 > 试题广场 >

无聊的牛牛和羊羊

[编程题]无聊的牛牛和羊羊
  • 热度指数:2235 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
牛牛和羊羊非常无聊.他们有n + m个共同朋友,他们中有n个是无聊的,m个是不无聊的。每个小时牛牛和羊羊随机选择两个不同的朋友A和B.(如果存在多种可能的pair(A, B),任意一个被选到的概率相同。),然后牛牛会和朋友A进行交谈,羊羊会和朋友B进行交谈。在交谈之后,如果被选择的朋友之前不是无聊会变得无聊。现在你需要计算让所有朋友变得无聊所需要的时间的期望值。

输入描述:
输入包括两个整数n 和 m(1 ≤ n, m ≤ 50)


输出描述:
输出一个实数,表示需要时间的期望值,四舍五入保留一位小数。
示例1

输入

2 1

输出

1.5
头像 牛客题解官
发表于 2020-06-05 18:15:48
题解 难度:中等难度 知识点:递推 数学逻辑 思路: 本题考察递推公式,1.本题将n无聊,m为不无聊。总共人数为s=n+m。每次从其中随机选出2个,将这两个数中的不无聊变成无聊,最终将s个人全部变成无聊。 2.假设当S个人中有K个人是不无聊,设平均需要f(K)次操作使得S个人全部变为无聊。每一次操作 展开全文