#include <iostream.h>
#include <math.h>
#include <complex>
using namespace std;
typedef complex<double> Complex;
#define pi 3.14159265
int fft(Complex *a,int cishu)
{
Complex u,w,t;
unsigned int n=1,num2,nml,k,le,lei,ip;
double temp;
n<<=cishu;
num2=n>>1;
nml=n-1;
int i=0;
int j=0;
for(i=0;i<nml;i++)
{
if(i<j)
{
t=a[j];
a[j]=a[i];
a[i]=t;
}
k=num2;
while(k<=j)
{
j=j-k;
k=k>>1;
}
j=j+k;
}
le=1;
for(int m=1; m<=cishu;m++)
{
lei=le;
le<<=1;
u=Complex(1,0);
temp=pi/lei;
w=Complex(cos(temp),-sin(temp));
for(j=0;j<lei;j++)
{
for(i=j;i<n;i+=le)
{
ip=i+lei;
t=a[ip]*u;
a[ip]=a[i]-t;
a[i]=a[i]+t;
}
u=u*w;
}
}
return 0;
};
void main()
{
Complex input[8];
for(int i=0;i<8;i++)
{
input[i]=i;
}
fft(input,3);
for(i=0;i<8;i++)
{
cout<<real(input[i])<<"+"<<imag(input[i])<<"i"<<endl;
}
}
评论0