代码:
typedef long double db;
typedef complex<db> C;
const db Pi=acos(-1.0);
void DFT(C* f,int len,int rev){
cout<<len<<" ";
if(len==1)return;
for(int i=0;i<len;i++)tmp[i]=f[i];
for(int i=0;i<len;i++){
if(i&1)f[(len+i)>>1]=tmp[i];
else f[i>>1]=tmp[i];
}
C *l=f,*l2=f+(len>>1);
DFT(l,len>>1,rev);
DFT(l2,len>>1,rev);
C cur(1,0),stp(cos(2*Pi/len),rev*sin(2*Pi/len));
for(int i=0;i<len/2;i++){
tmp[i]=l[i]+cur*l2[i];
tmp[i+len/2]=l[i]-cur*l2[i];
cur*=stp;
}
for(int i=0;i<len;i++)f[i]=tmp[i];
}
变换后再逆变换得到的结果比原数组大不少,这是什么问题?