//?FFT.cpp?:?此文件包含?“main“?函數。程序執行將在此處開始并結束。
//

#include?“pch.h“

#include?

#include?

#include?



#define?N?1000

/*定義復數類型*/

typedef?struct?{

	double?real;

	double?img;

}complex;





complex?x[N]?*W;?/*輸入序列變換核*/

int?size_x?=?0;??????/*輸入序列的大小，在本程序中僅限2的次冪*/

double?PI;?????????/*圓周率*/

void?fft（）;?????/*快速傅里葉變換*/

void?initW（）;???/*初始化變換核*/

void?change（）;?/*變址*/

void?add（complex?complex?complex?*）;?/*復數加法*/

void?mul（complex?complex?complex?*）;?/*復數乘法*/

void?sub（complex?complex?complex?*）;?/*復數減法*/

void?output（）;/*輸出快速傅里葉變換的結果*/









int?main（）

{

	int?i;?????????????????????????????/*輸出結果*/

	system（“cls“）;

	PI?=?atan（1）?*?4;

	printf（“????????????????????????????????????????輸出DIT方法實現的FFT結果\n“）;

	printf（“Please?input?the?size?of?x:\n“）;//輸入序列的大小

	scanf（“%d“?&size_x）;

	printf（“Please?input?the?data?in?x[N]:\n“）;//輸入序列的實部和虛部

	for?（i?=?0;?i?
	{

		printf（“請輸入第%d個序列：“?i）;

		scanf（“%lf%lf“?&x[i].real?&x[i].img）;

	}

	printf（“輸出倒序后的序列\n“）;

	initW（）;//調用變換核

	fft（）;//調用快速傅里葉變換

	printf（“輸出FFT后的結果\n“）;

	output（）;//調用輸出傅里葉變換結果函數

	return?0;

}







/*快速傅里葉變換*/

void?fft（）

{

	int?i?=?0?j?=?0?k?=?0?l?=?0;

	complex?up?down?product;

	change（）;??//調用變址函數

	for?（i?=?0;?i?
	{

		l?=?1?<
		for?（j?=?0;?j?
		{

			for?（k?=?0;?k?
			{

				mul（x[j?+?k?+?l]?W[size_x*k?/?2?/?l]?&product）;