首页 > 试题广场 >

配对游戏

[编程题]配对游戏
  • 热度指数：101 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
美团点评是综合性生活服务平台，覆盖吃喝玩乐。在休闲娱乐版块，有很多轰趴、桌游、密室逃脱类的项目，适合多人一起玩。下面就是出自团队游戏场景中的一个问题。
有 n 个人排成一排，一开始全部面向前方，然后大家一起转身，随机朝左或是朝右转。
转身后，不断检查队列，如果存在两个面对面的相邻的人，则将这两个人从队列中消除；直到不存在两个面对面的相邻的人。
例如 > 表示向右， < 表示向左
队列“>>><<<”的消除过程为，“>>><<<”到“>><<”到“><”到“”（每次去除一对），最后剩下人数为0。
队列“>><><<<>”的消除过程为，“>><><<<>”到“>><<<>”到“><<>”到“<>”（每次去除一对)，最后剩下人数为2
求最后剩下人数的期望值。

输入描述:
一行一个正整数 n (1 ≤ n ≤ 2000)。


输出描述:
一行一个实数，表示剩下人数的期望值，四舍五入保留三位小数。
示例1

输入

10

输出

4.168
算法知识视频讲解
添加回答
C/C++
hades496头像 hades496
递推~ 
f[1]=1;f[2]=1.5;f[3]=2;
for(int i=4;i<=n;i++)
    f[i]=(-(i-2)*f[i-3]+(i-3)*f[i-2]+(i+1)*f[i-1])/i;
printf("%.3lf\n",f[n]);

编辑于 2017-07-21 21:36:47 回复(1)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 美团 动态规划 测试开发工程师 大数据开发工程师 Java工程师
来自：CodeM 2017美...
难度：
1条回答 4548浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号