题目如下：
这道题难点不仅在于正确理解题意，判断递归条件，更在于用数学方法推出解决公式。因为N最大为1百万，而内存只有256MB, 所以暴力递归肯定会超时，超空间。
不过，我才疏学浅，又没有大量时间去深究，所以只写出了暴力递归算法。进一步优化的话，可以考虑P在迭代很久后会变为0这一事实，也许可以进一步节省时空消耗。
下面给出算法，由于我注释写的很详细，这里就不进一步解释了。
import java.util.Scanner;
public class Main { static int P;
static int Q;
static int N; static double result = 0; /**
*
* @param num 当前获得宝物个数，初始化为0
* @param arrayProb 保存每次路径参数
* @param prob 当前路径成功概率，初始化为0
* @param pathLen 当前路径长度，初始化为0
* @param p 初始成功概率，初始化为P
*/
public static void getPath(int num,int[] arrayProb ,int prob, int pathLen, int p){
if (num < N)
{
//首先递归左子树，也就是成功路径子树,成功只有三种情况
if (prob >= 100){
arrayProb[pathLen] = 100;
getPath(num+1, arrayProb, 0, pathLen+1, (int)(p/Math.pow(2,num+1)));
}else if(prob > 0){
arrayProb[pathLen] = prob;
getPath(num+1,arrayProb,0, pathLen+1, (int)(p/Math.pow(2,num+1)));
} else if (p > 0){
arrayProb[pathLen] = p;
getPath(num+1, arrayProb, 0, pathLen+1, (int)(p/Math.pow(2,num+1)));
} //再遍历同层右子树，也就是失败路径概率。prob<100，才有失败可能。
if (prob < 100 && p < 100) {
int tmp;
if(prob == 0){//只有第一次或者成功后prob才会为0
tmp = 100 - p;
prob = p;
}else {
tmp = 100 - prob;
}
arrayProb[pathLen] = tmp;
getPath(num, arrayProb, prob + Q, pathLen + 1,p);
}
} else{
double tmp = 1;
for (int i = 0; i < pathLen; i++) {
tmp *= 0.01 * arrayProb[i];
System.out.printf(arrayProb[i] + " ");
}
System.out.println();
tmp *= pathLen;
result += tmp;
}
} public static void main(String[] args) {
// write your code here
int[] array = new int[100000];
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()){
result = 0;
P = scanner.nextInt();
Q = scanner.nextInt();
N = scanner.nextInt();
getPath(0,array,0,0,P);
System.out.printf("%.2f", result);
}
}
}