bookmark_borderProject Euler 解題筆記 (4) – #184

#184 Triangles containing the origin (難度 75%)

這題題目描述起來很簡單:考慮平面上一些點的集合,這些點滿足:點的座標為整數,以及它們都在一個圓心在原點,半徑為 r 的圓的內部。考慮由這點集當中的點為頂點的三角形,計算圓心 (原點) 在其內部的三角形個數。
對 r=2,一共可以找得到 8 個原點在內部的三角形;r=3 有 360 個,而 r=5 則有 10600 個。試求 r=105 時有多少個。

看起來很簡單,但仔細想下去就會發現很多細節藏在裡面:

  • 首先,點的數量很多:用圓面積估計可以得到半徑 105 的圓內整點數約有三萬四千多個,在其中選三個的選法有近七兆種;
  • 三角形要包含圓心。說起來簡單,但包含這回事並不容易化成條件;
  • 看起來好像有一些對稱性可以用,但這又不是大家都一樣的對稱 (有的翻轉不同,有的翻轉相同等等),要分狀況會很麻煩;
  • 等等。

先來提「包含」這件事好了;因為這題其實是個標準的計算幾何題目。所謂計算幾何,以不那麼精準的懶人包說法就是:把幾何問題座標化的解析算式用電腦程式計算的演算法。畢竟電腦要「看」一個幾何圖形只能用描述它的參數性質去看,一些只要圖畫出來對人來說很直接的判斷,電腦程式都需要進行一些運算才能判定;加上一些幾何上的簡單性質其實很容易出現無理數 (以最常見的直角三角形來說好了,畢氏定理求斜邊會有根號,而角度則就連有理數度都是少數),若沒有特別設計的話數值精確度也會是一個問題。

在計算幾何當中要求一個點是否包在簡單多邊形當中,常用的做法有幾個:

  • 繞多邊形的邊,每次都看該點是否在邊的同一側:想像沿著多邊形開車,結果繞了一圈都發現目標點都在同一邊,那就可以知道這個點在多邊形裡面了。從這個形象化也很容易知道知道這個方法只對凸多邊形有用,不過三角形一定是凸的所以對三角形也算常用。
  • 從點任意發射射線,如果只和多邊形交叉奇數次那就是在裡面:這也是個在圖形上滿直觀的做法。
  • 上一個方法的進階版:計算這個多邊形對所求點的卷繞數,如果不是零那就是在裡面。

等等。

單單只運用這些方式就能輕鬆寫程式檢驗題目給的三個數字,但直上 r=105 時就會卡住了。這才是這題的困難點:點集內有 \(O(r^2)\) 個點,所以選三個點組成的三角形個數有 \(O(r^6)\) 個,全部試過一遍的時間會太久。

Continue reading “Project Euler 解題筆記 (4) – #184”

bookmark_borderProject Euler 解題筆記 (3) – #167

來把題號擺在標題上好了。原本不放的原因是打算一篇可以擠好幾個,不過後來想想會能寫筆記的都應該不是三言兩語能解決的東西的。

#167 Investigating Ulam sequences (難度 75%)

所謂 Ulam sequence 是指這樣的數列:給定開頭兩個正整數 a < b,每次都找大於最後一項的整數當中,能夠唯一地表示為之前數列當中的兩項和的數中最小的那一個。題目給的例子是最簡單的 a=1, b=2 所產生的數列 (OEIS A002858):1, 2, 3, 4, 6, 8, 11, ……。因為 5 = 1+4 = 2+3 有兩種兩項和表示法,所以不在數列中;因此 6 就在數列中了 (只有 2+4 一種)。令這樣的數列第 \(k\) 項記為 \(U(a,b)_k\)。

試求 \(\sum_{n=2}^{10} U(2,2n+1)_k\),其中 \(k=10^{11}\)。

一般化的 Ulam sequence 其實有很多很詭異的性質,例如單就上面提的 a=1, b=2 產生的數列來說:

  • 它是一個完全序列,表示任何正整數都可以表示成數個這個數列中的項的和;
  • 除了開頭三項 1, 2, 3,其他任何連續三項都滿足三角不等式;
  • 在數值方面它有一個很大略的規律:如果把所有正整數排成 216 個一排,點出在數列中的數,會發現它們大致地排成十條帶狀圖,帶與帶之間有個還不錯明顯的空白,也就是數值上大約有個差 21.6 左右的「週期關係」在;
  • 如果只考慮數列本身的話,它也被人發現其傅立葉轉換當中有兩個異常突出的頻率:對這數列的前十億項,存在一個數 \(\theta\approx2.5714474995\),使得這十億項當中除了四個都滿足 \(\cos(\theta a_n)<0\)。

等等。不過這些都無助於我們求出第 1011 項--這個項數實在是太後面了,漸近性質沒辦法精準點到特定的某一項來。

Continue reading “Project Euler 解題筆記 (3) – #167”

bookmark_borderProject Euler 解題筆記 (2)

#152 Writing 1/2 as a sum of inverse squares (難度 65%)

這題躺在我的未解題裡躺很久了:有一陣子我在嘗試從頭開始答題,寫一寫就撞上這題這個軟牆,所以就開始往後亂跳題目 XD 也就是說,除了在約三四百題那附近時有比較集中在一出題就去解之外,其他的解題進度都是這樣散散的,看到有點難的題目就給它拼命跳,所以這題才留著這麼久。

題目很簡單:就如同標題說的,把 1/2 寫成不同整數平方的倒數和。題目敘述給了一個範例:

$$\begin{align}\dfrac{1}{2} &= \dfrac{1}{2^2} + \dfrac{1}{3^2} + \dfrac{1}{4^2} + \dfrac{1}{5^2} +\\
&\quad \dfrac{1}{7^2} + \dfrac{1}{12^2} + \dfrac{1}{15^2} + \dfrac{1}{20^2} +\\
&\quad \dfrac{1}{28^2} + \dfrac{1}{35^2}\end{align}$$

並且給出如果只考慮 2 到 45 的平方倒數的話,連同這個範例一共只有三組解。題目要問的是:如果放大範圍到 2 到 80 的話有幾組解?

之所以是軟牆是因為,2 到 80 這個範圍很微妙的稍微大了一點;這個題目本質上是一個子集和問題,要我們在給定的 79 個元素中選出數個來加到目標 1/2;由於子集和問題是著名的 NP-Complete 問題,所需要的工作量不會比把 79 個數個別選不選所得到的 \(2^{79}\) 種選項逐一嘗試來得好多少。

Continue reading “Project Euler 解題筆記 (2)”

bookmark_borderProject Euler 解題筆記 (1)

既然要來記解題筆記就來順便記一下時不時會做的 Project Euler 好了。這裡的文章應該會一起排進慣例的週三更新當中,所以看到一篇筆記出來並不代表我剛解完這一題,而可能是好幾天前的事了 XD

我做 Project Euler 主要的工具是 Mathematica,因為很多數學相關的東西可以不用我自己寫;只有在一些資料結構用 MMA 不好寫或很需要效率的時候才會轉用 C++ 來寫的。我的 PE 帳號裡登記的使用語言也是 Mathematica。

另外,為了在全文章模式也作點簡單的防雷,每篇在討論的題目我會放在繼續閱讀之上,然後在前面寫一點這題可以公開的東西,例如簡評或我流翻譯等;在繼續閱讀的前一段我會放上我的 Project Euler 簽名圖,那之下就會來開始放雷了。

#168 – Number Rotations (難度 65%)

簡述這題是這樣的:
142857 這個數字,將其個位數放到最前面 (稱為其右旋轉) 得到 714285,而我們發現 714285 是 142857 的 5 倍整。試問,所有具有此種性質--一數為其右旋轉的因數--並且在 10 到 10100 之間的數的總和,其末五位是多少?

這題其實很久以前解過,但因為少考慮了一個東西所以 WA 了不少次,就被我放著了。最近回來重新思考才發現我少考慮的東西是什麼--而說來有趣,題目用 142857 舉例正是讓我掉進這個陷阱的元兇 XD

Continue reading “Project Euler 解題筆記 (1)”