西安电子科技大学第16届程序设计竞赛网络同步赛 另一个另一个简单游戏

文章内容大纲 (右击展开→→)

内容预览:
  • 接下来为T组数据~
  • 输出描述: 对于每组数据,在一行上输出最后剩下数的期望值的整数部分~
  • 示例1 输入 231 1 122 3 输出 12   现有数字a,b,c.那么abc的平均值...~

链接:https://www.nowcoder.com/acm/contest/107/D
来源:牛客网

题目描述

现在有n个数,每次随机取出两个数x,y,然后加入一个数为(x+y)/2,问最后剩下的那个数的期望是多少?

输入描述:

有多组输入数据,第一行为一个数字T,代表有T组输入数据 (0<T≤20)。
接下来为T组数据。
每组测试数据分2行:
第一行为n,表示有n个数(1≤n≤100)
接下来的一行有n个正整数ai,表示初始的n个数(1≤ai≤10000,1≤i≤n)。

输出描述:

对于每组数据,在一行上输出最后剩下数的期望值的整数部分。

示例1

输入

2
3
1 1 1
2
2 3

输出

1
2

 

现有数字a,b,c.那么abc的平均值为(a+b+c)/3;

取出两个数,只有可能三种情况,ab,ac,bc;

这三种情况,每一种的概率是相等的;

而每种情况的平均值分别为((a+b)/2+c)/3,((a+c)/2+b)/3,((b+c)/2+a)/3;      //如果看不清楚请手动模拟啊

而对于新数列,肯定也有一个平均值,我们假设d=((a+b)/2+c)/3,那么对于第一种情况,平均值就是(d+c)/2;

刚刚说过,每种情况的概率相等,也就是说,对于新的三个数列,平均值的期望可以很容易算出,就是把三个数列的平均值加起来除以三;

经过计算,很容易得出,新数列平均值的期望,就是(a+b+c)/3,也就是说,新数列的平均值值的期望,相较于原数列的平均值,是相等的;

对于最后一个数列,将只有一个元素,也就是题中描述的那个数,这个数列的平均值就是它自己,所以求它的期望,就是求它的平均值的期望,那么由上面的结论一步步递推下来,就可以得出,这个期望,就是原数组的平均值;

于是,我们只需要求平均值就行了;

以上就是:西安电子科技大学第16届程序设计竞赛网络同步赛 另一个另一个简单游戏 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论