#include?
#include?


void?IFFT（double?x[]double?y[]int?n）//數(shù)組x存儲時域序列的實部，數(shù)組y存儲時域序列的虛部n代表N點FFT.
{
int?ijklmn1n2;
double?cc1ess1ttrti;


for（j?=?1i?=?1;?i<16;?i++）//計算?i?=?log2N；變量j進行每次自乘2，當j=n，即算出i的值.
{
?????m?=?i;
?????j?=?2*j;
?????if（（j?==?n））//此時判斷j是否與n相等時，j與2乘，所以n輸入時應該選為2的次方。
?????????break;
}


n1?=?n?-?1;?//計算蝶形圖的輸入下標（碼位倒讀）
for（j=0i=0;?i{
????if（i????{
?????????tr?=?x[j];
?????????ti?=?y[j];
?????????x[j]?=?x[i];
?????????y[j]?=?y[i];?
?????????x[i]?=?tr;
?????????y[i]?=?ti;?????????????????
????}
????k?=?n/2;
????while（k<（j+1））
????{
????????j?=?j?-?k;
????????k?=?k/2;??????????????
????}
????j?=?j?+?k;
}


n1?=?1;??//計算每一級的輸出，l為某一級，i為同一級的不同群，使用同一內(nèi)存（即位運算）
for（l=1;?l<=m;?l++）
{
????n1?=?2*n1;
????n2?=?n1/2;
????e?=?3.1415926/n2;
????c?=?1.0;
????s?=?0.0;
????c1?=?cos（e）;
????s1?=?sin（e）;
????for（j=0;?j????{
????????for（i=j;?i???????