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

摘錄自：Geometry Concepts: Basic Concepts、Computer Graphics: 向量運算

向量
可以用座標型式 (x, y) 表示，向量相加也可以直接用座標相加：(x₁+x₂, y₁+y₂)。

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

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

　

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

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 - 基礎數學」全文)

[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)」全文)

TopCoder Algorithm Tutorials - 解題規劃

摘錄自：Planning an Approach to a TopCoder Problem

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

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

(念到Atomic Code開始)

(... 閱讀「TopCoder Algorithm Tutorials - 解題規劃」全文)

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

摘錄自：How To Find a Solution

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

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

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

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

暴力搜尋、backtracking
暴力搜尋的條件(複雜度)不能太高，因為它就是(必須/可以)嘗試所有可能、然後找最好的。backtracking 也是暴力搜尋的一種，通常用遞迴做，並且題目給的條件(複雜度)會很低，那就很適合。

(... 閱讀「TopCoder Algorithm Tutorials - 從題目線索中找解法」全文)

TopCoder Algorithm Tutorials - 序

摘錄自：The Importance of Algorithms

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


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

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

(... 閱讀「TopCoder Algorithm Tutorials - 序」全文)