FFT（快速傅里叶变换）是一种 离散傅里叶变换的快速算法，用于将离散时间信号从时域变换到频域。FFT显著降低了计算DFT的复杂度，从而使得在数字信号处理、图像处理和音频处理等领域的高效实现成为可能。FFT的基本思想是通过分治法将N点DFT分解为规模较小的DFT，进而减少计算量。
FFT程序通常包含以下几个关键部分：
初始化：
设置必要的变量和参数，如输入数据的长度、复数序列的实部和虚部等。
主函数：
调用FFT计算函数，并处理或输出变换结果。
FFT计算函数：
实现FFT算法，通过递归或迭代的方式将输入数据转换为频域表示。
```c
include
void fft（int n, float *real, float *imag） {
if （n == 1） {
return；
}
int half = n / 2；
fft（half, real, imag）；
fft（half, real + half, imag + half）；
float w = 1.0；
for （int i = 0； i < half； i++） {
float xr = real[i]；
float xi = imag[i]；
real[i] = xr + w * imag[half + i]；
imag[i] = xi - w * real[half + i]；
real[half + i] = xr - w * imag[half + i]；
imag[half + i] = xi + w * real[half + i]；
w *= -1.0；
}
}
int main（） {
int n；
printf（"Please input the number of xi/n: "）；
scanf（"%d", &n）；
float *real = （float *）malloc（n * sizeof（float））；
float *imag = （float *）malloc（n * sizeof（float））；
// 输入实部
for （int i = 0； i < n； i++） {
scanf（"%lf", &real[i]）；
}
// 输入虚部（这里假设虚部为0，因为示例中没有给出）
for （int i = 0； i < n； i++） {
imag[i] = 0.0；
}
fft（n, real, imag）；
// 输出傅里叶变换结果
for （int i = 0； i < n； i++） {
printf（"%lf %lf\n", real[i], imag[i]）；
}
free（real）；
free（imag）；
return 0；
}
```
此外，FFT还可以通过多线程、使用JIT编译器（如Numba）等方式进行优化，以提高计算性能。在实际应用中，FFT程序可以根据具体需求进行定制和优化，以适应不同的应用场景和性能要求。