這是一道常見的筆試題,用遞推可以解,用「找規律」也能解。以下先給可互動的實作,再說明兩種思考路徑。
題:有 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>
展開後即 innerPoint = n(n-1)/2,part = n(n+1)/2 + 1。
列出 1 到 5 條直線的可用參數:
觀察後可以發現:外交點沒有實質意義,恆為線條數的兩倍;部分數 = 線條數 + 內交點數 + 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),答案會完整得多。