fft.cpp

简单的fft控制台程序

#include<iostream.h>
#include<math.h>
#define PI 3.141592653
int n;
void ComplexMult(float*x,int num)
{
	float temp=*(x);
	*(x)=(*(x))*cos(-2*PI*num/n)-(*(x+1))*sin(-2*PI*num/n);
	*(x+1)=cos(-2*PI*num/n)*(*(x+1))+sin(-2*PI*num/n)*temp;
}
void main()
{
	cout<<"请输入序列长度"<<endl;
	cin>>n;
    float **x;
	x=new float*[n];
	for(int i=0;i<n;i++)
	{
		x[i]=new float[2];
	}
     for(i=0;i<n;i++)
	{
		cin>>x[i][0];
		x[i][1]=0;
	}
	int nn=n;
	int m3=1;
	while(1)
	{
		nn/=2;
		if(nn==1)
			break;
		m3++;
	}
    int next1=1;
	int next2=n/2;
	for(i=0;i<n/4;i++)
	{
		float temp1,temp2;
		temp1=x[next1][0];
		temp2=x[next1][1];
		x[next1][0]=x[next2][0];
		x[next1][1]=x[next2][1];
		x[next2][0]=temp1;
		x[next2][1]=temp2;
		next1+=2;
		next2+=2;

	}
	int m=2;
	int m1=n/2;
	int m2=1;
	int num=0;
	for(i=1;i<=m3;i++)
	{
		for(int j=0;j<n;j++)
		{
			
			if((m/2)<=(j%m))
			{
                ComplexMult(x[j],num);
				num+=m1;
				if(num==n/2)
					num=0;
			}
		}
		for(j=0;j<n;j+=m)
		{
			for(int k=j;k<j+m2;k++)
			{
				float temp1=x[k][0];
				float temp2=x[k][1];
			    x[k][0]=x[k][0]+x[k+m2][0];
				x[k][1]=x[k][1]+x[k+m2][1];
				x[k+m2][0]=temp1-x[k+m2][0];
				x[k+m2][1]=temp2-x[k+m2][1];
			}
		}
		m1/=2;
		m2*=2;
		m*=2;

	}
	cout<<"序列经过FFT后为"<<endl;
    for(i=0;i<n;i++)
	{
		if(x[i][1]==0)
			cout<<x[i][0]<<endl;
		else if(x[i][1]>0)
			cout<<x[i][0]<<"+"<<x[i][1]<<"i"<<endl;
		else
			cout<<x[i][0]<<x[i][1]<<"i"<<endl;
	}

}