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

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

我只考虑了编程的求解算法。假设一点P(x,y)处于1x1的正方形之内，它与各端点连线形成了四个三角形，能够大于120度的只有中间的四个角，这里我利用两个矢量夹角的计算公式：

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多字的第一回，欢迎围观：一男，二女，三門票 - 第一回-- 第二組

---

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