写一个FFT的C语言程序

我可以回答这个问题。FFT是一种快速傅里叶变换算法，可以用于信号处理、图像处理等领域。以下是一个简单的FFT的C语言程序：

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

#define PI 3.14159265358979323846

void fft(double *x, double *y, int n)
{
    if (n == 1) {
        return;
    }

    double xr[n/2], xi[n/2], yr[n/2], yi[n/2];
    for (int i = 0; i < n/2; i++) {
        xr[i] = x[2*i];
        xi[i] = x[2*i+1];
        yr[i] = y[2*i];
        yi[i] = y[2*i+1];
    }

    fft(xr, xi, n/2);
    fft(yr, yi, n/2);

    for (int i = 0; i < n/2; i++) {
        double t = xr[i];
        xr[i] = xr[i] + cos(-2*PI*i/n)*yr[i] - sin(-2*PI*i/n)*yi[i];
        xi[i] = xi[i] + sin(-2*PI*i/n)*yr[i] + cos(-2*PI*i/n)*yi[i];
        xr[i+n/2] = t - cos(-2*PI*i/n)*yr[i] + sin(-2*PI*i/n)*yi[i];
        xi[i+n/2] = xi[i+n/2] - sin(-2*PI*i/n)*yr[i] - cos(-2*PI*i/n)*yi[i];
    }
    for (int i = 0; i < n; i++) {
        x[i] = xr[i];
        y[i] = xi[i];
    }
}

int main()
{
    int n = 8;
    double x[] = {1, 0, 1, 0, 1, 0, 1, 0};
    double y[] = {0, 0, 0, 0, 0, 0, 0, 0};

    fft(x, y, n);

    for (int i = 0; i < n; i++) {
        printf("%f + %fi\n", x[i], y[i]);
    }

    return 0;
}

这个程序实现了一个长度为8的FFT，输入的实部和虚部分别存储在数组x和y中，输出的实部和虚部也分别存储在数组x和y中。程序中使用了递归的方式实现FFT，具体实现可以参考算法导论等相关书籍。