请使用C语言写出傅里叶变换和反傅里叶变换的算法

傅里叶变换和反傅里叶变换的算法可以使用C语言实现。以下是基于快速傅里叶变换（FFT）的算法实现：

傅里叶变换算法：

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

#define PI 3.14159265358979323846

void fft(double *x, double *y, int n) {
    if (n == 1) {
        return;
    }
    double xn[n / 2], yn[n / 2], xo[n / 2], yo[n / 2];
    for (int i = 0; i < n / 2; i++) {
        xn[i] = x[2 * i];
        yn[i] = y[2 * i];
        xo[i] = x[2 * i + 1];
        yo[i] = y[2 * i + 1];
    }
    fft(xn, yn, n / 2);
    fft(xo, yo, n / 2);

    for (int k = 0; k < n / 2; k++) {
        double t = xo[k] * cos(2 * PI * k / n) + yo[k] * sin(2 * PI * k / n);
        x[k] = xn[k] + t;
        y[k] = yn[k] + t;
        x[k + n / 2] = xn[k] - t;
        y[k + n / 2] = yn[k] - t;
    }
}

int main() {
    int n = 4;
    double x[] = {1, 2, 3, 4};
    double y[] = {0, 0, 0, 0};
    fft(x, y, n);
    for (int i = 0; i < n; i++) {
        printf("(%lf, %lf)\n", x[i], y[i]);
    }
    return 0;
}

反傅里叶变换算法：

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

#define PI 3.14159265358979323846

void ifft(double *x, double *y, int n) {
    if (n == 1) {
        return;
    }
    double xn[n / 2], yn[n / 2], xo[n / 2], yo[n / 2];
    for (int i = 0; i < n / 2; i++) {
        xn[i] = x[2 * i];
        yn[i] = y[2 * i];
        xo[i] = x[2 * i + 1];
        yo[i] = y[2 * i + 1];
    }
    ifft(xn, yn, n / 2);
    ifft(xo, yo, n / 2);

    for (int k = 0; k < n / 2; k++) {
        double t = xo[k] * cos(2 * PI * k / n) - yo[k] * sin(2 * PI * k / n);
        x[k] = xn[k] + t;
        y[k] = yn[k] + t;
        x[k + n / 2] = xn[k] - t;
        y[k + n / 2] = yn[k] - t;
    }
}

int main() {
    int n = 4;
    double x[] = {1, 2, 3, 4};
    double y[] = {0, 0, 0, 0};
    fft(x, y, n);
    ifft(x, y, n);
    for (int i = 0; i < n; i++) {
        printf("(%lf, %lf)\n", x[i] / n, y[i] / n);
    }
    return 0;
}