Peienwu's Blog

上課內容

雙連通元件

樹壓平、點雙連通、邊雙連通

SCC強連通元件

LCA（最低共同祖先）

簡介

克卜勒第三運動定律說明公轉週期的平方與行星到太陽的平均距離三次方成正比。若是行星以橢圓軌道繞行太陽，則行星到太陽的平均距離 $\overline d$ 會是近日點距 $r_1$ 加上遠日點距 $r_2$ 的平均，也就是橢圓的半長軸，讓我十分好奇該如何證明這件事！

所要做的是就是將橢圓圓周上的每一點，到太陽的距離進行積分後取平均。

簡介

上週補習班開始教「平面方程式」，有一題範例感覺特別的酷，題目如下：

空間坐標系中，有一平面鏡E，一雷射光線經過點$A(1,-1,2)$射向鏡面E上的點$B(0,1,0)$，反射又經過點$C(4,-3,2)$，試求平面E的方程式為何？

解法大概就是利用菱形對角線平分的概念求出平面方程式！由這一題延伸，我想看看當改變已知平面的各項參數時，反射光的向量會有怎麼樣的變化，於是就嘗試用VPython模擬出來！

Manim安裝

Manim is an animation engine for explanatory math videos.

利用Manim可以生成許多數學類的動畫影片、以及製作一些動畫模擬！

我是利用Mac安裝Manim，只要按照這一篇的說明一步步完成即可，不要上網找教學影片，因為很多都是過時的，在安裝上會出現一些問題。

至於使用教學的部分，可以參考這一篇官方使用手冊。Manim總共有三種版本，建議使用Manim Community比較方便，資源比較多！

簡介

Bertrand Paradox是Bertrand他在他的一本書中提到關於機率論的悖論，他以「在圓上產生隨機的弦」來說明當沒有嚴謹的定義好產生隨機的「方法」，就有可能產生許多合理但結果卻完全不同的答案。

悖論如下：給定一個平面上的圓，內接一個邊長為 $T$ 的正三角形。接著隨機產生園內的一條弦，想問這條弦的長度大於 $T$ 的機率有多大？

題序

從前從前有一個人名叫thanksone，他與他的兩個哥哥thankstwo以及thanksthree以及他的弟弟thankszero一起開了一家「牛牛牧場」，用來養牛以及一些奇怪的東西。

有一天，他發現他的牛牛少了很多隻，不知道是跑去了哪裡，他很難過，因此他想要建造一個圍籬，讓所有牛牛都跑不出去。於是他拜託他的兩個哥哥thankstwo以及thanksthree去市集買了$n$個用來架設圍籬的木樁，並要求他們把這些木樁架設在他指定的位置。

這篇文章的主題有以下：

1. 歐拉路徑、迴路（七橋問題）
2. 漢米頓路徑、迴路
3. 最短路徑演算法（Dijkstra,Bellman-Ford,Floyd-Warshall）
4. 旅行業務員問題（TSP）

問題描述

對於婚姻匹配問題有以下描述：對於一個群體來說，男生女生都要尋找自己最心儀的對象。而一個「穩定」的群體我們把他定義為在婚姻中的每一對男女都沒有比目前的配對方式更好的組合。

下圖為四男（小寫字母）以及四女（大寫字母）對異性的偏好順序，第一格代表男生對女生的偏好順序，第二格則代表女生對男生的偏好順序。

CSES Geometry

• Point Location Test
• Line Segment Intersection
• Polygon Area
• Point in Polygon
• Polygon Lattice Points
• Minimum Euclidean Distance
• Convex Hull

多元選修課提到歐拉函數 $\phi$，想說蠻有趣的可以跟程式結合一下，看會發生什麼有趣的事情！

定義與公式

對於一個正整數 $n$，歐拉函數 $\phi(n)$ 表示閉區間 $[1,n]$ 中的正整數與 $n$ 互質的個數。定義序列 $p$ 為所有正整數 $n$ 質因數分解之後的數字。在不失一般性的假設序列 $p$ 的長度為 $r$，以質因數分解表示 $n$ 即為 $n = p_1^{k_1}\cdot p_2^{k_2}\cdots p_r^{k_r}$，則歐拉函數滿足以下關係式：