c++编写一个快速傅里叶变换程序

下面是一个简单的 C++ 实现快速傅里叶变换（FFT）的程序：

#include <iostream>
#include <cmath>
#include <complex>

using namespace std;

const double PI = acos(-1);

void fft(complex<double> *a, int n, bool invert) {
    int bits = log2(n);

    for (int i = 1; i < n; ++i) {
        int j = 0;
        for (int k = 0; k < bits; ++k) {
            j <<= 1;
            if (i & (1 << k)) j |= 1;
        }
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double angle = 2 * PI / len * (invert ? -1 : 1);
        complex<double> wlen(cos(angle), sin(angle));
        for (int i = 0; i < n; i += len) {
            complex<double> w(1);
            for (int j = 0; j < len / 2; ++j) {
                complex<double> u = a[i + j];
                complex<double> t = w * a[i + j + len / 2];
                a[i + j] = u + t;
                a[i + j + len / 2] = u - t;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (int i = 0; i < n; ++i) {
            a[i] /= n;
        }
    }
}

int main() {
    int n;
    cout << "输入序列长度 n ：" << endl;
    cin >> n;

    complex<double> *a = new complex<double>[n];

    cout << "输入序列：";
    for (int i = 0; i < n; ++i) {
        double x;
        cin >> x;
        a[i] = complex<double>(x, 0);
    }

    fft(a, n, false);

    cout << "傅里叶变换后的结果：";
    for (int i = 0; i < n; ++i) {
        cout << a[i].real() << "+" << a[i].imag() << "i" << " ";
    }
    cout << endl;

    delete[] a;
    return 0;
}

该程序可以通过输入一个长度为 n 的实数序列，计算出其傅里叶变换的结果。其中，fft 函数为快速傅里叶变换的实现。如果 invert 参数为 true，则表示进行逆变换。

需要注意的是，该程序只是一个简单的实现，可能存在精度问题和效率问题，实际应用中需要根据具体情况进行优化。