从零开始的算法题生活(二) 有更新!

引言

前几天刷了下微软的预科生笔试题,感觉略难,今天静下心仔细思考做出其第一道,特此分享一下。

题目描述

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% + 3*50%*75%*100% + 3*50%*100%*25% + 4*50%*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;
}

结束语

看到题目描述,其实很容易想到利用深度优先遍历遍历解空间树来做,但是这样做会造成空间复杂度过高,而且要用递归遍历整个子树,我开始就是按照这个思路去做,但感觉很麻烦,最后看到别人提供的思路即求每个物品的期望叠加,简洁清晰,但这就需要在思考时不局限于题目,深刻分析题目从而最终找到解决方案。

————没有什么是停不下来的,除了时间
validate