某游戏规则中,甲乙双方每回合的战斗总是有一方胜利,一方失败。失败后要把自己的体力值1/4交给胜利的一方。

现在已知双方开始时的体力值:甲1000,乙2000.假设双方战斗胜率各为p。双方经过4回合的战斗,双方体力值之差abs小于1000的概率

Sample Input

0.5

Sample Output

0.625

代码:

#include<stdio.h>
#include<math.h>
#define N 4
double p = 0.5;//p表示甲赢的概率是0.5

double fun(double x, double y, int cur, double k) {
    double sum = 0;
    if (cur == N) {
        if (fabs(x - y) < 1000)
            sum += k;
        return sum;
    }
    sum += fun(x - x / 4, y + x / 4, cur + 1, k * (1 - p));//甲输掉比赛
    sum += fun(x + y / 4, y - y / 4, cur + 1, k * p);
    return sum;
}
int main() {
    printf("%lf\n", fun(1000, 2000, 0, 1));
    return 0;
}
这里给出了一个思考路径

每个结点封装了这些东西:层数,甲乙血量,从根节点到该结点的概率k,还有一个神秘的变量就叫做sum

上面的代码给出了一个深度搜索的示例,通过前序遍历来构建这个树:结点一进入Stack中就立刻对该结点进行搜索。搜索的结果存进一个叫做sum的变量里面,然后对sum进行汇总求和。
对于非叶结点:比如说上图第7号结点的sum=A结点sum+B结点sum
对于叶结点:A结点的sum就是做个判断,如果血量差满足题目要求:sum=概率k,如果不满足:sum=0
再看代码:
sum += fun(x – x / 4, y + x / 4, cur + 1, k * (1 – p));//甲输掉比赛
sum += fun(x + y / 4, y – y / 4, cur + 1, k * p);
这两行代码就是递归,每一次递归就开一层Stack,到叶结点就停止,弹栈,从左到右,遍历顺序我在这分析一下:
首先根节点进入左子树,再进入左子树的左子树,因为这个是完全二叉树,没到规定层数完全不担心子树指向NULL的情况。顺序是:1->3->7->A->B->8->C->D这样来的,到了叶结点就弹栈,就进入上一层根节点的右子树。右子树遍历完了就继续弹栈,到上上结点的右子树,如此循环。这也跟树的前序遍历差别

总之这是一个简单的数据结构的题目,当然这道题完全可以脱离树的结构来做,因为这个数据量较小,用暴力的方法也不会慢很多。

如有问题欢迎在评论区指正,谢谢!

最后修改日期:2020年5月31日

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。