QY16. 无聊的牛牛和羊羊
描述
牛牛和羊羊非常无聊.他们有n + m个共同朋友,他们中有n个是无聊的,m个是不无聊的。每个小时牛牛和羊羊随机选择两个不同的朋友A和B.(如果存在多种可能的pair(A, B),任意一个被选到的概率相同。),然后牛牛会和朋友A进行交谈,羊羊会和朋友B进行交谈。在交谈之后,如果被选择的朋友之前不是无聊会变得无聊。现在你需要计算让所有朋友变得无聊所需要的时间的期望值。输入描述
输入包括两个整数n 和 m(1 ≤ n, m ≤ 50)输出描述
输出一个实数,表示需要时间的期望值,四舍五入保留一位小数。示例1
输入:
2 1
输出:
1.5
C 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2020-12-23
#include <stdio.h>
int main()
{
int n, m, s, k;
scanf("%d%d", &n, &m);
s = n + m;
double f0 = 0, f1 = s * 0.5, cur;
for(k = 2; k <= m; ++k)
{
cur = s * (s - 1) / (1.0 * k * (2 * s - k - 1))
+ 2 * (s - k) * 1.0 / (2 * s - k - 1) * f1
+ (k - 1) * 1.0 / (2 * s - k - 1) * f0;
f0 = f1;
f1 = cur;
}
printf("%.1lf\n", f1);
}
C 解法, 执行用时: 2ms, 内存消耗: 364KB, 提交时间: 2020-07-28
#include <stdio.h>
int main()
{
int n, m, s, k;
scanf("%d%d", &n, &m);
s = n + m;
double f0 = 0, f1 = s * 0.5, cur;
for(k = 2; k <= m; ++k)
{
cur = s * (s - 1) / (1.0 * k * (2 * s - k - 1))
+ 2 * (s - k) * 1.0 / (2 * s - k - 1) * f1
+ (k - 1) * 1.0 / (2 * s - k - 1) * f0;
f0 = f1;
f1 = cur;
}
printf("%.1lf\n", f1);
}