#include?
#include?
#include?“math.h“
using?namespace?std;

const?double?pi?=?3.1415926535897932;
const?int?N=256;

class?complex
{
public:
	//無參構造函數(shù)
	complex（）
	{
		re=0;
		im=0;
	}
	//有參構造函數(shù)
	complex（double?realdouble?imag）
	{
		re=real;
		im=imag;
	}
	//加法
	complex?operator?+?（complex&?c）
	{
		return?complex（?re?+?c.re??im?+?c.im?）;
	}
	//減法
	complex?operator?-?（complex&?c）
	{
		return?complex（?re?-?c.re??im?-?c.im?）;
	}
	//乘法
	complex?operator?*?（complex&?c）
	{
		return?complex（?（re?*?c.re）-（im?*?c.im）??（re?*?c.im）+（im?*?c.re）?）;
	}
	//除法
	complex?operator?/?（complex&?c）
	{
		return?complex（?（?re*c.re?+?im*c.im?）/（?c.re*c.re?+?c.im*c.im?）
			（（im?*?c.re）-（re?*?c.im））/（（c.re*c.re）+（c.im*c.im））?）;
	}
	//除2
	void?half（）
	{
		re=re/2;
		im=im/2;
	}

	//輸出到ostream
	void?insert（ostream&?out）
	{
		if（re>=0）?cout<<“?“;
		out<=0）?‘+‘:‘-‘）?<<‘j‘<=0）?im:（0-im））;
	}
	//顯示
	void?show（）
	{
		cout<=0）?‘+‘:‘-‘）?<<‘j‘<=0）?im:（0-im））?;
	}
	//設值
	void?setValue（double?realdouble?imag）
	{
		if（real>0.00000001||real		else?re=0;
		if（imag>0.00000001||imag		else?im=0;
	}

private:
	double?reim;
};

//流輸出
ostream&?operator?<{
	c.insert（out）;
	return?out;
}


//獲得Wn
void?getW（complex?w[]int?len）
{
	for（int?i=0;i	{
		w[i].setValue（?cos（0?-?pi*2*（i）/len）??sin（0?-?pi*2*（i）/len）?）;
	}
}

//倒序重排
void?resort（complex?X[]）
{
	double?len=N;
	int?L=log（len）/log（double（4））;
	int?in;
	complex?*temp?=?new?complex[N];
	for（i=0;i		temp[i]=X[i];
	for（i=0;i	{
		n=i;
		n=（（n&0xcccc）>>2）|（（n&0x3333）<<2）;
		n=（（n&0xf0f0）>>4）|（（n&0x0f0f）<<4）;
		n=（（n&0xff00）>>8）|（（n&0x00ff）<<8）;
		n=n>>（2*（8-L））;
		X[i]=temp[n];
	}
	delete[]temp;
}
//基2時間FFT
void?FFT2t（complex?x[]）
{
	//初始化
	double?len=N;
	int?L=log（len）/log（double（4））;
	int?lgkm;
	int?k0k1k2k3k4;
	int?gc2gi1gi2;
	complex?*temp?=?new?complex[N];
	complex?*w?=?new?complex[N];
	complex?*X=new?complex[4];
	complex?j（01）;
	getW（wN）;
	resort（x）;
	//開始迭代運算
	for（l=1;l<=L;l++）
	{
		gc2=1<<（2*（L-l））;

		gi2=1<<（2*l）;
		gi1=1<<（2*（l-1））;

		for（g=0;g			for（k=0;k			{
				k0=k+g*gi2;
				m=gc2*k;
				k1=k0;k2=k1+gi1;k3=k2+gi1;k4=k3+gi1;
				
				X[0]=x[k1];X[1]=w[m]*x[k2];X[2]=w[2*m]*x[k3];X[3]=w[3*m]*x[k4];

				temp[k1]=X[0]+X[1]+X[2]+X[3];
				temp[k2]=X[0]-j*X[1]-X[2]+j*X[3];
				temp[k3]=X[0]-X[1]+X[2]-X[3];
				temp[k4]=X[0]+j*X[1]-X[2]-j*X[3];
			}
		for（int?i=0;i			x[i]=temp[i];
	}
	delete[]Xw;
}

//主函數(shù)
void?main（）
{
	//初始化
	complex?q（0.90.3）;
	complex?x[N]w[N];
	int?i;
	getW（wN）;?//獲取Wn序列
	x[0].setValue（21）;
	for（i=1;i	{
		x[i]=x[i-1]*q;
	}
	//輸出原序列
	cout<<“原序列：“<	for（i=0;i<16;i+=2）
	{
		cout<