2015年6月4日 星期四
2015年6月3日 星期三
2015年6月2日 星期二
2015年5月25日 星期一
2015年5月14日 星期四
Totient Summatory Function
Reference: http://mathworld.wolfram.com/TotientSummatoryFunction.html
例子:[0, 1] 之間所有最簡分數 p/q 滿足 q <= N 的個數 = Phi[N]
定理:Phi[N] ~ O(N^2)
也就是說,如果要直接計算 Phi[N],
最笨的方法就是 O(N^2) 不能比這個再笨了。
枚舉:枚舉所有最簡分數 p/q 可以利用 Stern-Brocot Tree,時間複雜度依然是 O(N^2)。
舉例來說 ProjectEuler #198,如果只是單純枚舉所有最簡分數 p/q < 1/100,
時間複雜度永遠是 O(N^2),當 N = 10^8 這樣是行不通的。
(但比枚舉所有分數再檢查是否為最簡分數聰明得多)
話說回來,有沒有聰明招式可以計算 Phi[N]?
Phi[N] = 1/2 * \sum_{d = 1 to N} MobiusFunction[d] Floor[N/d] (1 + Floor[N/d])
這樣只要 O(N) 的計算量就可以算完,似乎還可以再改進。
的確,如果利用 Mobius inversion formula,
Phi[N] = N(N+1)/2 - \sum_{k = 2 to N} Phi[Floor[N/k]]
因為 Floor[N/k] 有很好的性質,piecewise constant,
當 k >= Sqrt[N] 我們可以計算一大票 Phi[Floor[N/k]],
例如 k in (N/2, N],所有的 Phi[Floor[N/k]] = Phi[1],
k in (N/3, N/2],所有的 Phi[Floor[N/k]] = Phi[2],
k in (N/4, N/3],所有的 Phi[Floor[N/k]] = Phi[3],以此類推。
這樣的時間複雜度 O(N^{3/4}),比 O(N) 還要再快些。
2015年5月12日 星期二
ProjectEuler #423
以前做法時間複雜度太高,不切實際,
必須思考好的演算法。
Prime counting function: http://en.wikipedia.org/wiki/Prime-counting_function
數論重要定理:pi(n) ~ n/log(n)
如果可以找到 O(n pi(n)) = O(n^2 / log(n)) 的演算法,
接著再來改進演算法就可以了(廢話)。
此外,Sieve of Eratosthenes 的時間複雜度是 O(n log log(n)),
不過 ProjectEuler 許多題目需要質數表,對某些解題者來說時間複雜度是 O(1)。
2015年4月15日 星期三
Create simple mvn project
1. mvn archetype:generate -DgroupId=com.mycompany.app -DartifactId=my-app -DarchetypeArtifactId=maven-archetype-quickstart -DinteractiveMode=false
2. mvn package
3. java -cp target/my-app-1.0-SNAPSHOT.jar com.mycompany.app.App
2. mvn package
3. java -cp target/my-app-1.0-SNAPSHOT.jar com.mycompany.app.App
2015年4月13日 星期一
ProjectEuler #403
1. 條件 area of D(a, b) is a rational number 可以得到 relation between a and b。
2. 假設上面說的正確,L(a, b) 可以公式計算 ((不然也沒其他算法?不!還可以用猜的!))。
3. 假設上面說的正確,暴力法複雜度是 O(N^2) 恰巧可以利用 S(100) = 26709528 驗證演算法正確性,並且算出其他 S(某些數字)。
4. 假設題目滿足 ProjectEuler一分鐘定律,要能夠解決 N = 10^12,根據經驗,演算法複雜度有可能是:
2. 假設上面說的正確,L(a, b) 可以公式計算 ((不然也沒其他算法?不!還可以用猜的!))。
3. 假設上面說的正確,暴力法複雜度是 O(N^2) 恰巧可以利用 S(100) = 26709528 驗證演算法正確性,並且算出其他 S(某些數字)。
4. 假設題目滿足 ProjectEuler一分鐘定律,要能夠解決 N = 10^12,根據經驗,演算法複雜度有可能是:
- O(1)
- O(Log[N]),或者是 O((Log[N])^M) for some fix M,簡單說就是 Log[N] 多項式。
- O(Sqrt[N])
- 其他比 O(N) 還要快的演算法。
這是心得。根據這樣子的心得,很容易找出目標演算法可能的複雜度(但離真正解開問題可能還有一段差距)
舉例來說:
(1) N = 10^7
演算法不能是 O(N^2),但演算法複雜度會是 O(Sqrt[N]) 之類的嗎?恐怕不太可能,如果有如此演算法存在題目設計者就會把 N 調高一點,例如 N = 10^15。因此有可能是 O(N) 或是 O(N Log[N]^M) 之類的東西。
(2) N = 100
令人可疑的小數字,通常演算法差不多是 O(N^3) 到 O(N^4),有可能有一些 Log[N] 多項式在裡頭。
(3) N = 10^10, 10^11
如果是 O(Sqrt[N]) 以下的演算法,感覺 N 可以在調高一點。所以判斷演算法差不多比 O(Sqrt[N]) 慢些但不會到 O(N)。
(4) N = 10^100, 10^10000
這種不合理的大數字,有可能把 N 當成無窮大使用(分析)。如果是求確實數字演算法很有可能是 O(1) 或者是 O(Log[N]^M) 之類的玩意兒。
2015年4月7日 星期二
Setup maven on mac
1. Download Apache Maven 3.3.1 (http://maven.apache.org/download.cgi)
2. Set environment variable
- export JAVA_HOME=$(/usr/libexec/java_home)
- export PATH=$PATH:/Users/menggen/Downloads/apache-maven-3.3.1/bin
- mvn --version
2015年4月1日 星期三
ProjectEuler #440
當初看錯題目,以為題目規定排出來的數字的 GCD 要等於 1,這樣根本沒辦法解下去。
做完發現沒有那麼困難,difficulty rating = 60%。然後前面還有兩題算超久:#152 跟 #185,兩大障礙,不過值得安慰的是 #185 可以利用題目來檢查答案對不對,不用傻傻輸入答案拿到一個紅紅的大叉叉。
做完發現沒有那麼困難,difficulty rating = 60%。然後前面還有兩題算超久:#152 跟 #185,兩大障礙,不過值得安慰的是 #185 可以利用題目來檢查答案對不對,不用傻傻輸入答案拿到一個紅紅的大叉叉。
2015年3月24日 星期二
全台灣鬼島第三名終於
解題分享
推薦大家看 Polya 寫的怎樣解題
Polya’s First Principle: Understand the problem
- 容易理解的題目,例如:https://projecteuler.net/problem=370
- 不太容易理解的題目,例如:https://projecteuler.net/problem=367
Polya’s Second Principle: Devise a plan
訂定解題計劃。
- Guess and check
- 數學靈感極佳的人可以嘗試
- Look for a pattern
- 我的愛招。
- 例子:https://projecteuler.net/problem=386。對於小數字情況利用有效率的演算法生出解答試圖找出規律。
- 很多題目知其然不知所以然的就這樣解決了。
- Make an orderly list
- Draw a picture
- 圖片提供直觀的論證
- 例子:https://projecteuler.net/problem=395
- Eliminate possibilities
- Solve a simpler problem
- 暴力法可以解決 small dataset,借此生成小數據測試資料。接著利用小數據測試資料提出有效率的演算法。
- 例子:https://projecteuler.net/problem=386。暴力法笨歸笨但還是有找出正確答案的能力(只是時間花很久而已)
- Use symmetry
- 計算數對個數常用伎倆。
- 特殊一點的用法有計算互質數對 (a, b),接著再計算 (na, nb) 個數。
- Use a model
- 許多機率困難題目必須使用機率模型來處理,例如 Monte Carlo method,Markov chain
- Consider special cases
- Work backwards
- Use direct reasoning
- 直接坦過去。
- 例子:https://projecteuler.net/problem=218
- Use a formula
- 某些數論冷門題必須用冷門公式解答。
- 例子:https://projecteuler.net/problem=412
- Solve an equation
- 數論題目多屬於此類。有時候我們必須快速列舉畢氏三角形整數邊長,有時候我們必須計算 Totient Summatory Function 諸如此類。
- 例子:https://projecteuler.net/problem=446。直接沒有繞圈餘地。
- Be ingenious
Polya’s Third Principle: Carry out the plan
能夠紙筆計算的題目並不多,多數題目必須寫程式來縮短紙筆計算時間。熟悉並且熟練 C/C++/Java/Python 或是其他程式語言很重要。
實作上 C/C++ 必須留意常發生的 pointer/overflow 等問題。至於 Python 常犯的錯誤就是 list 沒有 deep copy。
Polya’s Fourth Principle: Look back
這點十分重要,解完題目一定要詳閱討論串。我看到許多人解完 ProjectEuler #1,用 O(n) 解完 ProjectEuler #1,便興匆匆貼上程式碼沒有仔細去看 O(1) 解法的妙味,ProjectEuler #1 不是獨立題目不是免洗筷解完就丟,後面許多題目都會利用規則性來快速計算個數(可能搭配排容原理或是有排容原理內含的定理),總之妙味無窮。
訂閱:
文章 (Atom)