C语言实验作业选做题I-游戏问题（完全二叉树）

C语言实验作业选做题I-游戏问题（完全二叉树）

于2020年5月31日2020年5月31日由Sukuna发布

某游戏规则中，甲乙双方每回合的战斗总是有一方胜利，一方失败。失败后要把自己的体力值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这样来的，到了叶结点就弹栈，就进入上一层根节点的右子树。右子树遍历完了就继续弹栈，到上上结点的右子树，如此循环。这也跟树的前序遍历差别

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

如有问题欢迎在评论区指正，谢谢！