我写的这个源程序是基于MATLAB平台写的，但是其思想是基于C++写的，因为MATLAB中自带快速傅里叶变换（fft）函数。MATLAB自带的fft它的运行原理我没有搞懂，所以就自己写了一个源程序。
PS:MATLAB自带的快速傅里叶变换（fft）函数，它依据的原理，也就是说它为点值表达式所输入的点，并不是，所以用MATLAB自带的fft函数，得到的结果会和你的预期不一样。
FFT的理论知识可以参考这几位博主的内容《/RabbitHu/p/FFT.html》《/zwfymqz/p/8244902.html?mType=Group#_label3》
《/enjoy_pascal/article/details/81478582》
上面几位都是大佬，可以看看，写的都很好，讲解的也清楚，同时他们的博客中也有C++源代码，原谅我的C++水平太低，看别人写好的程序都看不大懂。
下面是MATLAB源代码，有不懂的可在下方评论，我经常在线
function [X,Y]=FFT(arry)%% 快速傅里叶变换% X,Y分别是输出的点值表示法中的点与值% arry是输入的多项式系数向量，请提前准备好系数向量,长度务必是2的n次幂%% 预计算arry=arry(end:-1:1); %将输入的多项式系数翻转% 因为本程序中使用的多项式序列是a0,a1,a2,...,an，按照书面用语写的% 在MATLAB中（别的平台，C++可能也是，不太清楚），多项式的序列是an,a(n-1),a(n-2),...,a1,a0% 例如你在命令窗口中输入[1 2 3],它代表的多项式是x^2+2*x+3.% 而在书面用语中一般是f(x)=1+2*x+3*x^2(a0+a1*x+a2*x^2)n=length(arry); %求系数向量的长度num1=0:n-1; %创建原始多项式系数序列，a0,a1,a2,...an,num1=[0 1 2 ,...,n]num2=num1; %创建一个备用向量，用于存储翻转后的二进制多项式系数B=dec2bin(num1); %将多项式转换为二进制%% 将多项式转化为二进制后，将其翻转，并存储for L=1:nB(L,:)=reverse(B(L,:));num2(L)=bin2dec(B(L,:));endX=zeros(1,n); %为X预分配空间%% 预计算复数点Xfor k=1:nX(k)=cos(((k-1)/n)*2*pi)+1i*sin(((k-1)/n)*2*pi);endcount=0;N=n;%% 计算需要将整个多项式系数分几次，才会分到最后单个系数while(1)N=N/2;count=count+1;if N==1break;endendY=zeros(1,n); %为多项式值预分配空间a1=2^(count-1); %计算每次需要迭代中X需要乘方的次数%每次需要迭代中X需要乘方的次数构成一个等比数列，a1是第一项q=1/2;%等比数列的q%% 对多项式进行迭代计算for L=1:n/2%只需计算n/2次即可，后n/2次可根据前面的A1(X),A2(X)得到num3=num2;for LL=1:countlen=length(num3);nt=0;an=a1*q^(LL-1);for LLL=1:2:lennt=nt+1;if LL==1y1(nt)=arry(num3(LLL)+1)+(X(L)^an)*arry(num3(LLL+1)+1);elseif LL==county1(nt)=num3(LLL)+(X(L)^an)*num3(LLL+1);y2=num3(LLL)-(X(L)^an)*num3(LLL+1);elsey1(nt)=num3(LLL)+(X(L)^an)*num3(LLL+1);endendnum3=y1(1:nt);endY(L)=num3; %存储前半部分结果值Y(L+n/2)=y2; %存储后半部分结果值endend
