分类 数学 下的文章

气死禅师的勒洛三角形

昨天在微信上看到一篇文章,很有意思,其中有一个小故事是这样的

青年问禅师:“大师,在单位,他们总嫌我棱角太突出,不合群!”
禅师掏出数根圆柱铺在地上,在上面搁了一块木板,并推动它说:“你看,轮子合作一致才能保持所承载木板的平稳前进,你能找到棱角突出的形状也让木板平稳前进吗?”

青年略一沉吟,默默地掏出一个勒洛三角形。

大师吐血而亡。

勒洛三角形是这样的,它是定宽曲线,用它来搬运东西,不会发生上下抖动

640.jpg

今天又仔细的看了下相关的知识

定宽曲线(英文:Curve of constant width)定义:平面上一凸形封闭曲线,不论如何转动,其宽度永远不变,则称之定宽曲线或恒宽曲线。这里所称的“宽度”是指平行线夹住某封闭曲线时,平行线间的距离。

圆应该就是最常见的定宽曲线了,这个性质应用太广泛了,比如车轮,井盖,轴承等等。而莱洛三角形也是等宽曲线,很多使用圆的场景也可以使用它了,比如井盖,使用莱洛三角形的话,怎么样也不会掉下去的。

通过勒贝格积分可以算出,勒洛三角是定宽曲线所能构成的面积最小的图形,其面积为${1\over2}(\pi - \sqrt3)s^2$,s为定宽宽度。

莱洛三角形的画法也很简单,先画一个等边三角形,然后分别以三个顶点为圆心,三角形边长为半径画三个圆。

图片:“Construction triangle Reuleaux”,作者Frédéric MICHEL - travail personnel (my own work)。采用CC BY-SA 3.0授权,来自维基共享资源

Rouleaux_triangle_Animation.gif

图片:“Rouleaux triangle Animation”,作者Momet - en-wiki。采用CC BY-SA 3.0授权,来自维基共享资源

很明显,它的宽度是三角形的边长。而从下面这个图可以看出,它可以在正方形中无障碍的转动。

勒洛三角形并不能用来做轮子,因为轮子的轴承是固定的,而三角形在旋转的时候,并没有一个固定的中心点到边的距离是不变的,这个中心点是在做圆周运动的,所以会发生颠簸。

geohash查找附近的人

微信、默默等查找附近的人最简单的方法就是遍历一遍,然后使用经纬度计算距离。计算公式是http://en.wikipedia.org/wiki/Haversine_formula

$$havarsin(\frac{d}{R}) = haversin(l_{2} - l_{1}) + cos(l_{1})cos(l_{2})haversin(Δk)$$

其中

$$havarsin(θ) = sin^{2}(\frac{θ}{2}) = \frac{1 - cos(θ)}{2}$$

R是地球半径,$l_{1} l_{2}$是两点纬度,Δk是两点经度的差。

使用Python实现就是

from math import sin, asin, cos, radians, fabs, sqrt

EARTH_RADIUS=6371           # 地球平均半径,6371km

def hav(theta):
    s = sin(theta / 2)
    return s * s

def get_distance(lat0, lng0, lat1, lng1):
    # 经纬度转换成弧度
    lat0 = radians(lat0)
    lat1 = radians(lat1)
    lng0 = radians(lng0)
    lng1 = radians(lng1)

    dlng = fabs(lng0 - lng1)
    dlat = fabs(lat0 - lat1)
    h = hav(dlat) + cos(lat0) * cos(lat1) * hav(dlng)
    distance = 2 * EARTH_RADIUS * asin(sqrt(h))

    return distance

这样的话,每次搜索附近的人,都可以通过公式计算出来附近x km的经纬度范围,然后去数据库查询。这样的缺点就是每次生成的sql语句都不一样,很难缓存,毕竟附近的人不是特别精确的,只要两个人在同一个范围内就可以认为是在一起的。

目前常见的一个解决方案就是geohash,将经纬度映射到一个字符串上。

下面以(39.92324, 116.3906)为例,介绍一下geohash的编码算法。首先将纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90), 如果目标纬度位于前一个区间,则编码为0,否则编码为1。由于39.92324属于(0, 90),所以取编码为1。然后再将(0, 90)分成 (0, 45), (45, 90)两个区间,而39.92324位于(0, 45),所以编码为0。以此类推,直到精度符合要求为止,得到纬度编码为1011 1000 1100 0111 1001。经度也用同样的算法,对(-180, 180)依次细分,得到116.3906的编码为1101 0010 1100 0100 0100。

接下来将经度和纬度的编码合并,奇数位是纬度,偶数位是经度,得到编码 11100 11101 00100 01111 00000 01101 01011 00001。最后,用0-9、b-z(去掉a, i, l, o)这32个字母进行base32编码,得到(39.92324, 116.3906)的编码为wx4g0ec1。

http://code.google.com/p/python-geohash/有一个Python的geohash库,相关的api有

r = encode(50.231, 15.234, precision=5)
print r
print bbox(r)
print expand(r)
"""
u2fvf
{'s': 50.2294921875, 'e': 15.2490234375, 'w': 15.205078125, 'n': 50.2734375}
['u2fvc', 'u2fvg', 'u2fy1', 'u2fy4', 'u2fy5', 'u2fv9', 'u2fvd', 'u2fve', 'u2fvf']
"""

由上面的计算公式可以得到,编码长度为3的时候,一个编码能表示大约155km边长的正方形,4位的时候代表大约40km * 20km的矩形,5位的时候能代表5km * 5km的正方形。

还有一个误差对照表

09185913-9f6f65fc3d3c40ecb3328970831c625c.png

由于GeoHash是将区域划分为一个个规则矩形,并对每个矩形进行编码,目标点在靠近边界的时候,可能会出现:本区域内有一个距离稍远的,但是编码相同,而边界隔壁有一个距离很近的,但是编码不同。解决的思路很简单,我们查询时,除了使用定位点的GeoHash编码进行匹配外,还使用周围8个区域的GeoHash编码,这样可以避免这个问题,也就是上面的expand方法。

现有的GeoHash算法使用的是Peano空间填充曲线,这种曲线会产生突变,造成了编码虽然相似但距离可能相差很大的问题,因此在查询的时候,需要首先筛选GeoHash编码相似的POI点,然后进行实际距离计算。
09185941-53f7b0f1a9b6407eb5cd06b028d98fb8.png
Peano空间填充曲线最大的缺点就是突变性,有些编码相邻但距离却相差很远,比如0111与1000,编码是相邻的,但距离相差很大。

参考
http://blog.charlee.li/geohash-intro/

http://www.cnblogs.com/LBSer/p/3310455.html

http://www.zhihu.com/question/19596950

概率论几个有意思的模型

问题:袋子中有a个黑球,b个白球,现在一只只的摸出来,求第k次摸出黑球的概率。(a ≤ k ≤ a + b)

本题有两个解法,首先考虑是有次序的,也就是排列方法,另一个就是组合解法。

排列方法的样本空间就是对a+b个球进行了全排列,也就是$(a+b)!$,然后填充第k个位置,选一个黑球,有a个选择,然后就是对(a+b-1)的位置放球,有(a+b-1)!种方法。所以得到

$$P = \frac{a × (a + b - 1)!}{(a + b)!} = \frac{a}{a + b}$$

第二种解法就是认为全部的球就两部分,黑的和白的,认为同种颜色的球之间没有区别。先把黑球放好的话,有$C_{a + b}^{a}$种方法。这个事情做完了,剩下的都是白球了。有利场合就是$C_{a + b - 1}^{a - 1}$种。所以

$$P=\frac{C_{a + b - 1}^{a - 1}}{C_{a + b}^{a}}=\frac{a}{a + b}$$

这样的话,最后的结果很重要,结果和k是没有关系的,最终的概率都是一样的,这个也是抽签的模型。这个证明显示抽签的前后顺序是不影响结果的。


现在有n个球,每个球都有相同的概率$\frac{1}{n}$落到N个格子里面(N大于等于n)的每一个格子中,求

  1. 某指定的n个格子中各有一个球的概率P(A)
  2. 任何n个格子中各有一个球的概率P(B)

要注意的是一个格子中可以放多个球。

第一问是先在N个格子中选出n个进行有重复的排列,样本空间就是$N^{n}$,比如第一个有N种方法,第二次还是N个,以后还是。
因为已经指定了n个格子,相当于n个球进行了全排列,有利场合就是$n!$。

第二问因为n个格子是任意的,首先要挑出n个格子,然后对n个球进行全排列。有利场合就是$C_{N}^{n} × n!$。结果是

$$P(B) = \frac{C_{N}^{n} × n!}{N^{n}}=\frac{N!}{N^{n}(N - n)!}$$

实际应用一下,有n个人(n < 365),每个人的生日都不一样的概率就可以套用第二问,每个格子都有一个人,而且只有一个人。n个人中至少两个人生日相同的概率就可以使用1 - P(B)


蒙提霍尔问题

问题详情参考
http://wiki.mbalib.com/wiki/%E4%B8%89%E9%97%A8%E9%97%AE%E9%A2%98

使用Python模拟就好了

# coding=utf-8
import random


# 不改变选择
def do_not_change():
    prize = ["goat", "goat", "car"]
    random.shuffle(prize)
    return prize[random.randint(0, 2)] == "car"


# 不确定改不改变
def random_selection():
    # 不确定改不改变的话,也就是在除去主持人打开的门之后再随机选择一个
    prize = ["goat", "car"]
    random.shuffle(prize)
    return prize[random.randint(0, 1)] == "car"


# 改变选择
def change():
    prize = ["goat", "goat", "car"]
    random.shuffle(prize)
    choice = random.randint(0, 2)
    prize.pop(choice)
    for i in [0, 1]:
        # 主持人选择山羊
        if prize[i] == "goat":
            prize.pop(i)
            break
    # 选择最后一个
    return prize[0] == "car"

count = 0
for i in range(100000):
    if do_not_change():
        count += 1

print u"不改变选择", count / 100000.0

count = 0
for i in range(100000):
    if random_selection():
        count += 1
print u"不确定改不改变选择", count / 100000.0

count = 0
for i in range(100000):
    if change():
        count += 1
print u"改变选择", count / 100000.0

"""
最终结果
不改变选择 0.33098
不确定改不改变选择 0.50006
改变选择 0.6637
"""