首页 > 试题广场 >

碰撞的蚂蚁

[编程题]碰撞的蚂蚁
  • 热度指数：7370 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

平面上n个顶点的多边形上有n只蚂蚁，这些蚂蚁同时开始沿着多边形的边爬行（一个顶点一只蚂蚁，蚂蚁速度都一样）。现给定一个int n(3<=n<=10000)，代表n边形和n只蚂蚁，编写函数返回会有蚂蚁相撞的概率double值。

测试样例： 
3
返回：0.75
算法知识视频讲解
添加回答
超小白头像 超小白 
class Ants {
public:
    double antsCollision(int n) {
        // write code here
        return (1.0-(1.0/(1<<(n-1))));
    }
};
分析的如上述大牛缩写，计算用位运算会更快，代码也更简洁，跟大家分享
发表于 2016-06-06 22:21:23 回复(3)
Python
华科平凡头像 华科平凡

python solution

        return 1-2.0/2**n
发表于 2017-10-31 16:19:16 回复(0)
粉色曼陀罗的花语头像 粉色曼陀罗的花语
这尼玛，不科学呀！ n达到1000了意味着绝对会超啊！
发表于 2015-09-15 20:51:17 回复(0)
MichaelTim头像 MichaelTim 
//要想没有相撞，只有所有的蚂蚁朝一个方向走，要么顺时针，要么逆时针
//每个蚂蚁都有两个选择，所有情况2的n次方种，其中满足条件的2种
class Ants {
public:
    double antsCollision(int n) {
        return 1.0 - 1.0/(1 << (n-1));
    }
};

发表于 2016-08-25 10:13:32 回复(1)
九城城主头像 九城城主
思路：每个蚂蚁爬行的方向都有两个，即围绕多边形顺时针爬和逆时针爬，因此n个蚂蚁爬行的方法有2^n种。
只有当所有的蚂蚁按照同一个方向爬行才能保证所有的蚂蚁都不相撞，只有两种方法--都按逆时针或顺时针方向爬行。
所以相撞的概率为1 - （double）2 / (2 ^n)
代码如下所示:
发表于 2015-08-18 10:49:48 回复(0)
InGodWeTrust头像 InGodWeTrust 
import java.util.*;

public class Ants {
    public double antsCollision(int n) {
        //所有蚂蚁同向时不会发生碰撞
     	return 1-Math.pow(0.5, n-1);   
    }
}

发表于 2017-06-08 17:34:11 回复(0)
Neway头像 Neway 













	class Ants {





	public:





	    double antsCollision(int n) {





	        double result = 1;





	        while(n > 1) {





	            result *= 0.5;





	            --n;





	        }





	        return 1 - result;





	    }





	};

发表于 2017-02-13 20:59:20 回复(0)
RainDrop头像 RainDrop 
import java.util.*;

public class Ants {
    public double antsCollision(int n) {
        return 1.0 - 1.0/(1 << (n-1));
    }
//蚂蚁有两个方向可以爬 所以需要乘上2
编辑于 2016-08-13 23:13:41 回复(0)
Java
牛客942337361号头像 牛客942337361号
import java.util.*;

public class Ants {
    public double antsCollision(int n) {
        // 当且仅当蚂蚁保持同向时才不会发生碰撞
        return 1- Math.pow(2,-n+1);
    }
}
发表于 2023-05-06 16:59:53 回复(0)
C++
好菜啊我头像 好菜啊我 
/*
思路：排除

所有可能的情况 = 相撞的情况 + 不相撞的情况

相撞 = 所有-不撞

不撞：所有蚂蚁都向左或向右

*/
class Ants {
public:
    double antsCollision(int n) {
        // write code here
        double count = 1;
        //假设所有都向左，每只向左的概率是0.5
        while(n--){
            count *= 0.5;
        }
        //返回的时候还需要减去向右的概率
        return (1-2*count);
    }
};

发表于 2023-04-13 15:29:33 回复(0)
Java
牛客47601710号头像 牛客47601710号

    //任何多变行都只有在蚂蚁走同一方向才不会相撞，走同一方向有两种可能，
    //所以任何多边行下所有可能是2的n次方
    public double antsCollision(int n) {
        // write code here
        return 1 - 2.0/(2<<(n-1));
    }
发表于 2022-12-29 14:14:00 回复(0)
liabi4hao头像 liabi4hao
double antsCollision(int n) {
        // write code here
        /*
        * 思路：每个蚂蚁爬行的方向都有两个，
        * 即围绕多边形顺时针爬和逆时针爬，因此n个蚂蚁爬行的方法总共有2^n种。
        * 只有当所有的蚂蚁按照同一个方向爬行才能保证所有的蚂蚁都不相撞，
        * 总共只有两种方法--都按逆时针或顺时针方向同向爬行。
        * 反向思考：如果把蚂蚁不相撞的概率剔除掉，剩下的就是相撞的。
        * 题目中无此信息，按大概率推断两者同概率，所以是0.5n*2，然后1-0.5n*2就可以了。
        */
        return 1.0-pow(0.5,(double)n-1.0);
    }
发表于 2022-03-09 11:19:16 回复(0)
真的会谢的我很爱吃香菜头像 真的会谢的我很爱吃香菜
我觉得应该说明是正n边形 
class Ants {
    public double antsCollision(int n) {
        return (double)(1.0 / (1 << (n-1)));
    }
}



发表于 2021-03-10 10:37:25 回复(0)
cl、头像 cl、 
import java.util.*;

public class Ants {
    public double antsCollision(int n) {
        // write code here
        double N=0.5;// 蚂蚁往一个方向走的概率
        return 1-(Math.pow(N,n)*2);
    }
}

发表于 2020-10-22 08:36:51 回复(0)
C/C++
字节内推小跟班头像 字节内推小跟班 
class Ants {
public:
    double antsCollision(int n) {
        return 1 - 2 * pow(0.5, n);
    }
};

发表于 2020-04-27 23:40:50 回复(0)
Java
天山剑客头像 天山剑客 
import java.util.*;

public class Ants {
    public double antsCollision(int n) {
        // write code here
    	double res = 0.0;
    	res = 1 - 2 / Math.pow(2, n);
    	return res;
    }
}

发表于 2019-12-13 17:16:49 回复(0)
cpppppp头像 cpppppp 
// 第1只方向任意， 剩下 n-1的方向就固定了。
// 相撞 = 1- 不相撞
// 一行搞定

class Ants {
public:
    double antsCollision(int n) {
        // write code here
        return 1- pow(0.5,n-1);
    }
};

发表于 2019-07-02 22:56:05 回复(0)
C/C++
nbgao头像 nbgao 
class Ants {
public:
    double antsCollision(int n) {
        return 1-pow(0.5,n-1);
    }
};

发表于 2019-02-26 01:38:43 回复(0)
马什么梅呀头像 马什么梅呀 
class Ants {
public:
    double antsCollision(int n) {
        // write code here
        double a = 1.0, all=1.0;
        for(int i=1;i<=n;i++){
            all = all*2;
        }
        return (all-2)/all;
    }
};

发表于 2019-01-04 15:13:40 回复(0)
C/C++
蛟龙吐火球丰头像 蛟龙吐火球丰 
class Ants {
public:
    double antsCollision(int n) {
        // write code here

        return 1.0-1.0/pow(2,n-1);
    }
};
发表于 2018-06-30 10:36:13 回复(0)
提交观点

问题信息

位运算 数学 基础数学
难度：
53条回答 12537浏览

热门推荐

通过挑战的用户

查看代码

相关试题

碰撞的蚂蚁

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号