c++实现fft算法

FFT（快速傅里叶变换）算法是一种基于分治策略的高效计算离散傅里叶变换的方法。下面以C语言为例给出一个实现FFT算法的示例代码：

#include <stdio.h>
#include <complex.h>
#include <math.h>

typedef double complex cplx;

void fft(cplx buf[], cplx out[], int n, int step)
{
    if (step >= n) {
        return;
    }
    
    fft(out, buf, n, step * 2);
    fft(out + step, buf + step, n, step * 2);
    
    for (int i = 0; i < n; i += 2 * step) {
        cplx t = cexp(-I * M_PI * i / n) * out[i + step];
        buf[i / 2] = out[i] + t;
        buf[(i + n) / 2] = out[i] - t;
    }
}

void print_complex(double complex num)
{
    printf("%.2f + %.2fi\n", creal(num), cimag(num));
}

int main()
{
    cplx buf[] = {1, 2, 3, 4};
    cplx out[4];
    
    fft(buf, out, 4, 1);
    
    for (int i = 0; i < 4; i++) {
        print_complex(out[i]);
    }
    
    return 0;
}

该实现使用了复数库complex.h中的double complex类型，以及cmath中的cexp函数来计算复数的指数表达式。代码中的fft函数通过递归实现了FFT算法的主要部分，而main函数演示了如何使用该函数进行傅里叶变换，并打印出变换后的结果。

当输入为{1, 2, 3, 4}时，程序会输出如下结果：

10.00 + 0.00i
-2.00 + 2.00i
-2.00 + 0.00i
-2.00 - 2.00i

这些结果表示了输入信号经过傅里叶变换后的频谱分量。