DIV CSS 佈局教程網

筆試題解析:n 條直線最多能把平面分成幾部分
編輯:關於JavaScript     

這是一道常見的筆試題,用遞推可以解,用「找規律」也能解。以下先給可互動的實作,再說明兩種思考路徑。

互動頁面

題:有 n 條直線最多可以把一個平面分成多少個部分
線條數:<input type="text" id="line" />
內交點:<label id="innerPoint"></label>
分割數:<label id="part" style="background:yellow;"></label>
<input type="button" onclick="calculate()" value="計算" />

<script type="text/javascript">
function calculate() {
    var line = document.getElementById('line').value;
    if (line == "") {
        line = 0;
        document.getElementById('line').value = line;
    }
    line = parseInt(line);
    var innerPoint = line * (line - 1) / 2;
    var part = (Math.pow(line, 2) + line) / 2 + 1;

    document.getElementById('innerPoint').innerText = innerPoint;
    document.getElementById('part').innerText = part;
}
</script>

正規解法:遞推

  1. 最多分成的部分數 = 線條數 + 內交點數 + 1。
  2. 內交點數 =(n−1 條線的內交點數)+(n−1),因為新加入的那條線最多可與其餘每一條相交。
  3. 用遞推求出內交點數後代入第一式。

展開後即 innerPoint = n(n-1)/2,part = n(n+1)/2 + 1。

另一條路:列舉找規律

列出 1 到 5 條直線的可用參數:

  • 1 條:內交點 0,外交點 2,部分數 2
  • 2 條:內交點 1,外交點 4,部分數 4
  • 3 條:內交點 3,外交點 6,部分數 7
  • 4 條:內交點 6,外交點 8,部分數 11
  • 5 條:內交點 10,外交點 10,部分數 16

觀察後可以發現:外交點沒有實質意義,恆為線條數的兩倍;部分數 = 線條數 + 內交點數 + 1。

而相鄰線條數的內交點差值構成公差為 1 的等差序列:1−0=1、3−1=2、6−3=3、10−6=4。橫向看 1+0=1、2+1=3、3+3=6……仍需遞推;因此改看縱向:2×1=2、3×2=6、4×3=12,正好是內交點數的兩倍,於是得到 n(n-1)/2 這個閉式解。

小結

兩條路殊途同歸。面試時先講遞推(思路清晰、易於推廣到三維的平面分割),再補上閉式解與時間複雜度 O(1),答案會完整得多。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved