【正确答案】可用书上讨论的两种框图的任一种来编程。
   程序如下：
   基-2  FFT(频率抽取DIF法)算法程序
   /*Free_Copy*/
   /*C语言编写的频率抽取FFT算法(最大计算64点)*/
   /*输入：序列点数、序列值*/
   /*输出：序列FFT变换后的数值及反变换(应与原序列相同)*/
   #include"conio.h"
   #include"math.h"
   #include"stdio.h"
   #define N 64
   #define PI 3.1415926
   #define w0(0.125*PI)
   #define Cmul(a,b,c)a.x=b.x*c.x-b.y*c.y;a.y=b.x*c.y+b.y*c.x;
   #define CequaI(a,b)a.×=b.x;a.y=b.y;
   #define Cadd(a,b,c)a.x=b.x+c.x;a.y=b.y+c.y;
   #define Csub(a,b,c)a.x=b.x-c.x;a.y=b.y-c.y;
   #define Wn(w,r)w.x=cos(2.0*PI*r/n);w.y=-sin(2.0*PI*r/n);
   struct comp
   {
   float x;
   float y;
   };
   void main()
   {
   int i,j,nu2,nm1,n,m,le,le1,k,ip,z;
   int flag,f,n1;
   struct comp a[N],t,t1,w,d;
   float a_ipx,m1;
   printf("\nThis program is about FFT by DIF way. ");
   printf("\nplease enter N: ");
   scanf("/%d",&n1);
   n=n1;
   m1=log(n1)/log(2);
   m=log(n1)/log(2);
   if(m!=m1)  n=pow(2,m+1);
   for(i=0;i<n;i++){a[i].x=a[i].y=0.0;}
   printf("\n");
   for(i=0;i<n1;i++)
   {
   printf("\nplease enter data(/%d)_[Re]: ",i);
   scanf("/%f",&a[i].x);
   printf("\nplease enter data(/%d)_[Im]:",i);
   scanf("/%f",&a[i].y);
   }
   for(z=0;z<=1;z++)
   {
   flag=-1;
   for(m=(log(n)/log(2));m>=1;m--)
   {
   le=pow(2,m);
   flag++;
   lel=le/2;
   for(j=0;j<lel;j++)
   {
   for(i=j;i<-(n-1);i+=le)
   {
   ip=i+le1;
   Cequal(t,a[i]);
   Cequal(t1,a[ip]);
   f=(int)(i*pow(2,flag))/%n;
   Wn(w,f);
   Cadd(a[i],t,t1);
   Csub(a[ip],t,t1);
   a_ipx=a[ip].x;
   if(z--1)
   {
   w.y*=-1;
   }
   a[ip].x=a[ip].x*w.x-a[ip].y*w.y;
   a[ip].y=a_ipx*w.y+a[ip].y*w*x;
   }
   }
   }
   nu2=n/2;
   nml=n-2;
   j=0;i=0;
   while(i<=nm1)
   {
   if(i<j)
   {
   Cequal(d,a[j]);
   Cequal(a[j],a[i]);
   Cequal(a[i],d);
   }
   k=nu2;
   while(k<=j)
   {
   j=j-k;k=k/2;
   }
   j=j+k;
   i=i+1;
   }
   if(z==0)
   {
   printf("\n序列的fft是：\n\n");
   }
   else
   printf("\n用ifft计算出的原序列是：\n\n");
   for(i=0;i<n;i++)
   if(z==0)
   {
   printf("  /%7.3f",a[i].x);
   if(a[i].y>=0)
   printf("  +/%7.3f j \n",a[i].y);
   else
   printf("  -/%7.3f j \n",fabs(a[i].y));
   a[i].y=-a[i].y;
   }
   else
   {
   printf("  /%7.3f",a[i].x/n);
   a[i].y=-a[i].y/n;
   if(a[i].y>=0)
   printf("  +/%7.3f j \n",a[i].y);
   else
   printf("  -/%7.3f j\n",fabs(a[i].y));
   }
   }
   printf("\n");
   }
   ；分裂基FFT算法程序
   ；该段程序为分裂基FFT算法(C语言编写)
   /*Free_Copy*/
   /*主程序：64点分裂基FFT算法*/
   /*输入：64点任意序列*/
   /*输出：序列的FFT变换*/
   #include"conio.h";
   #include"math.h"
   #include"stdio.h"
   #define PI 3.1415926
   #define N 128
   void main()
   {
   float x[N],y[N],xt;
   float cc1,cc3,ss1,ss3;
   float r1,r2,r3,s1,s2,a,a3,e,m1;
   int n,n1,m,j,k,i;
   int is,id,i0,i1,i2,i3,n2,n4;
   printf("\nThis program is about FFT by SPEFT way.  ");
   printf("\nplease enter n:  ");
   scanf("/%d",＆n1);
   n=n1;
   m1=log(n1)/log(2);
   m=log(n1)/log(2);
   if(m!=m1)  n=pow(2,m+1);
   for(i=0;i<=N;i++)
   {
   x[i]=y[i]=0.0;
   }
   printf("\n");
   for(i=1;i<=n1;i++)
   {
   printf("\nplease enter data(/%d)_[Re]：",i);
   seanf("/%f",＆x[i]);
   printf("\nplease enter data(/%d)_[Im]:",i);
   scanf("/%f",＆y[i]);
   }
   j=1;
   for(i=1;i<=n-1;i++)
   {
   if(i<j)
   {
   xt=x[j];
   x[j]=x[i];
   x[i]=xt;
   xt=y[j];
   y[j]=y[i];
   y[i]=xt;
   }
   k=n/2;
   while(k<j)
   {
   j=j-k;
   k=k/2;
   }
   j=j+k;
   }
   is=1;
   id=4;
   while(is<n)
   {
   for(i0=is;i0<-n;iO+=id)
   {
   i1=i0+1;
   r1=x[i0];
   x[i0]=r1十x[i1];
   x[i1]=r1-x[i1];
   r1=y[i0];
   y[-i0]=r1+y[-i1];
   y[i1]=r1-y[i1];
   }
   is=2*id-1;
   id=4*id;
   }
   n2=2;
   for(k=2;k<=m;k++)
   {
   n2=n2*2;
   n4=n2/4;
   e=2.0*PI/n2;
   a=0.0;
   for(j=1;j<-n4;j++)
   {
   a3=3.0*a;
   cc1=cos(a);
   ss1=sin(a);
   cc3=cos(a3);
   ss3=sin(a3);
   a=j*e;
   is=j;
   id=2*n2;
   while(is<n)
   {
   for(i0=is;i0<=n-1;i0+=id)
   {
   i1=i0+n4;
   i2=i1+n4;
   i3=i2+n4;
   r1=x[i2]*cc1+y[i2]*ss1;
   s1=y[i2]*cc1-x[i2]*ss1;
   r2=x[i3]*cc3+y[i3]*ss3;
   s2=y[i3]*cc3-x[i3]*ss3;
   r3=r1+r2;
   r2=r1-r2;
   r1=s1+s2;
   s2=s1-s2;
   x[i2]=x[i0]-r3;
   x[i0]=x[i0]+r3;
   x[i3]=x[i1]-s2;
   x[i1]=x[i1]+s2;
   y[i2]=y[i0]-r1;
   y[i0]=y[i0]+r1;
   y[i3]=y[i1]+r2;
   y[i1]=y[i1]-r2;
   }
   is=2*id-n2+j;
   id=4*id;
   }
   }
   }
   printf("\n分裂基fft结果是：\n");
   for(i=1;i<=n;i++)
   {
   printf("\n/%7.3f,/%7.3f j",x[i],y[i]);
   y[i]=-y[i];
   }
   getch();
   printf("\n\n");
   }