多項式插值是數值分析核心課題。牛頓插值法以其增量構建特性（新增節點無需重算舊係數）成為工程首選。本文深度解析一個完整的 C++ 實現，涵蓋節點排序、差分表構建、多項式係數提取、霍納法則求值等關鍵步驟。
n 個節點 (xᵢ, yᵢ)，按 x 升序排列（插值要求節點有序）f[xᵢ, ..., xⱼ]差分表為下三角矩陣，採用一維陣列壓縮映射：
#define Q(a,b) Q[(a)*(a+1)/2 + b]
// Q(i,j) 對應第 i 行第 j 列 (0 ≤ j ≤ i < n)
// 總大小：n(n+1)/2這消除了動態二維陣列指針開銷，提升快取局部性。
setroot()void setroot() {
// 冒泡排序 x[] 並同步調整 Q(i,0)
for (i=0; iNewton()void Newton() {
for (i=1; i遞推公式：f[xᵢ,...,xᵢ₋ⱼ] = (f[xᵢ,...,xᵢ₋ⱼ₊₁] - f[xᵢ₋₁,...,xᵢ₋ⱼ]) / (xᵢ - xᵢ₋ⱼ)
f(x₀)void f(double x0) {
for (i=n-1; i>0; i--)
b[i-1] = Q(i-1,i-1) + b[i] * (x0 - x[i-1]);
// b[0] 即為 Pₙ(x₀)
}對應多項式嵌套形式：P(x) = a₀ + (x-x₀)[a₁ + (x-x₁)[a₂ + ...]]
// in.txt
7
-3 -4.5
6 2.1
-1 -3.2
5 2.8
-2 -1.8
3 1.7
0 0.5
// out.txt 差分表片段
0 -3 -4.5
1 -2 -1.8 2.7
2 -1 -3.2 -1.4 -2.05
3 0 0.5 3.7 2.55 1.53333
...
// 中點插值結果
f(-2.5) = -1.06517
f(-1.5) = -3.06750
f(-0.5) = -1.86002
f(1.5) = 5.90552
f(4.0) = -0.57778
f(5.5) = 4.59237new[]/delete[] 配對使用，現代 C++ 建議 std::vector 自動管理class NewtonInterpolator {
std::vector x_, coef_;
public:
NewtonInterpolator(std::vector> nodes) {
// 排序、構建差分表、提取係數
}
double operator()(double x) const { /* 霍納法則 */ }
void printDiffTable(std::ostream& os) const;
}; 牛頓均勻插值的 C++ 實現展示了數學演算法到工程代碼的轉化精髓：三角陣列壓縮存儲、遞推差分計算、霍納法則求值、中點驗證質量。掌握這套流程，不僅能解決插值問題，更能建立「演算法工程化」的系統性思維——這正是從程式設計師邁向計算科學工程師的關鍵一步。
