碰撞的蚂蚁 牛客网 程序员面试金典 C++ Java Python

碰撞的蚂蚁 牛客网 程序员面试金典 C++ Java Python

• 题目描述

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

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

• 测试样例：

• 3

• 返回：0.75

C++

class Ants {
public:
//run:4ms memory:484k
double antsCollision(int n) {
int sum = 1;
for (int i = 0; i < n; i++)
sum = 2*sum;
return 1 - (double)2/sum;
}
};

Java

import java.util.*;public class Ants {
//run:62ms memory:10584k
public double antsCollision(int n) {
int sum = 1;
for(int i=0;i<n;i++)
sum = 2 * sum ;
return (1 - (double)2/sum);
}
}

Python

class Ants:
#run:32ms memory:5736k
def antsCollision(self, n):
sum = 1.0
for i in range(n):
sum = 2 * sum
return 1 - 2/sum;