數學 × 程式編寫比賽 (第七回):我的Python算法

来steemit的时间不长,第一次参加了steemit里的数学程序编写比赛(第七回),用数学方法求解我实在没有耐心去琢磨,有兴趣的可以参考 @tvb这篇文章,佩服她的耐心。

我只考虑了编程的求解算法。假设一点P(x,y)处于1x1的正方形之内,它与各端点连线形成了四个三角形,能够大于120度的只有中间的四个角,这里我利用两个矢量夹角的计算公式:
contest.jpg
cos(a) = u·v / (|u|*|v|)
公式里的u, v都是矢量,u、v之间的小点表示矢量的点积,|u|和|v|表示矢量的长度。

题目要求内角的角度小于120度,也就是角度的余弦值大于-0.5,这样在程序代码里可以不用计算反余弦,提升一点点性能。

四个矢量分别为(-x, -y),(-x, 1-y),(1-x, 1-y),(1-x, -y),需要分别计算相邻的两个矢量的夹角。

这里不考虑性能,只用了笨办法,每次随机选取一点,如果满足条件,count计数增一,模拟上几百万次,按照概率论,模拟得越多,结果越趋近于答案,我用300万试验基本稳定在0.21255,用Python实现的代码如下:

import math
import random

def cosa(u1, v1, u2, v2) :
    len1 = math.sqrt(u1*u1 + v1*v1)
    len2 = math.sqrt(u2*u2 + v2*v2)
    return  (u1*u2 + v1*v2) / (len1 * len2)

def valid(x, y) :
    v1 = cosa(-x, -y, -x, 1 - y)
    v2 = cosa(-x, 1 - y, 1 - x, 1 - y)
    v3 = cosa(1 - x, 1 - y, 1 - x, -y)
    v4 = cosa(1 - x, -y, -x, -y)
    return (v1 > -0.5 and v2 > -0.5 and  v3 >= -0.5 and v4 > -0.5)

count = 0
total = 3000000
for i in range(total) :
    x = random.random()
    y = random.random()
    if valid(x, y) :
         count = count + 1

print(count/total)

---END---


最近还参加了一场故事接龙大赛,被排在第二组第一个出场,憋出800多字的第一回,欢迎围观:一男,二女,三門票 - 第一回-- 第二組


一名爱折腾的程序员,还运营着一个微信公众号:申龙斌的程序人生

H2
H3
H4
3 columns
2 columns
1 column
3 Comments