基礎演算法想法

演算法簡單來說就是處理問題的方法
問題必須限定於能在有限次數內得出有效解
想辦法提升解答的效率就是演算法的精神
針對各種需求例如搜尋、排序等，分別有對其最有效率的演算法

而各種演算法的設計原則大概可基於以下幾個概念

窮舉法(Exhaustive Attack method)是最簡單的演算法
原理就是運用電腦的計算能力來窮盡每一種可能
雖然效率不高，但適用於沒有明顯規律的場合
最著名的問題，雞兔同籠，線上範例

function test(head, foot) {
    var i, j;
    for (i = 0; i < head; i++) {
        j = head - i;
        if (2 * i + 4 * j == foot) {
            console.log("chicken=" + i + " rabbit=" + j);
            break;
        }
    }
}

test(35, 94);

遞推演算法適用於有明顯公式規律的場合
使用者須知道問題與解答的邏輯關係
例如費式數列 : 1, 1, 2, 3, 5，邏輯規則就是 F(n) = F(n-2) + F(n-1)
線上範例

function Fibonacci(n) {
    if (n == 1 || n == 2) {
        return 1;
    } else return Fibonacci(n - 1) + Fibonacci(n - 2);
}

console.log(Fibonacci(10));

遞迴演算法是實務上常用的演算法之一
藉由多次呼叫自己來取得答案，但須注意一些重點以避免寫出不適合或有錯誤的遞迴
最常犯的錯誤是忘了加"return"關鍵字來回傳，以及建立無窮遞迴
遞迴的好處是程式碼簡潔易讀
缺點則是沒有減少記憶體等資源的使用量，以及因為大量的呼叫方法(自身)使得速度較慢
前一例的 Fibonacci function的實作面便運用了遞迴

機率演算法則是一種應付問題難以得到精確解的演算法
藉由大量的數據去推算近似值
例如以機率演算法中的蒙地卡羅法為例，線上範例

最著名的例子就是利用圓面積的特性來計算π
以左邊的1/4圓為例，假設圓半徑為1，則1/4圓面積就是π/4，正方形面積為1
則現在放置大量的"點"於正方形中，點位於1/4圓的機率等同面積比 = π/4
而判斷"點"是否在1/4圓則可藉由 x² + y²  <= 1 公式判斷

function MontePI(n) {
    var times = 0;
    var x, y;
    for (var i = 0; i < n; i++) {
        x = Math.random();
        y = Math.random();
        if (x * x + y * y <= 1) {
            times++;
        }
    }
    return 4.0 * times / n;
}

console.log(MontePI(100000));