已知n次函数图像上n+1个点的坐标，求解析式各项的系数

Question

点值表示怎么转系数表示？
请不要盲目回答FFT中的那些公式
可以没有代码，但请讲清楚一个中学生能理解的思路谢谢

Answer 1

用矩阵很方便
k[0]*x[0]^0+k[1]*x[0]^1+...+k[n]*x[0]^n=y[0]
k[0]*x[1]^0+k[1]*x[1]^1+...+k[n]*x[1]^n=y[1]
.
.
.
k[0]*x[n]^0+k[1]*x[n]^1+...+k[n]*x[n]^n=y[n]

等价于

系数k等于y左乘x的逆

#include <stdio.h>
#include <malloc.h>
#include <math.h>
#ifndef NULL
#define NULL ((void *)0)
#endif
/**
 * 求矩阵的余子矩阵
 * @param sm 原矩阵
 * @param row 行数
 * @param col 列数
 * @param l 行
 * @param r 列
 */
double *minor(double *sm,int row,int col,int l, int r) {
    if(row<1||col<1) {
        return NULL;
    }
    double *dm=(double *)malloc(sizeof(double)*(row-1)*(col-1));
    int i,j,li,rj;
    for (i = 0; i < row - 1; i++) {
        for (j = 0; j < col - 1; j++) {
            li = i;
            rj = j;
            if (i >= l) {
                li++;
            }
            if (j >= r) {
                rj++;
            }
            if (rj < col) {
                dm[i*(col-1)+j] = sm[li*col+rj];
            } else {
                dm[i*(col-1)+j] = 0;
            }
        }
    }
    return dm;
}
/**
 * 求矩阵的行列式值
 * @param m 矩阵
 * @param row 行数
 * @param col 列数
 */
double det(double *m,int row,int col) {
    double sum = 0;
    double *rm;
    if (row > 1) {
        int i;
        for (i = 0; i < row; i++) {
            rm = minor(m, row, col, i, 0);
            sum += det(rm,row-1,col-1) * m[i*col+0] * (i%2==0?1:-1);
            free(rm);
        }
    } else {
        sum += m[0];
    }
    return sum;
}
/**
 * 求矩阵的数乘
 * @param sm 原矩阵
 * @param n 倍数
 * @param row 行数
 * @param col 列数
 */
double *amass(double *sm, int row, int col, double n) {
    double *dm;
    dm = (double *)malloc(sizeof(double)*row*col);
    int i,j;
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            dm[i*col+j] = sm[i*col+j] * n;
        }
    }
    return dm;
}
/**
 * 求两矩阵的乘积
 * @param lm 左矩阵
 * @param lRow 左矩阵行数
 * @param lCol 左矩阵列数
 * @param rm 右矩阵
 * @param rRow 右矩阵行数
 * @param rCol 右矩阵列数
 */
double *multiply(double *lm, int lRow, int lCol, double *rm, int rRow, int rCol) {
    double *dm;
    double numb;
    dm = (double *)malloc(sizeof(double)*lRow*rCol);
    int i,j,k;
    for (i = 0; i < lRow; i++) {
        for (j = 0; j < rCol; j++) {
            numb = 0;
            for (k = 0; k < rRow; k++) {
                if (k < lCol && j < rCol) {
                    numb += lm[i*lCol+k] * rm[k*rCol+j];
                }
            }
            dm[i*rCol+j] = numb;
        }
    }
    return dm;
}
/**
 * 求矩阵的伴随矩阵
 * @param sm 原矩阵
 * @param row 行数
 * @param col 列数
 */
double *adjoint(double *sm, int row, int col) {
    double *dm, *rm;
    dm = (double *)malloc(sizeof(double)*row*col);
    int i,j;
    for (i = 0; i < row; i++) {
        for (j = 0; j < row; j++) {
            rm = minor(sm, row, col, i, j);
            dm[i*col+j] = ((i+j)%2==0?1:-1) * det(rm, row, col);
            free(rm);
        }
    }
    return dm;
}
/**
 * 求矩阵的逆矩阵
 * @param sm 原矩阵
 * @param row 行数
 * @param col 列数
 */
double *inverse(double *sm, int row, int col) {
    double *dm=NULL,*am;
    double smDet;
    smDet = det(sm, row, col);
    if (smDet != 0) {
        am=adjoint(sm,row,col);
        dm = amass(am,row,col, 1.0 / smDet);
        free(am);
    }
    return dm;
}
/**
 * 输出矩阵
 * @param m 矩阵
 * @param row 行数
 * @param col 列数
 */
void outputMatrix(double *m, int row, int col) {
    int i,j;
    for(i=0; i<row; i++) {
        printf("[");
        for(j=0; j<col; j++) {
            printf("%f",m[i*col+j]);
            if(j<col-1) {
                printf("\t");
            }
        }
        printf("]\n");
    }
}
int main() {
    int n,i,j;
    double *xm,*ym,*km,*rexm;
    printf("多少个点:");
    scanf("%d",&n);
    xm=(double *)malloc(sizeof(double)*n*n);
    ym=(double *)malloc(sizeof(double)*n);
    for(i=0; i<n; i++) {
        printf("第%d个点x坐标:",i);
        xm[i*n+0]=1;
        scanf("%lf",&xm[i*n+1]);
        for(j=2; j<n; j++) {
            xm[i*n+j]=pow(xm[i*n+1],j);
        }
        printf("第%d个点y坐标:",i);
        scanf("%lf",&ym[i]);
    }
    rexm=inverse(xm,n,n);
    if(rexm!=NULL) {
        km=multiply(rexm,n,n,ym,n,1);
        for(i=0; i<n; i++) {
            printf("k[%d]:%lf\n",i,km[i]);
        }
        printf("函数式为:\ny=");
        for(i=n; i>1; i--) {
            printf("(%lf)*x^%d+",km[i],i);
        }
        printf("(%lf)*x+",km[1],1);
        printf("%lf",km[0]);
    } else {
        printf("无特殊解");
    }
    return 0;
}