#include?
#include?
#include?

#define?N?4096											//設置抽樣點數
#define?PI?3.1514926535897932384626433832795028841971	//定義圓周率

typedef?struct											//定義復數結構體變量
{
	double?real;
	double?imag;
}complex;

void?c_plus（complex?complex?complex?*）;				//復數加運算
void?c_sub（complex?complex?complex?*）;				//復數減運算
void?c_mul（complex?complex?complex?*）;				//復數乘運算
void?Wn_i（int?int?complex?*）;							//FFT旋轉因子
void?Wn_ik（int?int?int?complex?*）;					//DFT旋轉因子

int?main（）
{
	complex?f[N]?A[N]?a[N];							//f[N]為輸出的快速傅里葉變換序列	A[N]為DFT變換輸出序列	a[N]為初始序列
	double?x[N]?=?{?1?2?3?4?5?6?7?8?};			//x[N]為進行抽樣運算的序列
	int?LH?K?J?B?L?k?N1?P?M?K1;				//L表示第L級蝶形	p旋轉因子指數	B兩序列間隔點數k	第k個序列
	double?T;
	clock_t?begin?end;
	double?cost1?cost2?persent;						//定義時間
	M?=?（int）（log2（N））;
	LH?=?N?/?2;
	J?=?LH;
	N1?=?N?-?1;
	for?（int?i?=?0;?i?	{
		a[i].real?=?x[i];
		a[i].imag?=?0;
	}
	printf（“*******************************??級數為：%d??*******************************\n“?M）;
	//.......................................................................................................................
	for?（int?I?=?1;?I?	{
		if?（I?		{
			T?=?x[I];
			x[I]?=?x[J];
			x[J]?=?T;
		}
		K?=?LH;
		if?（J?>=?K）
		{
			do
			{
				J?=?J?-?K;
				K?=?K?/?2;
			}?while?（J?>=?K）;
		}
		J?=?J?+?K;
	}
	//.......................................................................................................................
	/*	for?（int?i?=?0;?i?	{
	printf（“x[%d]為：%lf\n“?i?x[i]）;
	}*/
	//.......................................................................................................................
	for?（int?i?=?0;?i?	{
		f[i].real?=?x[i];
		f[i].imag?=?0;
	}
	/*	for?（int?i?=?0;?i?	{
	printf（“f[%d]為：%lf	+	j%lf\n“?i?f[i].real?f[i].imag）;
	}*/
	//.......................................................................................................................
	begin?=?clock（）;									//開始記錄時間
	for?（L?=?1;?L?<=?M;?L++）							//FFT運算
	{
		B?=?（int）（pow（2?L?-?1））;
		for?（J?=?0;?J?		{
			P?=?（int）（J*pow（2?M?-?L））;
			for?（k?=?J;?k?			{
				K1?=?k?+?B;
				complex?wn?t;
				Wn_i（N?P?&wn）;
				c_mul（f[K1]?wn?&t）;					//。。。。。。。。。。。。
				c_sub（f[k]?t?&（f[K1]））;				//蝶形運算
				c_plus（f[k]?t?&（f[k]））;				//。。。。。。。。。。。。
			}
		}
	}
	end?=?clock（）;										//結束記錄時間
	cost1?=?（double）（end?-?begin）?/?CLOCKS_PER_SEC;
	//.......................................................................................................................
	printf（“*****************************快速傅里葉變換輸出*****************************\n“）;
	for?（int?i?=?0;?i?	{
		printf（“f[%d]為：	%lf	+	j（%lf）\n“?i?f[i].real?f[i].imag）;
	}
	//..............................................

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2018-12-07?22:19??ConsoleApplication5\
?????目錄???????????0??2018-12-07?22:19??ConsoleApplication5\ConsoleApplication5\
?????文件????????4094??2018-11-23?14:42??ConsoleApplication5\ConsoleApplication5\ConsoleApplication5.vcxproj
?????文件?????????943??2018-11-23?14:42??ConsoleApplication5\ConsoleApplication5\ConsoleApplication5.vcxproj.filters
?????目錄???????????0??2018-12-07?22:19??ConsoleApplication5\ConsoleApplication5\Debug\
?????目錄???????????0??2018-12-07?22:19??ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\
?????文件????????1414??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\CL.read.1.tlog
?????文件?????????768??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\CL.write.1.tlog
?????文件?????????194??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\ConsoleApplication5.lastbuildstate
?????文件?????????788??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\cl.command.1.tlog
?????文件????????1442??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\link.command.1.tlog
?????文件????????2450??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\link.read.1.tlog
?????文件?????????750??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\link.write.1.tlog
?????文件????????1593??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\ConsoleApplication5.log
?????文件???????17666??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\time.obj
?????文件???????27648??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\vc120.idb
?????文件???????77824??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\Debug\vc120.pdb
?????文件????????5121??2018-11-30?21:48??ConsoleApplication5\ConsoleApplication5\time.c
?????文件?????2490368??2018-12-07?22:18??ConsoleApplication5\ConsoleApplication5.sdf
?????文件????????1003??2018-11-23?14:27??ConsoleApplication5\ConsoleApplication5.sln
?????文件???????16896??2018-12-07?22:18??ConsoleApplication5\ConsoleApplication5.v12.suo
?????目錄???????????0??2018-12-07?22:19??ConsoleApplication5\Debug\
?????文件???????36864??2018-11-30?21:48??ConsoleApplication5\Debug\ConsoleApplication5.exe
?????文件??????268956??2018-11-30?21:48??ConsoleApplication5\Debug\ConsoleApplication5.ilk
?????文件??????486400??2018-11-30?21:48??ConsoleApplication5\Debug\ConsoleApplication5.pdb
?????文件????????4974??2018-11-30?10:47??time.txt