#pragma once
#include"Complex.h"
class Fouier
{
Complex * data;
void fft(int start,int step,int len);
Complex W(int k,int n);//e^(-i*2*pi*k/n)
public:
Fouier(void);
~Fouier(void);
void fft();
};
#include "Fouier.h"
#include<iostream>
using namespace std;
#include<cmath>
#include<ctime>
#define DATALEN 32
#define KEYVALUE 10000 //生成隨機浮點(diǎn)數的值，保證分子和分母在這個(gè)值之內
#define PI 3.14159265358979323846
Fouier::Fouier(void)
{
data=new Complex[DATALEN];
srand(unsigned int(time(0)));
cout<<"源數據："<<endl;
for(int i=0;i<DATALEN;i++)
{
data[i]=(rand()%(KEYVALUE))/(double)(rand()%(KEYVALUE)+1);
if(i%5==0&&i!=0)
cout<<endl;
cout<<data[i]<<" ";
}
cout<<endl;
}
Fouier::~Fouier(void)
{
delete [] data;
}
Complex Fouier:: W(int k,int n)//歐拉公式
{
double alpha=-2*PI*k/n;
return Complex(cos(alpha),sin(alpha));
}
void Fouier::fft(int start,int step,int len)
{
if(len==1)//一個(gè)元素
{
//一個(gè)元素不需要變換
return ;
}
fft(start,step*2,len/2);//X1(k)
fft(start+step,step*2,len/2);//X2(k)
Complex X1,X2;
for(int i=0;i<len/2;i++)
{
X1=data[start+step*i*2];
X2=data[start+step*(i*2+1)];
//計算X(k):k=0~N/2-1
data[start+step*i]=X1+W(i,len)*X2;
//計算X(k):k=N/2~N-1
data[start+step*(i+len/2)]=X1-W(i,len)*X2;
}
}
void Fouier::fft()
{
fft(0,1,DATALEN);
cout<<"變換后數據："<<endl;
for(int i=0;i<DATALEN;i++)
{
if(i%5==0&&i!=0)
cout<<endl;
cout<<data[i]<<" ";
}
}
#pragma once
#include<iostream>
using namespace std;
class Complex//a+b*i
{
double a;//實(shí)數部分
double b;//虛數部分
public:
Complex(double a=0,double b=0);
//+操作
friend Complex operator +(Complex &x,Complex &y);
friend Complex operator +(double x,Complex &y);
friend Complex operator +(Complex &x,double y);
//-操作
friend Complex operator -(Complex &x,Complex &y);
friend Complex operator -(double x,Complex &y);
friend Complex operator -(Complex &x,double y);
//*操作
friend Complex operator *(Complex &x,Complex &y);
friend Complex operator *(double x,Complex &y);
friend Complex operator *(Complex &x,double y);
//=操作
Complex operator =(Complex &x);
Complex operator =(double x);
//<<操作
friend ostream & operator<<(ostream&out,Complex&c);
~Complex(void);
};
#include "Complex.h"
Complex::Complex(double a,double b)//虛部默認是0
{
this->a=a;
this->b=b;
}
Complex::~Complex(void)
{
}
Complex operator +(Complex &x,Complex &y)
{
return Complex(x.a+y.a,x.b+y.b);
}
Complex operator +(double x,Complex &y)
{
return Complex(x+y.a,y.b);
}
Complex operator +(Complex &x,double y)
{
return Complex(x.a+y,x.b);
}
Complex operator -(Complex &x,Complex &y)
{
return Complex(x.a-y.a,x.b-y.b);
}
Complex operator -(double x,Complex &y)
{
return Complex(x-y.a,-y.b);
}
Complex operator -(Complex &x,double y)
{
return Complex(x.a-y,x.b);
}
Complex operator *(Complex &x,Complex &y)
{
return Complex(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);
}
Complex operator *(double x,Complex &y)
{
return Complex(x*y.a,x*y.b);
}
Complex operator *(Complex &x,double y)
{
return Complex(x.a*y,x.b*y);
}
Complex Complex::operator =(Complex &x)
{
a=x.a;
b=x.b;
return *this;
}
Complex Complex::operator =(double x)
{
a=x;
b=0;
return *this;
}
ostream & operator<<(ostream&out,Complex&c)
{
if(c.a!=0||c.a==0&&c.b==0)
out<<c.a;
if(c.b!=0)
{
if(c.b>0)
out<<"+";
if(c.b!=1)
out<<c.b;
out<<"i";
}
return out;
}
#include<iostream>
using namespace std;
#include"Fouier.h"
int main()
{
Fouier f;
f.fft();
return 0;
}
