算法分析大型实验报告

《算法分析大型实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、班级:学号:指导老师:珊M工空*谆之江学院ZHUIANGCOLLEGEOFZHEJIANGUNIVERSITYOFTECHMQLOGY算法分析大型实验报告编号标题题目一2918Pachinko题目二2920Ranking软件801金睿颖200820630112赵端阳2010年7月Pachinko1SpecialJudgeTimeLimit:1SecondMemoryLimit:32768KBPachinkoisaJapanesegameplayedtoramusementandprizes,an

2、dissimilartopinball.Thegameisverysimple:youshootsmallmetalballsintothemachineandtheyfalldown,bouncingofftheobstaclesuntiltheyfallintoagate.Thegateintowhichyourballfallsdeterminesthewinnings.Sinceyoucanmoreorlessdeterminethecolumnintowhichtheballisdro

3、pped(bysettingitsinitialspeedanddirection),youcaninfluenceyourwinchances・Youaretocalculateyourexpectedwinnings.Wemodelthepachinkomachineasfollows:youcandroptheballinanycolumnanditfallsdownuntiliteitherreachesthebottomofthemachine(whichresultsinnowins

4、),agate(indicatedbyanumber1to9,whichresultsinthatwin)oranobstacle(indicatedbyaasterisk).Ifaballhitsanobstacleitproceedsfallinginthecolumntotheleftortotherightoftheobstacle,with50/50probability.Notwoobstaclesorgatesareadjacent,notevendiagonally,andnon

5、eislocatedintheleftmostorrightmostcolumn.InputOnthefirstlineanintegert(1<=t<=100):thenumberoftestcases・Thenforeachtestcase:Onelinewithtwointegershandw(1<=h，w<=100):theheightandwidthofthepachinkomachine・hlineswithwcharactersdescribingthepachinkomachin

6、e.ATdenotesanemptyspace,*anobstacleandT…9thewinninggates.OutputForeachtestcase:Onelinewiththemaximalexpectedwinningswitheitheranabsoluteorarelativeerrorofatmost10-6.SampleInput3751…..2.♦•♦•88•••1・•♦•-.9.7.7.1010********•・••••・•SampleOutput5.0000007.5

7、000003.375000【全文翻译】弹球游戏弹球游戏是一款集娱乐和奖励的tl本游戏，类似于三维弹球。游戏很简单：你发射一个小金属球到机器里，通过挡板和障碍物的反弹，直到掉进洞口。球掉在哪个洞里决定了你的奖金。既然你可以或多或少的决定金展球从哪个入口进入（通过设定球的初始速度和方向），你可以提髙你的获胜儿率。你耀计算你的预期奖金。我们建立弹球游戏的模型如下：你可以让金属球从任何入口进入，球会掉到机器底部（不会赢得奖励），也会掉到洞里（由数字1到9表示，会赢得奖励），还会撞到障碍物上（由1个星号表

8、示）。如果金属球撞到障碍上它会向左或向右掉下去，各有50%的概率。没有两个相邻的洞或者障碍，甚至对角，也没有在最左边或最右边的入口。输入第一行的一个整数t（1<=t<=100）：要输入的个数。然后输入每个测试数据：一行两个整数h和w（1<=h,w<=100）：表示弹球游戏机的高度和宽度。h行和w用来绘制弹球游戏机。一个“・”表示一个空的空I'可，一个表示障碍，“1”……“9”表示可赢得奖金的洞。输出对于每个测试数据：一行为预期的最大奖金和一个最大为10七的相对或绝对误差。【程序代码】程序名称：Z