We randomly distribute n points on the circumference of a circle. What is the probability that they will all fall in a common semi-circle?
我们先用程序模拟一下这个过程,看看结果会是什么?
算法思想:我们先定义一个点的最大值,然后随机生成N个点,之后对这N个点进行排序,定义两点之间的最大距离为max_distance,把它的初始值设置为最小值点+最大值-最大值点,然后遍历所有点,求的相邻两点之间的最大值,如果max_distance大于半圆周长,说明这些点在同一半圆内。
代码清单:
import java.util.Arrays; import java.util.Random; public class Npoints { /** * @param args */ public static void main(String[] args) { int m = 10000; int count; Npoints robot = new Npoints(); for(int n = 1; n <= 8; n++){//一共测试n个点 count = 0; for(int i = 0; i < m; i++){//每个点做m次测试 if(robot.judge(n) == true){ count++; } } System.out.println("n=" + n + "时,在同一半圆的概率为:" + count*1.0/m); } } private boolean judge(int n) { int points = 10000;//点的最大值 int half = points >> 1; Random r = new Random(); int[] array = new int[n+1]; for(int i = 1; i <= n; i++) array[i] = r.nextInt(points) + 1; Arrays.sort(array); int max_distance = array[1] + points - array[n]; for(int i = 1; i < n; i++){ if(array[i+1] - array[i] > max_distance) max_distance = array[i+1] - array[i]; } return max_distance >= half; } }
输出:
n=1时,在同一半圆的概率为:1.0
n=2时,在同一半圆的概率为:1.0
n=3时,在同一半圆的概率为:0.7517
n=4时,在同一半圆的概率为:0.4955
n=5时,在同一半圆的概率为:0.3131
n=6时,在同一半圆的概率为:0.1919
n=7时,在同一半圆的概率为:0.1095
n=8时,在同一半圆的概率为:0.0601
通过上面的模拟结果,可以看出随着n的增大,概率呈指数递减,并且通过P(1)=P(2)=1,猜测出它的结果可能为
n / 2^(n-1),通过多次验证,验证了这个结果的正确性。之后我花了一下午的时间试图对这个问题进行数学证明,不过很遗憾,几次尝试都是错误的解释或证明。
最后查到了原题作者对此问题的数学证明,见识下作者强悍的数学功力。
在求解的过程中,我还发现了一个有趣的现象:对n个点排序后,如果认为最大值点-最小值点 < 半圆周长 的话,那么它的结果将是第n+1个点的概率。
==================================================================================================
作者:nash_ 欢迎转载,与人分享是进步的源泉!
转载请保留原文地址:http://blog.csdn.net/nash_/article/details/8547278
===================================================================================================