#include<stdio.h>
#include<string.h>
#include<math.h>
#define PI 3.1415926 
#define MAX 100

void main()
{int i=0;
 int *m=NULL;
 int *N=NULL;
  

 float x[MAX],y[MAX];                        /* y第一步幫助二進(jìn)制翻轉(zhuǎn)，然后第二步保存虛部*/
 void zero_add(float *,int *,int * );                      /*補(bǔ)零*/
 void FFT(float *,float *,int *,int *);
 void flip(float *,int *,int *,float *);/*翻轉(zhuǎn)*/
m=new int;                               /*m級(jí)數(shù)*/
N=new int;                               /*點(diǎn)的個(gè)數(shù)*/

  
  printf("輸入數(shù)據(jù):\n");
 scanf("%f",&x[i]);
  while(getchar()!='\n')
  {i++;
   scanf("%f",&x[i]);
   if(i>MAX)
	   printf("超過(guò)最大個(gè)數(shù)點(diǎn)");
     }
   *N=i+1;
  zero_add( x, N,m);/*補(bǔ)零*/
flip(x,N,m,y);           /*翻轉(zhuǎn) 重新排序*/ 
for(i=0;i<*N;i++)
{printf("%f\n",x[i]);
}

 FFT(x,y,m,N);
for(i=0;i<*N;i++)
{printf("X[%d]=(%f)+(%f)i\n",i,x[i],y[i]);
}


}  
 
void zero_add(float *x,int *N,int *m) /*補(bǔ)零*/
{int i,t;
 *m=(int)(log(*N)/log(2));
	t=(int)(pow(2,*m));
if(*N!=t)
  {(*m)++;
  }

  t=(int)(pow(2,*m));
  for(i=*N;i<t;i++)
  {x[i]=0;
  }
  *N=t;
}
void flip(float*x,int *N ,int *m,float *y)  /*排序*/
{int i,j;
int k;
float t;
for(i=0;i<*N;i++)
{j=i;
 k=*m;
y[i]=0;
	while(j!=0)
	{ k--;
		y[i]=y[i]+pow(2,k)*(j%2);
		j=j/2;
	}
}
  for(i=0;i<*N;i++)
  {  if(y[i]!=0)
  {  t=x[i];
      k=(int)(y[i]);
     x[i]=x[k];
     x[k]=t;
     y[i]=0;
     y[k]=0;
  }
  }
}
void FFT(float *x,float *y,int *m,int *N)
{int i,r,h,k,j;
float xp,xq,xp1,xq1,w;
 for(i=0;i<*m;i++)     /*實(shí)現(xiàn)m級(jí)運(yùn)算*/
 {h=(int)(pow(2,i));   /*計(jì)算步長(zhǎng)*/
	 for(r=0;r<pow(2,i);r++)/*r相同的分一組計(jì)算*/
	 { w=2*PI*r/pow(2,i+1); /*旋轉(zhuǎn)因子的值*/
		 for(j=0;j<(*N/pow(2,i+1));j++)/*r相同的值的組的計(jì)算*/
	 {k=(int)( r+j*pow(2,i+1));          /*每一組成員的下標(biāo)*/
		 
		 xp=x[k]+cos(w)*x[k+h]+sin(w)*y[k+h];/*蝶形計(jì)算*/
		 xp1=y[k]+cos(w)*y[k+h]-sin(w)*x[k+h];
		 xq=x[k]-cos(w)*x[k+h]-sin(w)*y[k+h];
		 xq1=y[k]-cos(w)*y[k+h]+sin(w)*x[k+h];
		 
		 x[k]=xp;
		 x[k+h]=xq;
		 y[k]=xp1;
		 y[k+h]=xq1;
			
			
	 }
	 }
 }
}