程序员面试金典

时间:2022-07-26 19:01:55

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

题目描述

在n个顶点的多边形上有n只蚂蚁,这些蚂蚁同时开始沿着多边形的边爬行,请求出这些蚂蚁相撞的概率。(这里的相撞是指存在任意两只蚂蚁会相撞)

给定一个int n(3<=n<=10000),代表n边形和n只蚂蚁,请返回一个double,为相撞的概率。

测试样例:
3
返回:0.75

 

有n个蚂蚁,则有 2 ^ n 种走法, 但是这些走法中只有两种才是不相撞的 (所有蚂蚁同时向左向右爬行), ans = 1 - 1/(2 ^ (n-1)) 

 

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