Ants

https://www.cnblogs.com/yunlambert/p/9370003.html

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

3
返回：0.75

解法

这道题考察数学的，每只蚂蚁都可以选择走临近的两条边其中的一条，所以总共有2n$2^n$种情况。所有蚂蚁不相撞的的情况为都朝，向同一个方向，要么顺时针、要么逆时针，两种情况，所以最后拿1一减就行了。

    double antsCollision(int n) {
        // write code here
        if(n<3) return 0;
        return (1-2/pow(2,n));
    }

https://blog.csdn.net/HelloZEX/article/details/81162369

思路：每个蚂蚁爬行的方向都有两个，即围绕多边形顺时针爬和逆时针爬，因此n个蚂蚁爬行的方法有2^n种。

只有当所有的蚂蚁按照同一个方向爬行才能保证所有的蚂蚁都不相撞，只有两种方法--都按逆时针或顺时针方向爬行。

所以相撞的概率为1 - （double）2 / (2 ^n)