#include <reg51.h>
#include "stdio.h"
#include <math.h>       //調(diào)用源（頭）文件

struct compx           /*定義一個(gè)複數(shù)結(jié)構(gòu)*/
{float real;float imag;
};
struct compx s[ 257 ];      //FFT輸入輸出均從是s[1]開始存入
struct compx EE(struct compx,struct compx); //定義複數(shù)相乘結(jié)構(gòu)
void FFT(struct compx xin,int N);   /*定義FFT函數(shù)*/
struct compx EE(struct compx a1,struct compx b2) //兩複數(shù)相乘的程序
{struct compx b3;  //b3保存兩複數(shù)間的結(jié)果
b3.real=a1.real*b2.real-a1.imag*b2.imag; //兩複數(shù)間的運(yùn)算
b3.imag=a1.real*b2.imag+a1.imag*b2.real;
return(b3);    /*返回結(jié)果*/
}

void FFT(struct compx xin,int N)   /*FFT函數(shù)體*/
{int f,m,nv2,nm1,i,k,j=1,l;   /*定義變量*/
struct compx v,w,t;    /*定義結(jié)構(gòu)變量*/
nv2=N/2;           /*最高位值的權(quán)值*/
f=N;                  /*f為中間變量*/
for(m=1;(f=f/2)!=1;m++){;}            /*求級(jí)數(shù)m*/
nm1=N-1;                               /*nm1為數(shù)組長(zhǎng)度*/
for(i=1;i<=nm1;i++)                   /*倒序*/
{if(i<j) {t=xin[ j ];xin[j]=xin[ i ];xin[ i ] =t;}         /*i<j則換位*/
k=nv2;                       /*k為倒序中相應(yīng)位置的權(quán)值*/
while(k<j) {j=j-k;k=k/2;}            /*k<j時(shí)最高為變?yōu)?*/
j=j+k;                  /* j為數(shù)組中的位數(shù)，是一個(gè)十進(jìn)制數(shù)*/ 
} 
{int le,lei,ip;       //變量初始化,le為序列長(zhǎng)度
  float pi;
  for(l=1;l<=m;l++)                /*l控制級(jí)數(shù)*/
   {le=pow(2,l);                  /*le等於2的l次方*/
    lei=le/2;                   /*蝶形兩節(jié)點(diǎn)間的距離*/
    pi=3.14159265;
    v.real=1.0;                    // 此次的v運(yùn)於複數(shù)的初始化    v.imag=0.0;  
   w.real=cos(pi/lei);                  /*旋轉(zhuǎn)因子*/
    w.imag=-sin(pi/lei);
    for(j=1;j<=lei;j++)      //外循環(huán)控制蝶行運(yùn)算的級(jí)數(shù)
     {for(i=j;i<=N;i=i+le)      //內(nèi)循環(huán)控制每級(jí)間的運(yùn)算次數(shù) 
      {ip=i+lei;                 /*蝶形運(yùn)算的下一個(gè)節(jié)點(diǎn)*/
       t=EE(xin[ ip ],v);             /*第一個(gè)旋轉(zhuǎn)因子*/
       xin[ ip ].real=xin[ i ].real-t.real;   /*蝶形計(jì)算*/
       xin[ ip ].imag=xin[ i ].imag-t.imag;
       xin[ i ].real=xin[ i ].real+t.real;
       xin[ i ].imag=xin[ i ].imag+t.imag;
      }
      v=EE(v,w); //調(diào)用EE複數(shù)相乘程序，結(jié)果給下次的循環(huán)    
      }     
   }
  }
}

main()                    /*定義主函數(shù)*/
{int N,i;     //變量初始化，N為總點(diǎn)數(shù)，i為每點(diǎn)數(shù)
printf("shu ru N de ge shu N=");  /*提示輸入*/
scanf("%d",&N);                   /*輸入N*/
for(i=1;i<=N;i++)              /*輸入*/
  {printf("di %d ge shu real=",i); 
   getchar();  
   scanf("%f",&s[ i ].real);
   getchar();   
   printf("\n");
   printf("di %d ge shu imag=",i);
   scanf("%f",&s[ i ].imag);
   printf("\n");
  }  
  FFT(s,N);               /*調(diào)用FFt*/
  for(i=1;i<=N;i++)                 /*輸出*/
   {printf("%f",s[ i ].real);
   printf(" + ");
    printf("%f",s[ i ].imag);
    printf("j");
    printf("\n");
   }  
}