c++实现快速傅里叶变换（FFT）

快速傅里叶变换（FFT）是一种高效的计算离散傅里叶变换（DFT）的算法。下面是使用 C++ 实现 FFT 的示例代码：

#include <iostream>
#include <cmath>
#include <complex>
using namespace std;

const double PI = acos(-1.0);

void FFT(complex<double>* a, int n, int inv) {
    if (n == 1) return;
    complex<double> a0[n / 2], a1[n / 2];
    for (int i = 0; i < n / 2; i++) {
        a0[i] = a[i * 2];
        a1[i] = a[i * 2 + 1];
    }
    FFT(a0, n / 2, inv);
    FFT(a1, n / 2, inv);
    complex<double> w = 1, wn = exp(complex<double>(0, inv * 2 * PI / n));
    for (int i = 0; i < n / 2; i++) {
        a[i] = a0[i] + w * a1[i];
        a[i + n / 2] = a0[i] - w * a1[i];
        w *= wn;
    }
}

int main() {
    int n = 8;
    complex<double> a[n] = {1, 2, 3, 4, 5, 6, 7, 8};
    FFT(a, n, 1);
    for (int i = 0; i < n; i++) {
        cout << a[i] << endl;
    }
    FFT(a, n, -1);
    for (int i = 0; i < n; i++) {
        cout << a[i] / n << endl;
    }
    return 0;
}

上述代码中，FFT 函数实现了对复数数组 a 的 DFT 或 IDFT 计算。其中，inv 参数表示计算 DFT 还是 IDFT，1 表示 DFT，-1 表示 IDFT。在 FFT 函数内部，首先进行递归，将 a 数组划分为两个长度为 n/2 的数组，然后对这两个数组分别进行 FFT 计算。最后，按照蝴蝶操作的方式将两个数组合并为一个长度为 n 的数组，完成 DFT 或 IDFT 计算。在 main 函数中，我们构造了一个长度为 8 的复数数组并对其进行了 DFT 和 IDFT 计算，并输出了结果。