C++代码实现傅里叶变换

以下是一个C代码实现傅里叶变换的示例：

#include <stdio.h>
#include <math.h>
#define PI 3.14159265359

void FFT(double *real, double *imag, int n) {
    if(n == 1) {
        return;
    }
    double *even_real = (double *) malloc(n/2 * sizeof(double));
    double *even_imag = (double *) malloc(n/2 * sizeof(double));
    double *odd_real = (double *) malloc(n/2 * sizeof(double));
    double *odd_imag = (double *) malloc(n/2 * sizeof(double));

    for(int i = 0; i < n/2; i++) {
        even_real[i] = real[2*i];
        even_imag[i] = imag[2*i];
        odd_real[i] = real[2*i+1];
        odd_imag[i] = imag[2*i+1];
    }

    FFT(even_real, even_imag, n/2);
    FFT(odd_real, odd_imag, n/2);

    for(int i = 0; i < n/2; i++) {
        double w_real = cos(2*PI*i/n);
        double w_imag = sin(2*PI*i/n);

        real[i] = even_real[i] + w_real*odd_real[i] - w_imag*odd_imag[i];
        imag[i] = even_imag[i] + w_real*odd_imag[i] + w_imag*odd_real[i];

        real[i+n/2] = even_real[i] - w_real*odd_real[i] + w_imag*odd_imag[i];
        imag[i+n/2] = even_imag[i] - w_real*odd_imag[i] - w_imag*odd_real[i];
    }

    free(even_real);
    free(even_imag);
    free(odd_real);
    free(odd_imag);
}

int main() {
    // 输入实部和虚部数组
    double real[] = {1, 2, 3, 4};
    double imag[] = {0, 0, 0, 0};

    int n = sizeof(real)/sizeof(double);
    FFT(real, imag, n);

    // 输出傅里叶变换结果
    for(int i = 0; i < n; i++) {
        printf("%lf + %lfi\n", real[i], imag[i]);
    }

    return 0;
}

该代码使用递归实现了快速傅里叶变换（FFT），可以将一个长度为 $2^n$ 的实数序列 $x$ 变换为一个长度为 $2^n$ 的复数序列 $X$，公式为：

$$X_k = \sum_{n=0}^{N-1} x_n e^{-2\pi i nk/N}$$

其中 $N$ 是序列长度，$k$ 是频率序号，$n$ 是时间序号。

在该代码中，`FFT` 函数的输入参数为实部和虚部数组以及序列长度。在函数内部，首先进行递归调用，将序列按照奇偶性拆分成两个长度为 $N/2$ 的序列，然后对这两个序列分别进行递归调用，直到序列长度为 1。接着，根据傅里叶变换公式计算出每个频率的值，最后将结果存储在原实部和虚部数组中。最后，主函数调用 `FFT` 函数，并输出傅里叶变换的结果。