MyException - 我的异常网
当前位置:我的异常网» 编程 » 这道题您会做吗?codeforces程序算法网的一道入门级题

这道题您会做吗?codeforces程序算法网的一道入门级题

www.MyException.Cn  网友分享于:2014-08-06  浏览:1次
这道题你会做吗?codeforces程序算法网的一道入门级题
概述:本文翻译了NB程序员们常去的国际知名的算法竞赛网站codeforces的第259期的一道入门级算法题,程序员朋友,这道题你会做么?

代码测试需求:

程序响应时间限制:1秒以内
程序内存限制:256M以内
输入方法:标准输入
输出方法:标准输出

《彩虹小马》里的女孩Twilight Sparkle与她的朋友Rainbow Dash,Apple Jack 以及 Flutter Shy在一起玩骰子游戏,但是她一直都在输。回到城堡以后,Twilight Sparkle对游戏里使用的骰子很感兴趣。

pony

骰子一共有m个面,第一面有一个点,第二面有两个点,以此类推,第m个面有m个点。Twilight Sparkle很清楚的知道,每当她丢一次骰子,都有可能随机出现其中的一个面。并且她还知道,每次扔出的概率都是独立的。现在请你帮助她计算下,当她扔出n次骰子后,所得的最大的点的预期值是多少?

输入值:包含2个整数,m和n (1 ≤ m, n ≤ 105)。

输出值:输出的结果对应于最大的点的预期值,结果误差在10-4范围内都视为正确答案。

示例,比如在假定m=2,n=2的情况下(即骰子只有两面,扔2次的情况):

  1. 你第一次扔了1个1,第二次扔了1个2,最大结果为2。
  2. 你第一次扔了1个1,第二次扔了1个1,最大结果为1。
  3. 你第一次扔了1个2,第二次扔了1个1,最大结果为2。
  4. 你第一次扔了1个2,第二次扔了1个2,最大结果为2。

由于出现上述四种情况的概率都为0.25,那么预期值为

(2 + 1 + 2 + 2)* 0.25 = 7/4

一些输出结果:

Input
6 1
Output
3.500000000000
 
Input
6 3
Output
4.958333333333
 
Input
2 2
Output
1.750000000000

本文翻译自Little Pony and Expected Maximum

 
1 楼 joseph830727 20 小时前  
public void cal(int m, int n){
		long b = System.currentTimeMillis();
		double sum = 0;
		for(int i = 1; i <= m; i++){
			if(i == 1){
				sum += 1;
			}else if(i <= m){
				double t = Math.pow(i, n) - Math.pow(i - 1, n);
				sum += t * i;
			}
		}
		double result = sum / Math.pow(m, n);
		long e = System.currentTimeMillis();
		System.out.println(result);
		System.out.println(e - b);
	}
2 楼 qq1376888124 20 小时前  
joseph830727 写道
public void cal(int m, int n){
		long b = System.currentTimeMillis();
		double sum = 0;
		for(int i = 1; i <= m; i++){
			if(i == 1){
				sum += 1;
			}else if(i <= m){
				double t = Math.pow(i, n) - Math.pow(i - 1, n);
				sum += t * i;
			}
		}
		double result = sum / Math.pow(m, n);
		long e = System.currentTimeMillis();
		System.out.println(result);
		System.out.println(e - b);
	}

   

文章评论

编程语言是女人
编程语言是女人
那些争议最大的编程观点
那些争议最大的编程观点
10个调试和排错的小建议
10个调试和排错的小建议
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员应该关注的一些事儿
程序员应该关注的一些事儿
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员的鄙视链
程序员的鄙视链
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我是如何打败拖延症的
我是如何打败拖延症的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
旅行,写作,编程
旅行,写作,编程
Java程序员必看电影
Java程序员必看电影
程序员和编码员之间的区别
程序员和编码员之间的区别
每天工作4小时的程序员
每天工作4小时的程序员
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
代码女神横空出世
代码女神横空出世
中美印日四国程序员比较
中美印日四国程序员比较
我的丈夫是个程序员
我的丈夫是个程序员
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
如何成为一名黑客
如何成为一名黑客
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
为什么程序员都是夜猫子
为什么程序员都是夜猫子
总结2014中国互联网十大段子
总结2014中国互联网十大段子
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
程序员都该阅读的书
程序员都该阅读的书
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员必看的十大电影
程序员必看的十大电影
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
一个程序员的时间管理
一个程序员的时间管理
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
漫画:程序员的工作
漫画:程序员的工作
鲜为人知的编程真相
鲜为人知的编程真相
 程序员的样子
程序员的样子
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
老程序员的下场
老程序员的下场
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有