引言
前几天刷了下微软的预科生笔试题,感觉略难,今天静下心仔细思考做出其第一道,特此分享一下。
题目描述
Little Hi is playing a video game. Each time he accomplishes a quest in the game, Little Hi has a chance to get a legendary item.
At the beginning the probability is P%. Each time Little Hi accomplishes a quest without getting a legendary item, the probability will go up Q%. Since the probability is getting higher he will get a legendary item eventually.
After getting a legendary item the probability will be reset to ⌊P/(2I)⌋% (⌊x⌋ represents the largest integer no more than x) where I is the number of legendary items he already has. The probability will also go up Q% each time Little Hi accomplishes a quest until he gets another legendary item.
Now Little Hi wants to know the expected number of quests he has to accomplish to get N legendary items.
Assume P = 50, Q = 75 and N = 2, as the below figure shows the expected number of quests is
2*50%25% + 350%*75%100% + 350%*100%25% + 450%*100%*75%*100% = 3.25
输入
The first line contains three integers P, Q and N.
1 ≤ N ≤ 106, 0 ≤ P ≤ 100, 1 ≤ Q ≤ 100
输出
Output the expected number of quests rounded to 2 decimal places.
样例输入
50 75 2
样例输出
3.25
翻译一下
小嗨玩电子游戏。 每当他在游戏中完成任务时,小嗨都有机会获得一个传奇的物品。
一开始概率为 P%。 每次 Little Hi 完成任务而没有获得传奇物品,概率将上升 Q%。 由于概率越来越高,他最终会得到一个传奇物品。
获得传奇物品后,概率将重置为⌊P/(2I)⌋%(⌊x⌋表示最大整数,不超过 x),其中我是其已有的传奇物品的数量。 每当 Little Hi 完成任务时,概率也将上升 Q%,直到他获得另一个传奇物品。
现在,小嗨想知道他要完成的 N 个传奇物品的预期数量。
假设 P = 50,Q = 75,N = 2,如下图所示,预期的任务数是
2 * 50%* 25%+ 3 * 50%* 75%* 100%+ 3 * 50%* 100%* 25%+ 4 * 50%* 100%* 75%* 100%= 3.25
解析
分析题可知,此题目实际上是让求获得 N 个物品所需进行任务的数学期望,很容易看出获得每个物品的概率是独立事件,故每个物品的期望叠加即为 N 个物品所需进行任务的数学期望
代码如下:(gcc 6.3.1)
#include<stdio.h>
#include<stdbool.h>
double getNextLegend(int p,double q);
double getNextLegend(int p,double q){
double ration_p=1.0*p/100;
double needQuest=1;
double another=1;
while(true){
another*=(1-ration_p);
needQuest+=another;
ration_p+=q;
if(ration_p>=1.0)
break;
}
return needQuest;
}
int main(void){
int P,Q,N;
int i;
scanf("%d %d %d",&P,&Q,&N);
double result=0.0;
double ration_Q=1.0*Q/100;
for(i=0;i<N;i++){
double getLegend=getNextLegend(P,ration_Q);
result+=getLegend;
P/=2;
}
printf("%.2f",result);
return 0;
}
结束语
看到题目描述,其实很容易想到利用深度优先遍历遍历解空间树来做,但是这样做会造成空间复杂度过高,而且要用递归遍历整个子树,我开始就是按照这个思路去做,但感觉很麻烦,最后看到别人提供的思路即求每个物品的期望叠加,简洁清晰,但这就需要在思考时不局限于题目,深刻分析题目从而最终找到解决方案。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于