第四章习题与答案.doc 15页

'解:⑴直接计算:复乘所需时间:复加所需时间:⑵用FFT计算:复乘所需时间:复加所需时间: 由（1）式可得的路径，如下表所示:k01234567890.80.670.560.460.390.320.270.220.190.16arg[] 8.请用C语言编写程序:(1)按频率抽取的FFT算法(2)分裂基FFT算法基-2FFT(频率抽取DIF法)算法程序/*Free_Copy*/ /*C语言编写的频率抽取FFT算法(最大计算64点）*//*输入:序列点数、序列值*//*输出:序列FFT变换后的数值及反变换(应与原序列相同)*/#include"conio.h"#include"math.h"#include"stdio.h"#defineN64#definePI3.1415926#definew0(0.125*PI)#defineCmul(a,b,c)a.x=b.x*c.x-b.y*c.y;a.y=b.x*c.y+b.y*c.x;#defineCequal(a,b)a.x=b.x;a.y=b.y;#defineCadd(a,b,c)a.x=b.x+c.x;a.y=b.y+c.y;#defineCsub(a,b,c)a.x=b.x-c.x;a.y=b.y-c.y;#defineWn(w,r)w.x=cos(2.0*PI*r/n);w.y=-sin(2.0*PI*r/n);structcomp{floatx;floaty;};voidmain(){inti,j,nu2,nm1,n,m,le,le1,k,ip,z;intflag,f,n1;structcompa[N],t,t1,w,d;floata_ipx,m1;printf("nThisprogramisaboutFFTbyDIFway.");printf("npleaseenterN:");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=1;m--){le=pow(2,m);flag++;le1=le/2;for(j=0;j=0)printf("+%7.3fjn",a[i].y);elseprintf("-%7.3fjn",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.3fjn",a[i].y);elseprintf("-%7.3fjn",fabs(a[i].y));}}printf("n");}分裂基FFT算法程序/*Free_Copy*//*主程序:64点分裂基FFT算法*//*输入:64点任意序列*//*输出:序列的FFT变换*/#include"conio.h";#include"math.h"#include"stdio.h"#definePI3.1415926#defineN128 voidmain(){floatx[N],y[N],xt;floatcc1,cc3,ss1,ss3;floatr1,r2,r3,s1,s2,a,a3,e,m1;intn,n1,m,j,k,i;intis,id,i0,i1,i2,i3,n2,n4;printf("nThisprogramisaboutFFTbySPEFTway.");printf("npleaseentern:");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("npleaseenterdata(%d)_[Re]:",i);scanf("%f",&x[i]);printf("npleaseenterdata(%d)_[Im]:",i);scanf("%f",&y[i]);}j=1;for(i=1;i<=n-1;i++){if(i