程序员面试金典——7.2碰撞的蚂蚁

Allenlzcoder

于 2018-04-20 10:29:54 发布

阅读量263

点赞数

CC 4.0 BY-SA版权

分类专栏：程序员面试金典题目笔记文章标签： c程序员面试金典碰撞的蚂蚁

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/80015188

程序员面试金典题目笔记专栏收录该内容

79 篇文章

订阅专栏

本文探讨了程序员面试中经典的碰撞蚂蚁问题。通过分析2^n种可能的蚂蚁爬行方案，得出了蚂蚁不相撞的概率为1/(2^(n-1))，进而计算出相撞概率为1减去该值。代码实现采用C++，通过迭代计算得出最终答案。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

程序员面试金典——7.2碰撞的蚂蚁

Solution：按照书上的思路写的
每个蚂蚁有两种爬行选择，共有 $2^n$ 种方案，只有当所有的蚂蚁同时顺时针爬行或逆时针爬行时，才不会相撞，所以不相撞的概率是 $P_0=\frac{2}{2^n}=\frac{1}{2^{n-1}}$ ，相撞的概率 $1-P_0$ 。OK

class Ants {
public:
    double antsCollision(int n) {
        // write code here
        double temp = 1.0;
        for(int i = 1; i < n; i++) 
            temp *= 0.5;
        return 1 - temp;
    }
};