次数的期望值

题目描述

小嗨玩电子游戏。 每当他在游戏中完成任务时，小嗨都有机会获得一个传奇的物品。
一开始概率为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

思路

构造二叉树，每个节点都有两个子节点，一个表示获得了奖励，另一个表示没得到奖励。
每个节点维护四个属性：获得的奖励数，到达该节点需要的概率，该节点的深度（即已经尝试的次数），到达该节点已经失败了的次数
按照题意，递归创建该二叉树
递归终止条件：
当节点的奖励数达到要求时返回
再递归遍历二叉树，根据每个节点的概率和叶子节点的深度即可求出最后的期望值。

代码

import java.awt.image.RescaleOp;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

import sun.java2d.pipe.SpanIterator;

class Node{
	public int num;
	public double possible;
	public Node left;	// 成功
	public Node Right;
	public int depth;
	public int failTime;
	public Node(int num, double possible, int depth, int faliTime) {
		this.num = num;
		this.possible = possible;
		this.depth = depth;
		this.failTime = faliTime;
	}
}
public class Main {
	private static int N;
	private static double P;
	private static double Q;
	public static float res = 0;
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		P = scanner.nextDouble();
		Q = scanner.nextDouble();
		
		Node root = new Node(0, 1, 0, 0);
		root.left = new Node(root.num+1, P, 1, 0);
		root.Right = new Node(root.num, 1-P, 1, 1);
		
		constructLeft(root.left);
		constructRight(root.Right);
		
		getPossible(root, 1);
		
		System.out.println(Main.res);
	}
	private static void getPossible(Node root, float single) {
		if(root == null ) {
			return;
		}
		if(root.num <= N) {
			single *= root.possible;
		}
		if(root.num == N) {
			single *= root.depth;
			res += single;
			return;
		}
		getPossible(root.left, single);
		getPossible(root.Right, single);
	}
	private static void constructLeft(Node root) {
		if(root.num == N) {
			return;
		}
		root.left = new Node(root.num+1, P/(2*root.num), root.depth+1, 0);
		root.Right = new Node(root.num, 1-(root.left.possible), root.depth+1, root.failTime+1);
		constructLeft(root.left);
		constructRight(root.Right);
	}
	private static void constructRight(Node root) {
		if(root.num == N) {
			return;
		}
		if(root.possible+Q*root.failTime >= 1) {
			
			root.left = new Node(root.num+1, 1, root.depth+1, 0);
			constructLeft(root.left);
		}else {
			root.left = new Node(root.num+1, root.possible+Q*root.failTime, root.depth+1, 0);
			root.Right = new Node(root.num, 1-(root.left.possible), root.depth+1, root.failTime+1);
			constructLeft(root.left);
			constructRight(root.Right);
		}
	}
}

考差点

• 递归
• 二叉树