首页 > 试题广场 >

无聊的牛牛和羊羊

[编程题]无聊的牛牛和羊羊

热度指数：2244 时间限制：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

算法知识视频讲解

Python

兰偷荀令香

max_value = 101

n_input, m_input = map(int, input().strip().split())
mark_lst = [[0 for _ in range(max_value)] for _ in range(max_value)]
value_lst = [[0 for _ in range(max_value)] for _ in range(max_value)]

def func_1(n, m):
if m <= 0:
return 0
if mark_lst[n][m]:
return value_lst[n][m]
else:
s = (n + m) * (n + m - 1) / 2
p_1 = n * (n - 1) / 2
p_2 = n * m
p_3 = m * (m - 1) / 2
a = p_2 / (s - p_1)
b = p_3 / (s - p_1)
c = s / (s - p_1)
value_lst[n][m] = a * func_1(n + 1, m - 1) + b * func_1(n + 2, m - 2) + c
mark_lst[n][m] = 1
return value_lst[n][m]

print(round(func_1(n_input, m_input), 1))

发表于 2019-02-20 19:47:21 回复(0)