「数学or算法？」每周学习心得 & 本周更新计划
「数学or算法？」每周学习心得 & 本周更新计划
「数学 \approx 算法?」
素材：Jonathan Borba from unsplash
刚刚过去的是：假借「作业」这个理由不去更新的第三周。但也是上大学以来，从未有过的、无比舒适的一周。
这一周，技术方面有什么值得讨论的呢？大概两点：
•我已经坚持 每周至少五道 LeetCode 题目 一个月之久：这有用吗？会给生活造成额外负担吗？•一道简化后的数学题目，我在数学频道 『三蓝一棕』 所见，我将在这里简单讨论：•不使用数学推导，如何利用仿真求解？用 python 实现；•python 的仿真过程可视化（一个很好的 python 入门实例）；•何谓「巧妙」的数学证明？
每周五道 LeetCode
大概从十一月末开始，每周5道算法题目。总结下来，算法题这个东西，还真的是熟能生巧：
•要见识过各种解题套路，从而获得把新问题拆解、转换成经典题目的能力•代码实现的能力：比如我喜欢用 C++ 11 写算法题，那么我就要借此机会熟悉 C++ 11 的各种容器、语法规则
github.com/PiperLiu/ACMOI_Journey
我开了一个 repo 放在 GitHub 上：
•https://github.com/PiperLiu/ACMOI_Journey
会记录每道题目的心得，总结一下方法论、容器的使用技巧等等。
目前我才研一，离找工作还比较远，那么，不得不问自己：如此做题，负担大吗？有必要吗？收获如何呢？
•负担大吗？ 负担不是很大，一般来讲，我每天早上到图书馆，先花一个小时以内做一道题，清神醒脑；如果今天比较忙，那则挑一道简单的题目•有必要吗？ 必要性不是很强，但确实有趣，算是一个小爱好•收获如何？ 除了从算法本身得到收获，我还很注重规范，比如：一般将链表中的哑节点命名为dummy，涉及到多个指针时一般命名为hair、head、next、prev、tail等
有趣的数学
在 3Blue1Brown 看到一个有趣的题目：
•https://www.bilibili.com/video/BV17W411a74F
我抽取了这道题的简化版本：『在一个圆上随机抽取三个点，构成一个三角形，该三角形覆盖圆心的概率是多少呢？』
第一种思路，我们可以通过大量的计算机仿真得出近似答案。这种思路类似：抛一个均匀的硬币一万次，将有五千次左右正面朝上，五千次左右背面朝上。
渲染效果
我写了两套代码，放在了 GitHub 中：
•https://github.com/PiperLiu/interesting-python3/tree/master/mathematics-python/triangle_3points
第一套，是进行大量数值实验，我这里进行了30组实验，每组实验采样3000次，生成如下图像。
纵轴：累计概率
如上纵轴为累积概率：覆盖圆心次数除以采样总次数。
收敛于0.25
可以看出累积概率将收敛于0.25。
代码只有寥寥 67 行。
import numpy as npimport matplotlib.pyplot as pltfrom tqdm import trangeplt.style.use('ggplot')R = 1xc = 0yc = 0def generate_1_point(): # polar coordinates theta = np.random.random() * np.pi * 2 return thetadef polar_to_cartesian(theta): x = R * np.cos(theta) y = R * np.sin(theta) return x, ydef is_center_in(theta_list): x1, y1 = polar_to_cartesian(theta_list[0]) x2, y2 = polar_to_cartesian(theta_list[1]) x3, y3 = polar_to_cartesian(theta_list[2]) vec_1 = np.array([x2 - x1, y2 - y1]) vec_2 = np.array([x3 - x2, y3 - y2]) vec_3 = np.array([x1 - x3, y1 - y3]) # test vec # 1 vec_t = np.array([xc - x1, yc - y1]) flag1 = np.cross(vec_1, vec_t) if flag1 == 0: return True # 2 vec_t = np.array([xc - x2, yc - y2]) flag2 = np.cross(vec_2, vec_t) if flag2 == 0: return True # 3 vec_t = np.array([xc - x3, yc - y3]) flag3 = np.cross(vec_3, vec_t) if flag3 == 0: return True if (flag1 > 0 and flag2 > 0 and flag3 > 0) or \ (flag1 < 0 and flag2 < 0 and flag3 < 0): return True return Falsedef main(): CNT = 3000 list_30 = [] for _ in trange(30): cnt = 0 per_list = [] for i in range(CNT): theta_list = [generate_1_point() for _ in range(3)] if is_center_in(theta_list): cnt += 1 # print("{:.5f}".format(cnt / (i + 1))) per_list.append(cnt / (i + 1)) list_30.append(per_list) for per_list in list_30: plt.plot(per_list) plt.show()if __name__ == "__main__": main()另外，渲染代码如下。两套代码都可独立运行。
/*
* 提示：该行代码过长，系统自动注释不进行高亮。一键复制会移除系统注释
* import numpy as npimport matplotlib.pyplot as pltimport sysimport pygamefrom pygame.locals import *plt.style.use('ggplot')R = 1xc = 0yc = 0pygame.init()pygame.display.set_caption("Piper蛋窝")screen = pygame.display.set_mode((360, 240))fcclock = pygame.time.Clock()SCALE = 80FPS = 10total_score = 0isin_socre = 0def generate_1_point(): # polar coordinates theta = np.random.random() * np.pi * 2 return thetadef polar_to_cartesian(theta): x = R * np.cos(theta) y = R * np.sin(theta) return x, ydef is_center_in(theta_list): x1, y1 = polar_to_cartesian(theta_list[0]) x2, y2 = polar_to_cartesian(theta_list[1]) x3, y3 = polar_to_cartesian(theta_list[2]) vec_1 = np.array([x2 - x1, y2 - y1]) vec_2 = np.array([x3 - x2, y3 - y2]) vec_3 = np.array([x1 - x3, y1 - y3]) # test vec # 1 vec_t = np.array([xc - x1, yc - y1]) flag1 = np.cross(vec_1, vec_t) if flag1 == 0: return True # 2 vec_t = np.array([xc - x2, yc - y2]) flag2 = np.cross(vec_2, vec_t) if flag2 == 0: return True # 3 vec_t = np.array([xc - x3, yc - y3]) flag3 = np.cross(vec_3, vec_t) if flag3 == 0: return True if (flag1 > 0 and flag2 > 0 and flag3 > 0) or \ (flag1 < 0 and flag2 < 0 and flag3 < 0): return True return Falsedef draw_static(): pygame.draw.circle(screen, (255, 255, 255), (360 // 3, 240 // 2), R * SCALE, 3) pygame.draw.circle(screen, (255, 255, 255), (360 // 3, 240 // 2), 5)def draw_dynamic(theta_list): global isin_socre xc_draw = 360 // 3 yc_draw = 240 // 2 x1, y1 = polar_to_cartesian(theta_list[0]) x2, y2 = polar_to_cartesian(theta_list[1]) x3, y3 = polar_to_cartesian(theta_list[2]) x1, y1 = x1 * SCALE + xc_draw, y1 * SCALE + yc_draw x2, y2 = x2 * SCALE + xc_draw, y2 * SCALE + yc_draw x3, y3 = x3 * SCALE + xc_draw, y3 * SCALE + yc_draw # is in flag = is_center_in(theta_list) if flag: isin_socre += 1 # draw r_point = 6 l_width = 4 inColor_r = (123, 104, 238) inColor_l = (147, 112, 219) notinColor_r = (199, 21, 133) notinColor_l = (218, 112, 214) if flag: pygame.draw.circle(screen, inColor_r, (360 // 3, 240 // 2), 5) pygame.draw.circle(screen, inColor_r if flag else notinColor_r, (int(x1), int(y1)), r_point) pygame.draw.circle(screen, inColor_r if flag else notinColor_r, (int(x2), int(y2)), r_point) pygame.draw.circle(screen, inColor_r if flag else notinColor_r, (int(x3), int(y3)), r_point) # line pygame.draw.line(screen, inColor_l if flag else notinColor_l, (int(x1), int(y1)), (int(x2), int(y2)), l_width) pygame.draw.line(screen, inColor_l if flag else notinColor_l, (int(x2), int(y2)), (int(x3), int(y3)), l_width) pygame.draw.line(screen, inColor_l if flag else notinColor_l, (int(x3), int(y3)), (int(x1), int(y1)), l_width)def draw_score(): global total_score global isin_socre WHITE = (255, 255, 255) text_1 = pygame.font.Font('freesansbold.ttf', 30) text_1_surface = text_1.render(str(isin_socre), True, WHITE) text_1_rect = text_1_surface.get_rect() text_1_rect.center = (360 // 20 * 13, 240 // 10 * 4) screen.blit( text_1_surface, text_1_rect ) text_2 = pygame.font.Font('freesansbold.ttf', 30) text_2_surface = text_2.render(str(total_score), True, WHITE) text_2_rect = text_2_surface.get_rect() text_2_rect.center = (360 // 20 * 13, 240 // 10 * 6) screen.blit( text_2_surface, text_2_rect ) pygame.draw.line(screen, WHITE, (360 // 20 * 12, 240 // 10 * 5), (360 // 20 * 14, 240 // 10 * 5), 3) text_3 = pygame.font.Font('freesansbold.ttf', 30) text_3_surface = text_3.render('=', True, WHITE) text_3_rect = text_3_surface.get_rect() text_3_rect.center = (360 // 20 * 15, 240 // 10 * 5) screen.blit( text_3_surface, text_3_rect ) text_4 = pygame.font.Font('freesansbold.ttf', 30) text_4_surface = text_4.render('{:.2f}'.format(isin_socre / total_score), True, WHITE) text_4_rect = text_4_surface.get_rect() text_4_rect.center = (360 // 40 * 35, 240 // 50 * 31) screen.blit( text_4_surface, text_4_rect )def draw(theta_list): screen.fill((0, 0, 0)) draw_static() draw_dynamic(theta_list) draw_score() fcclock.tick(FPS) pygame.display.update()def main(): global total_score pygame.init() while True: for event in pygame.event.get(): if event.type == QUIT: sys.exit() elif event.type == KEYDOWN: if event.key == K_ESCAPE: sys.exit() theta_list = [generate_1_point() for _ in range(3)] total_score += 1 draw(theta_list)if __name__ == "__main__": main()
*/这里有个小技巧：如何判断一个点是否在三角形（多边形）内呢？使用向量的叉乘（which is 基础线性代数中常被忽略的部分）判断正负即可。
话说回来，如何使用数学的方法进行证明呢？其实，最为精妙的地方在于 想到这种方法的过程 ，而这在原视频（BV17W411a74F）中已经很明确地被说明。
www.bilibili.com/video/BV17W411a74F
我仅谈谈我的收获：
•遇到复杂的问题，从较为简化的问题入手（本题目中，要求从球上任取四点；那么首先从圆上任取三点思考）•数学上的「等价」操作：随机抽取三点，可以等价于先取一点固定住，接着再取另一点等...•此外，应该提取问题的共性：•如上提，注意到，固定住P1与P2点，之后分别绘制出分别经过P1与P2的直径，这两条直径将圆分割成了4个圆弧；注意到，只有当P3处于远端的圆弧时，三角形才覆盖圆心•但是，圆弧长度、P3位置都是不确定的量，计算比较复杂•可以等价取点的过程：首先假设我们已经取定了P3，接着任取了两条直径，这三者都是任取的；此时，针对两条直径，分别取一个端点，作为P1与P2，此时P1与P2组合一共有4种，且只有如图的四种，而只有一种组合带来的三角形时符合条件的，因此概率 1 / 4 = 0.25；具体解释如下图
录制自：BV17W411a74F