用c语言写一个快速傅里叶变换
时间: 2023-05-20 17:06:17 浏览: 73
可以使用以下代码实现快速傅里叶变换:
#include <stdio.h>
#include <math.h>
#define PI 3.14159265358979323846
typedef struct {
double real;
double imag;
} complex;
void fft(complex *x, int n) {
if (n <= 1) return;
complex *even = new complex[n / 2];
complex *odd = new complex[n / 2];
for (int i = 0; i < n / 2; i++) {
even[i] = x[2 * i];
odd[i] = x[2 * i + 1];
}
fft(even, n / 2);
fft(odd, n / 2);
for (int i = 0; i < n / 2; i++) {
complex t = {cos(2 * PI * i / n), -sin(2 * PI * i / n)};
t.real *= odd[i].real;
t.imag *= odd[i].imag;
x[i].real = even[i].real + t.real;
x[i].imag = even[i].imag + t.imag;
x[i + n / 2].real = even[i].real - t.real;
x[i + n / 2].imag = even[i].imag - t.imag;
}
delete[] even;
delete[] odd;
}
int main() {
int n = 8;
complex x[] = {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}, {7, 0}, {8, 0}};
fft(x, n);
for (int i = 0; i < n; i++) {
printf("%f + %fi\n", x[i].real, x[i].imag);
}
return 0;
}