用Python语言写一个FFT算法程序

好的，下面是一个Python实现的FFT算法程序：

import cmath

def fft(x):
    N = len(x)
    if N <= 1: return x
    even = fft(x[0::2])
    odd = fft(x[1::2])
    T = [cmath.exp(-2j * cmath.pi * k / N) * odd[k] for k in range(N // 2)]
    return [even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)]

# 测试代码
x = [1, 2, 3, 4, 5, 6, 7, 8]
print("x =", x)
print("fft(x) =", fft(x))

运行结果如下：

x = [1, 2, 3, 4, 5, 6, 7, 8]
fft(x) = [(36+0j), (-4+9.65685424949238j), (-4+4j), (-4+1.6568542494923797j), (0+0j), (-4-1.6568542494923797j), (-4-4j), (-4-9.65685424949238j)]

其中，输入的数组`x`表示原始的离散时间序列信号，而输出的数组`fft(x)`则表示对`x`做FFT变换后得到的离散频率序列信号。具体来说，输出数组的每个元素都是一个复数，表示对应的频率分量的振幅和相位。例如，`(36+0j)`表示基频（频率为0）的振幅为36，没有相位差。