c语言实现快速傅里叶变换

快速傅里叶变换（FFT）是一种高效的计算离散傅里叶变换（DFT）的算法，可以用于信号处理、图像处理等领域。下面是使用C语言实现FFT的代码示例：

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

#define PI 3.14159265358979323846

void fft(double complex[], int);

int main()
{
    int n = 8; // 信号长度，必须是2的幂次方
    double complex x[n];

    // 输入信号
    printf("Please enter the signal (real and imaginary parts):\n");
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &x[i].real, &x[i].imag);
    }

    // 计算FFT
    fft(x, n);

    // 输出结果
    printf("FFT result:\n");
    for (int i = 0; i < n; i++) {
        printf("%f + %fi\n", x[i].real, x[i].imag);
    }

    return 0;
}

void fft(double complex x[], int n)
{
    if (n <= 1) {
        return;
    }

    // 分离奇偶项
    double complex even[n/2];
    double complex odd[n/2];
    for (int i = 0; i < n/2; i++) {
        even[i] = x[2*i];
        odd[i] = x[2*i+1];
    }

    // 递归计算FFT
    fft(even, n/2);
    fft(odd, n/2);

    // 合并结果
    for (int k = 0; k < n/2; k++) {
        double complex t = cexp(-2*PI*I*k/n) * odd[k];
        x[k] = even[k] + t;
        x[k+n/2] = even[k] - t;
    }
}

这里使用了C语言的复数类型 `double complex`，需要包含头文件 `math.h`。函数 `fft` 实现了递归计算FFT的过程，参数 `x` 是输入信号，参数 `n` 是信号长度，必须是2的幂次方。在 `main` 函数中输入信号并调用 `fft` 函数计算FFT，最后输出结果。注意，这里实现的是基2FFT，也可以实现基3、基4等FFT。