2009年12月30日 星期三

TopCoder Algorithm Tutorials - 基本幾何學(1)

摘錄自:Geometry Concepts: Basic ConceptsComputer Graphics: 向量運算

向量
可以用座標型式 (x, y) 表示,向量相加也可以直接用座標相加:(x1+x2, y1+y2)。

向量內積(dot product)
向量 A=(x1, y1)、向量 B=(x2, y2),則 A 與 B 的內積為:A‧B = x1*x2 +y1*y2 = |A||B|Cos(θ),是一個。又因為 Cos(90) = 0、Cos(0) = 1,所以垂直的兩個向量內積為 0、平行的兩個向量內積有最大值。並且內積公式不限於二維向量,在多維中也可套用。

在電腦圖學中,向量內積可以用來算投影或者光線照射量。光源照射方向若與平面法向量(垂直平面的向量)內積為 0,表示光源與平面平行,照不到平面,絕對值越大,平面受光量越大。

 
(... 閱讀「TopCoder Algorithm Tutorials - 基本幾何學(1)」全文)

2009年12月27日 星期日

TopCoder Algorithm Tutorials - 基礎數學

摘錄自:Mathematics for TopCoders

底數(base)
把 b 進位的數字轉成十進位,可以用下面這段 code 實現。簡單來說就是利用 mod 10 取出各個位數的數字,乘上 b 的 x 次方(multiplier)得到真正的值加到結果(result)中。
public int toDecimal(int n, int b)
{
   int result = 0;
   int multiplier = 1;
      
   while(n>0)
   {
      result += n % 10 * multiplier;
      multiplier *= b;
      n /= 10;
   }
      
   return result;
}
(... 閱讀「TopCoder Algorithm Tutorials - 基礎數學」全文)

2009年12月22日 星期二

[JavaScript] Callback Notes (with jQuery)

參考:Tutorials:How jQuery Works

Callback Function
callback function 當作參數傳給 parent function 時,像這樣:
$.get('myhtmlpage.html', myCallBack);
但是如果這個 callback function 本身也需要傳參數,則不能寫成
$.get('myhtmlpage.html', myCallBack(param1, param2));  // wrong!!
因為這樣是表示先呼叫 myCallBack,執行後的回傳結果當做 get 的第二個參數。正確的寫法應該是:
$.get('myhtmlpage.html', function(){
  myCallBack(param1, param2);
});
(... 閱讀「[JavaScript] Callback Notes (with jQuery)」全文)

2009年12月16日 星期三

TopCoder Algorithm Tutorials - 解題規劃

摘錄自:Planning an Approach to a TopCoder Problem

Pattern Mining and the Wrong Mindset
當解過一定數量的問題後,會發現問題大致上可以分成幾類,於是就會陷入一種「從過去類似問題中找解法」的情況,試著拿過去解過的問題套到眼前的這個問題。這樣的情況並不是很好,特別是當眼前的問題是一個全新的問題時,很容易產生挫敗感。唯有不斷的複習、把每個問題都當成全新的經驗,才能持續進步。

Coding Kata
試試看下面這個練習,它能帶你體驗面對問題的各種可能情況。
嘗試挑一個未解過的問題,開始思考、尋找解法,把解法寫出來、通過測試之後,記下總共花了多少時間解這個問題。接著把程式碼清掉、再寫一次!第二次可能還是會犯些小錯誤,最後再次通過測試後,同樣記下第二次所花的時間,接著再把程式碼清除重新寫一次。第三次就會覺得順多了,完成後也同樣記錄時間。第一個時間表示當你心中沒有任何解法時,理解問題並思考、設計一個解所需要的時間;第二個時間,很意外地,通常只是少了理解問題的時間;而第三次才是真正的當你面對一個問題且能馬上想到解法時,所需要花的時間以及帶給你的感受,記住這個感受作為日後解題時的鼓勵!

(念到Atomic Code開始)
(... 閱讀「TopCoder Algorithm Tutorials - 解題規劃」全文)

2009年12月15日 星期二

TopCoder Algorithm Tutorials - 從題目線索中找解法

摘錄自:How To Find a Solution

從題目給的線索中猜測該用什麼演算法解題。

直覺模擬
這類題目單純地會給很多步驟,條件(複雜度)不會太高,也不會太低,通常是在測試你的 coding 速度,因此不用想太多,照著做就對了。

BFS (廣度優先搜尋)
這類題目通常要求找出從起點狀態到終點狀態「最少步驟(最低成本)」的解,並且狀態間的轉移成本通常是1。常見題目都是給一個 N*M 的表格,有些格子不能通過,求要到達目的地的最短路徑。
因為 BFS 複雜度多半是線性的,因次 N (或 M) 很大(到百萬)也沒關係。

Flood Fill
BFS 找所有解,而非最小那個。

暴力搜尋、backtracking
暴力搜尋的條件(複雜度)不能太高,因為它就是(必須/可以)嘗試所有可能、然後找最好的。backtracking 也是暴力搜尋的一種,通常用遞迴做,並且題目給的條件(複雜度)會很低,那就很適合。
(... 閱讀「TopCoder Algorithm Tutorials - 從題目線索中找解法」全文)

2009年12月3日 星期四

TopCoder Algorithm Tutorials - 序

摘錄自:The Importance of Algorithms

執行時間分析
當 N = 100 時,各種複雜度的估計執行時間:


最短路徑
即使是目前最好的演算法也不一定能有效解決真實生活中的問題。通常處理這些真實問題時,會加一些 heuristic 來幫助加快找到可行的答案。

字串比對
使用 DP 可以大大節省時間。DNA 比對、文章嫖竊判定...等都是字串比對的應用,「版本比對」則是把"一行"視為一個"字",因此也是用字串比對的方式去看哪幾行有新增、修改、刪除。
(... 閱讀「TopCoder Algorithm Tutorials - 序」全文)