帮忙FFT C语言实现

好的，下面给你一个简单的 FFT 实现代码，使用的是 Cooley-Tukey 算法：

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

#define PI 3.14159265358979323846

typedef struct {
    double real;
    double imag;
} complex;

void fft(complex *buf, int n)
{
    if(n == 1)
        return;
    complex even[n/2], odd[n/2];
    for(int i = 0; i < n/2; i++) {
        even[i] = buf[i*2];
        odd[i] = buf[i*2+1];
    }
    fft(even, n/2);
    fft(odd, n/2);
    for(int i = 0; i < n/2; i++) {
        complex t;
        t.real = cos(2*PI*i/n)*odd[i].real + sin(2*PI*i/n)*odd[i].imag;
        t.imag = cos(2*PI*i/n)*odd[i].imag - sin(2*PI*i/n)*odd[i].real;
        buf[i] = (complex){even[i].real+t.real, even[i].imag+t.imag};
        buf[i+n/2] = (complex){even[i].real-t.real, even[i].imag-t.imag};
    }
}

int main()
{
    int n = 8;
    complex buf[] = {{1,0}, {2,0}, {3,0}, {4,0}, {5,0}, {6,0}, {7,0}, {8,0}};

    fft(buf, n);

    for(int i = 0; i < n; i++)
        printf("%f + %fi\n", buf[i].real, buf[i].imag);

    return 0;
}

调用 `fft` 函数时，传入的参数 `buf` 是一个复数数组，长度为 $2^n$，其中 $n$ 是一个正整数。这里使用的是递归实现，将复数数组分成两半，递归求解，最终合并。