从零开始的算法题生活 (二)

引言

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

题目描述

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;
}

结束语

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