使用c++实现分别用 （1）基于拉格朗日插值法，利用线性插值和抛物线插值，求的近似值； （2）基于牛顿插值法（阅读课本P81-P84），利用线性插值和抛物线插值，求根号115的近似值； 要求：（a）利用程序自动选择在插值计算中所需要的节点；（b）把原始数据点以及得到的插值多项式函数曲线都绘制在MATLAB Figure里，便于观察插值效果。

以下是使用C++实现基于拉格朗日插值法和牛顿插值法的代码：

#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

// 拉格朗日插值法
double LagrangeInterpolation(double x, const vector<double>& X, const vector<double>& Y) {
    double res = 0.0;
    for (int i = 0; i < X.size(); i++) {
        double Li = 1.0;
        for (int j = 0; j < X.size(); j++) {
            if (j == i) continue;
            Li *= (x - X[j]) / (X[i] - X[j]);
        }
        res += Li * Y[i];
    }
    return res;
}

// 抛物线插值法
double ParabolicInterpolation(double x, const vector<double>& X, const vector<double>& Y) {
    int n = X.size();
    if (n < 3) {
        cerr << "Error: Parabolic interpolation needs at least 3 data points." << endl;
        exit(1);
    }
    int i = 0;
    while (i < n - 2 && X[i+2] <= x) i++;
    double x1 = X[i], x2 = X[i+1], x3 = X[i+2];
    double y1 = Y[i], y2 = Y[i+1], y3 = Y[i+2];
    double L1 = ((x-x2)*(x-x3))/((x1-x2)*(x1-x3)), L2 = ((x-x1)*(x-x3))/((x2-x1)*(x2-x3)), L3 = ((x-x1)*(x-x2))/((x3-x1)*(x3-x2));
    return L1*y1 + L2*y2 + L3*y3;
}

// 牛顿插值法
double NewtonInterpolation(double x, const vector<double>& X, const vector<double>& Y) {
    int n = X.size();
    vector<double> c(n, 0.0);
    c[0] = Y[0];
    for (int i = 1; i < n; i++) {
        for (int j = n-1; j >= i; j--) {
            Y[j] = (Y[j] - Y[j-1]) / (X[j] - X[j-i]);
        }
        c[i] = Y[i];
    }
    double res = c[n-1];
    for (int i = n-2; i >= 0; i--) {
        res = c[i] + (x - X[i]) * res;
    }
    return res;
}

int main() {
    // 读入数据
    ifstream fin("data.txt");
    vector<double> X, Y;
    double x, y;
    while (fin >> x >> y) {
        X.push_back(x);
        Y.push_back(y);
    }
    fin.close();

    // 生成插值点
    srand((unsigned)time(0));
    vector<double> X_interp, Y_interp;
    for (int i = 0; i < 10; i++) {
        double x_interp = X[0] + (X.back() - X[0]) * rand() / RAND_MAX;
        X_interp.push_back(x_interp);
        Y_interp.push_back(LagrangeInterpolation(x_interp, X, Y)); // 用拉格朗日插值
        if (i % 2 == 0) Y_interp.back() = ParabolicInterpolation(x_interp, X, Y); // 用抛物线插值
    }

    // 在MATLAB中绘制原始数据点
    ofstream fout("data.m");
    fout << "figure;" << endl;
    fout << "hold on;" << endl;
    fout << "plot(";
    for (int i = 0; i < X.size(); i++) {
        fout << X[i] << ",";
    }
    fout << Y[0];
    for (int i = 1; i < Y.size(); i++) {
        fout << "," << Y[i];
    }
    fout << ",'bo');" << endl;

    // 在MATLAB中绘制拉格朗日插值曲线
    fout << "x = " << X_interp[0];
    for (int i = 1; i < X_interp.size(); i++) {
        fout << ":" << X_interp[i];
    }
    fout << ";" << endl;
    fout << "y = [";
    for (int i = 0; i < Y_interp.size(); i++) {
        fout << Y_interp[i] << ",";
    }
    fout << "0];" << endl;
    fout << "plot(x, y, 'r-');" << endl;

    // 在MATLAB中绘制牛顿插值曲线
    X_interp.clear();
    Y_interp.clear();
    for (int i = 0; i < 10; i++) {
        double x_interp = X[0] + (X.back() - X[0]) * rand() / RAND_MAX;
        X_interp.push_back(x_interp);
        Y_interp.push_back(NewtonInterpolation(x_interp, X, Y)); // 用牛顿插值
        if (i % 2 == 0) Y_interp.back() = ParabolicInterpolation(x_interp, X, Y); // 用抛物线插值
    }
    fout << "x = " << X_interp[0];
    for (int i = 1; i < X_interp.size(); i++) {
        fout << ":" << X_interp[i];
    }
    fout << ";" << endl;
    fout << "y = [";
    for (int i = 0; i < Y_interp.size(); i++) {
        fout << Y_interp[i] << ",";
    }
    fout << "0];" << endl;
    fout << "plot(x, y, 'g-');" << endl;

    fout << "hold off;" << endl;
    fout.close();

    return 0;
}

其中，数据点存储在`data.txt`文件中，每行包含一个$x$坐标和一个$y$坐标，用空格隔开。程序首先读入数据，然后生成10个插值点。对于每个插值点，程序用拉格朗日插值法和牛顿插值法分别计算近似值，如果该插值点的序号为偶数，则还用抛物线插值法计算近似值。最后，程序将原始数据点、拉格朗日插值曲线和牛顿插值曲线绘制在MATLAB Figure中，方便观察插值效果。MATLAB代码存储在`data.m`文件中，可以用MATLAB软件打开。