求快速傅里叶变换的算法实现，C/C++/JAVA都行，要求适用于所有的整数，谢谢！

发布网友 发布时间：2022-05-16 21:44

我来回答

共1个回答

热心网友 时间：2023-09-12 06:53

#include<graphics.h>
#include<stdio.h>
#include<math.h>
#include<conio.h>
#include<dos.h>

float ar[2048],ai[2048];
float a[4100];

void testdata()
{
int i;
for(i=0;i<512;i++)
{
ar[i]=50*cos(i*3.14159/32)+60*cos(i*3.14159/16)+53*cos(i*3.14159/64)+24*cos(i*3.14159/8)+10*cos(i*3.14159/128);
ai[i]=0;
}
}

void fft(int nn,int t)
{
int n1,n2,i,j,k,l,m,s,l1;
float t1,t2,x,y;
float w1,w2,u1,u2,z;
float pi=3.14159;
switch(nn)
{
case 2048: s=11; break;
case 1024: s=10; break;
case 512: s=9; break;
case 256: s=8; break;
}

n1=nn/2; n2=nn-1;
j=1;
for(i=1;i<=nn;i++)
{
a[2*i]=ar[i-1];
a[2*i+1]=ai[i-1];
}
for(l=1;l<n2;l++)
{
if(l<j)
{
t1=a[2*j];
t2=a[2*j+1];
a[2*j]=a[2*l];
a[2*j+1]=a[2*l+1];
a[2*l]=t1;
a[2*l+1]=t2;
}
k=n1;
while (k<j)
{
j=j-k;
k=k/2;
}
j=j+k;
}
for(i=1;i<=s;i++)
{
u1=1;
u2=0;
m=(1<<i);
k=m>>1;
w1=cos(pi/k);
w2=t*sin(pi/k);
for(j=1;j<=k;j++)
{
for(l=j;l<nn;l=l+m)
{
l1=l+k;
t1=a[2*l1]*u1-a[2*l1+1]*u2;
t2=a[2*l1]*u2+a[2*l1+1]*u1;
a[2*l1]=a[2*l]-t1;
a[2*l1+1]=a[2*l+1]-t2;
a[2*l]=a[2*l]+t1;
a[2*l+1]=a[2*l+1]+t2;
}
z=u1*w1-u2*w2;
u2=u1*w2+u2*w1;
u1=z;
}
}
for(i=1;i<=nn/2;i++)
{
ar[i]=a[2*i+2]/nn;
ai[i]=-a[2*i+3]/nn;
a[i]=4*sqrt(ar[i]*ar[i]+ai[i]*ai[i]);
}
}

int main ()
{
int i;
int gdriver=DETECT,gmode;
initgraph(&gdriver,&gmode,"");
setfillstyle(SOLID_FILL,WHITE);
bar(0,0,639,479);
//模拟测试数据
testdata();
//波形显示
setcolor(BLACK);
line(10,119,550,119); // x轴
line(10,10,10,239); // y轴
setcolor(BLUE);
for(i=0;i<511;i++)
line(i+10,119-ar[i],i+10+1,119-ar[i+1]);
//FFT
fft(512,-1);

//频谱显示
setcolor(BLACK);
line(10,459,550,459); // x轴
line(10,259,10,459); // y轴
setcolor(RED);
for(i=0;i<256;i++)
line(2*i+10,459-a[i],2*i+10,459);
getch();
closegraph();
return 0;
}