FFT快速福利叶变换

1、#include"stdio.h"#include"math.h"typedef structfloat Re;float Im;complex;void main()complex add(complex,complex);complex minus(complex,complex);complex mul(complex,complex);complex W(int,int);complex T(int); void print(complex );int M,N;int a100,b100;int i,j,m,k;int x=2; int F(in

2、t,int);complex c100,d100,ml;printf("请输入所要求的序列x(n)的长度N=2 M=");scanf("%d",&M);N=F(x,M);printf("你所求的傅立叶变换长度N=%dn",N);printf("请输入序列x(n):n");for(i=0;i<N;i+)scanf("%d",&ai);b0=0;for(i=0;i<M;i+)for(j=0;j<F(2,i);j+)bF(2,i)+j=bj+F(2,M-i-1);fo

3、r(i=0;i<N;i+)printf("%d,",abi);printf("n");for(i=0;i<N;i+)ci=T(abi); for(i=1;i<M+1;i+) m=F(2,i); for(j=0;j<N/m;j+) for(k=0;k<m/2;k+) ml=mul(W(m,k),cm*j+m/2+k); dm*j+k=add(cm*j+k,ml); dm*j+m/2+k=minus(cm*j+k,ml); for(int l=0;l<N;l+) cl=dl; for(i=0;i<N;i+) prin

4、tf("X(%d)=",i); print(ci); int F(int b,int a) int c;if(a>=0) if(a>0) c=b*F(b,(a-1);else c=1;return c; complex add(complex z1,complex z2)complex z;z.Re=z1.Re+z2.Re;z.Im=z1.Im+z2.Im;return z;complex minus(complex z1,complex z2)complex z;z.Re=z1.Re-z2.Re;z.Im=z1.Im-z2.Im;return z;complex mul(complex z1,complex z2)complex z;return z;complex T(int a)complex c;c.Re=(float)a;c.Im=0;return c;void print(complex a)float x,y;x=a.Re;y=a.Im;if(y=0)printf("%.4fn",x);elseprintf("%.4f+%.4fin",x,y);complex W(int n,int k)complex