傅里葉變換c語言實現-九游会j9娱乐平台

❶ 求個快速傅里葉變換的c語言程序

voidfft()
{
intnn,n1,n2,i,j,k,l,m,s,l1;
floatar[1024],ai[1024];//實部虛部
floata[2050];

floatt1,t2,x,y;
floatw1,w2,u1,u2,z;
floatfsin[10]={0.000000,1.000000,0.707107,0.3826834,0.1950903,0.09801713,0.04906767,0.02454123,0.01227154,0.00613588,};//優化
floatfcos[10]={-1.000000,0.000000,0.7071068,0.9238796,0.9807853,0.99518472,0.99879545,0.9996988,0.9999247,0.9999812,};
nn=1024;
s=10;

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{
if(l{
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-k;
k=k/2;
}
j=j k;
}
for(i=1;i<=s;i  )
{
u1=1;
u2=0;
m=(1<k=m>>1;
w1=fcos[i-1];
w2=-fsin[i-1];
for(j=1;j<=k;j  )
{
for(l=j;l{
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]);//幅值
}
}

❷ 一個關於128點的快速傅立葉的c語言程序

這是我寫的1024點的快速傅里葉變換程序，下面有驗證，你把數組
double
a[2049]={0};
double
b[1100]={0};
double
powera[1025]={0};
改成
a[256]={0};
b[130]={0};
power[129]={0};就行了，
void
fft(double
data[],
int
nn,
int
isign)
的程序可以針對任何點數，只要是2的n次方
具體程序如下：
#include

#include
"math.h"
#include
#include
#include

#include

#include

void
fft(double
data[],
int
nn,
int
isign)
{
//復數的快速傅里葉變換
int
n,j,i,m,mmax,istep;
double
tempr,tempi,theta,wpr,wpi,wr,wi,wtemp;
n
=
2
*
nn;
j
=
1;
for
(i
=
1;
i<=n
;
i=i 2)
//這個循環進行的是碼位倒置。
{
if(
j
>
i)
{
tempr
=
data[j];
tempi
=
data[j

1];
data[j]
=
data[i];
data[j

1]
=
data[i

1];
data[i]
=
tempr;
data[i

1]
=
tempi;
}
m
=
n
/
2;
while
(m
>=
2
&&
j
>
m)
{
j
=
j
-
m;
m
=
m
/
2;
}
j
=
j

m;
}
mmax
=
2;
while(
n
>
mmax
)
{
istep
=
2
*
mmax;
//這里表示一次的數字的變化。也體現了級數，若第一級時，也就是書是的第0級，其為兩個虛數，所以對應數組應該增加4，這樣就可以進入下一組運算
theta
=
-6.28318530717959
/
(isign
*
mmax);
wpr
=
-2.0
*
sin(0.5
*
theta)*sin(0.5
*
theta);
wpi
=
sin(theta);
wr
=
1.0;
wi
=
0.0;
for(
m
=
1;
m<=mmax;
m=m 2)
{
for
(i
=
m;
i<=n;
i=i istep)
{
j
=
i

mmax;
tempr=double(wr)*data[j]-double(wi)*data[j 1];//這兩句表示蝶形因子的下一個數乘以w因子所得的實部和虛部。
tempi=double(wr)*data[j 1] double(wi)*data[j];
data[j]
=
data[i]
-
tempr;
//蝶形單元計算後下面單元的實部，下面為虛部，注意其變換之後的數組序號與書上蝶形單元是一致的
data[j

1]
=
data[i

1]
-
tempi;
data[i]
=
data[i]

tempr;
data[i

1]
=
data[i

1]

tempi;
}
wtemp
=
wr;
wr
=
wr
*
wpr
-
wi
*
wpi

wr;
wi
=
wi
*
wpr

wtemp
*
wpi

wi;
}
mmax
=
istep;
}
}
void
main()
{
//本程序已經和matlab運算結果對比，准確無誤，需要注意的的是，計算中數組都是從1開始取得，丟棄了a[0]等數據
double
a[2049]={0};
double
b[1100]={0};
double
powera[1025]={0};
char
line[50];
char
dataa[20],
datab[20];
int
ij;
char
ch1[3]="\t";
char
ch2[3]="\n";
int
strl1,strl2;
cstring
str1,str2;
ij=1;
//********************************讀入文件data1024.txt中的數據,
其中的數據格式見該文件
file
*fp
=
fopen("data1024.txt","r");
if(!fp)
{
cout<<"open
file
is
failing!"<return;
}
while(!feof(fp))
//feof(fp)有兩個返回值:如果遇到文件結束，函數feof（fp）的值為1，否則為0。
{
memset(line,0,50);
//清空為0
memset(dataa,0,20);
memset(datab,0,20);
fgets(line,50,fp);
//函數的功能是從fp所指文件中讀入n-1個字元放入line為起始地址的空間內
sscanf(line,
"%s%s",
dataa,
datab);
//我同時讀入了兩列值，但你要求1024個，那麼我就只用了第一列的1024個值
//dataa讀入第一列，datab讀入第二列
b[ij]=atof(dataa);
//將字元型的dataa值轉化為float型
ij ;
}
for
(int
mm=1;mm<1025;mm )//a[2*mm-1]是實部，a[2*mm]是虛部，當只要輸入實數時，那麼保證虛部a[mm*2]為零即可
{
a[2*mm-1]=b[mm];
a[2*mm]=0;
}
//*******************************************正式計算fft
fft(a,1024,1);
//********************************************寫入數據到workout.txt文件中
for
(int
k=1;k<2049;k=k 2)
{
powera[(k 1)/2]=sqrt(pow(a[k],2.0) pow(a[k 1],2.0));//求功率譜
file
*pfile=fopen("workout.txt","a ");
//?a 只能在文件最後補充，游標在結尾。沒有則創建
memset(ch1,0,15);
str1.format("%.4f",powera[(k 1)/2]);
if
(a[k 1]>=0)
str2.format("%d\t%6.4f%s%6.4f
%s",(k 1)/2,a[k]," ",a[k 1],"i");//保存fft計算的頻譜，是復數頻譜
else
str2.format("%d\t%6.4f%6.4f
%s",(k 1)/2,a[k],a[k 1],"i");
strl1=strlen(str1);
strl2=strlen(str2);
//
用
法:fwrite(buffer,size,count,fp);
//
buffer：是一個指針，對fwrite來說，是要輸出數據的地址。
//
size：要寫入的位元組數；
//
count:要進行寫入size位元組的數據項的個數；
//
fp:目標文件指針。
fwrite(str2,1,strl2,pfile);
fwrite(ch1,1,3,pfile);
fwrite(ch1,1,3,pfile);
fwrite(str1,1,strl1,pfile);
fwrite(ch2,1,3,pfile);
fclose(pfile);
}
cout<<"計算完畢，到fft_test\workout.txt查看結果"<}

❸ 怎樣用c語言實現fft演算法啊

1、二維fft相當於對行和列分別進行一維fft運算。具體的實現辦法如下：
先對各行逐一進行一維fft，然後再對變換後的新矩陣的各列逐一進行一維fft。相應的偽代碼如下所示：
for (int i=0; ifft_1d(row[i]，n);
for (int j=0; jfft_1d(col[j]，m);
其中，row[i]表示矩陣的第i行。注意這只是一個簡單的記法，並不能完全照抄。還需要通過一些語句來生成各行的數據。同理，col[i]是對矩陣的第i列的一種簡單表示方法。
所以，關鍵是一維fft演算法的實現。

2、常式：

#include
#include
#include
#definen1000
/*定義復數類型*/
typedefstruct{
doublereal;
doubleimg;
}complex;
complexx[n],*w;/*輸入序列,變換核*/
intsize_x=0;/*輸入序列的大小，在本程序中僅限2的次冪*/
doublepi;/*圓周率*/
voidfft();/*快速傅里葉變換*/
voidinitw();/*初始化變換核*/
voidchange();/*變址*/
voidadd(complex,complex,complex*);/*復數加法*/
voidmul(complex,complex,complex*);/*復數乘法*/
voidsub(complex,complex,complex*);/*復數減法*/
voidoutput();
intmain(){
inti;/*輸出結果*/
system("cls");
pi=atan(1)*4;
printf("pleaseinputthesizeofx:
");
scanf("%d",&size_x);
printf("pleaseinputthedatainx[n]:
");
for(i=0;iscanf("%lf%lf",&x[i].real,&x[i].img);
initw();
fft();
output();
return0;
}
/*快速傅里葉變換*/
voidfft(){
inti=0,j=0,k=0,l=0;
complexup,down,proct;
change();
for(i=0;il=1<for(j=0;jfor(k=0;kmul(x[j k l],w[size_x*k/2/l],&proct);
add(x[j k],proct,&up);
sub(x[j k],proct,&down);
x[j k]=up;
x[j k l]=down;
}
}
}
}
/*初始化變換核*/
voidinitw(){
inti;
w=(complex*)malloc(sizeof(complex)*size_x);
for(i=0;iw[i].real=cos(2*pi/size_x*i);
w[i].img=-1*sin(2*pi/size_x*i);
}
}
/*變址計算，將x(n)碼位倒置*/
voidchange(){
complextemp;
unsignedshorti=0,j=0,k=0;
doublet;
for(i=0;ik=i;j=0;
t=(log(size_x)/log(2));
while((t--)>0){
j=j<<1;
j|=(k&1);
k=k>>1;
}
if(j>i){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
}
/*輸出傅里葉變換的結果*/
voidoutput(){
inti;
printf("theresultareasfollows
");
for(i=0;iprintf("%.4f",x[i].real);
if(x[i].img>=0.0001)printf(" %.4fj
",x[i].img);
elseif(fabs(x[i].img)<0.0001)printf("
");
elseprintf("%.4fj
",x[i].img);
}
}
voidadd(complexa,complexb,complex*c){
c->real=a.real b.real;
c->img=a.img b.img;
}
voidmul(complexa,complexb,complex*c){
c->real=a.real*b.real-a.img*b.img;
c->img=a.real*b.img a.img*b.real;
}
voidsub(complexa,complexb,complex*c){
c->real=a.real-b.real;
c->img=a.img-b.img;
}

❹ 求基2、基4、基8fft（快速傅里葉變換）的c語言程序，要能運行得出來的

#include
#include
#include

typedef struct{
double r;
double i;
}my_complex
;

//檢查a是否為2的整數次方數
#define not2pow(a) (((a)-1)&(a)||(a)<=0)
//pi
#define mypi 3.14159265358979323846

my_complex* fft(const my_complex* x, unsigned int len){
unsigned int ex=0,t=len;
unsigned int i,j,k;
my_complex *y;
double tr,ti,rr,ri,yr,yi;

if(not2pow(len)) return null; //如果失敗，返回空指針
for(;!(t&1);t>>=1) ex ; //len應該等於2的ex次方

y=(my_complex*)malloc(len*sizeof(my_complex));
if(!y) return null;

//變址計算，庫里-圖基演算法
for(i=0;i k=i;
j=0;
t=ex;
while((t--)>0){
j<<=1;
j|=k&1;
k>>=1;
}
if(j>=i){
y[i]=x[j];
y[j]=x[i];
}
}

//用變址後的y向量進行計算
for(i=0;i t=1< for(j=0;j for(k=0;k ti=-mypi*k/t;
rr=cos(ti);
ri=sin(ti);

tr=y[j k t].r;
ti=y[j k t].i;

yr=rr*tr-ri*ti;
yi=rr*ti ri*tr;

tr=y[j k].r;
ti=y[j k].i;

y[j k].r=tr yr;
y[j k].i=ti yi;
y[j k t].r=tr-yr;
y[j k t].i=ti-yi;
}
}
}

return y;
}

//以下為測試
int main()
{
int i,data_len;
my_complex *x,*y;

printf("基二fft測試\n輸入生成序列長度:");
scanf("%d",&data_len);
x=(my_complex*)malloc(data_len*sizeof(my_complex));

for(i=0;i x[i].r=i;
x[i].i=i-1;
}

printf("處理前...\n實部\t\t虛部\n");
for(i=0;i printf("%lf\t%lf\n",x[i].r,x[i].i);

y=fft(x,data_len);
if(!y){
printf("序列長度不為2的整數次方!\n");
return 0;
}

printf("處理後...\n實部\t\t虛部\n");
for(i=0;i printf("%lf\t%lf\n",y[i].r,y[i].i);

free(y);
free(x);

return 0;
}

❺ 音頻演算法入門-傅里葉變換

    上一篇文章中講了一個時域處理的演算法wsola，接下來會學習頻域處理演算法，在這之前必須得對頻域有所了解，這就不得不提傅里葉變換了，本文的目的是讓大家學會用傅里葉變換公式和傅里葉逆變換公式進行計算。數學公式是人們對世界中的現象的描述，我們學習數學公式也不該只停留在使用公式來解決問題的層次，得明白公式到底在描述什麼現象，從這些天才數學家的角度來看世界。懂的地方可跳過。項目地址在文章末尾給出。

   我直接說結論，傅里葉級數公式包含了傅里葉變換和傅里葉逆變換（不嚴謹的說就是這么回事）。
    先簡單說下具體關系，法國數學家傅里葉發現，任何周期函數都可以用正弦函數和餘弦函數構成的無窮級數來表示，這種表示方式就是傅里葉級數。假如有個波形比較復雜的周期函數，那麼找出能用來構成這個周期函數的正弦函數和餘弦函數的頻率的方法就叫做傅里葉變換，用這些頻率的正弦函數和餘弦函數疊加起來表示這個周期函數的方法就叫做傅里葉逆變換。
    再從公式中看下他們的關系，首先介紹傅里葉級數到底是什麼，首先級數是指將數列的項依次用加號連接起來的函數。這么說可能大家還不理解，舉個例子：e^x=1 x/1! x^2/2! ...x^n/n!....，等號左邊是指數函數，等號右邊就是級數。傅里葉級數公式如下：

    我們主要看這個指數形式的傅里葉級數公式，把求和符號去掉，展開一下就是f(t)=fa*e^jaω0t fb*e^jbω0t fc*e^jcω0t fd*e^jdω0.....。現在看下面的周期函數疊加效果圖，圖中顯示的是3個周期函數分別在坐標軸（橫軸時間，縱軸幅度）的圖像，寫成傅里葉級數形式就是f(t)=fa(t) fb(t) 0 0....，這就是傅里葉級數公式要描述的現象。其中fa*e^jaω0t=fa(t),fb*e^jbω0t=fb(t),fc*e^jcω0t=0....。

    看下圖的傅里葉變換和逆變換公式，你會發現傅里葉逆變換公式和傅里葉級數公式極其相似，而傅里葉級數系數公式fn又和傅里葉變換公式極其相似。所以對一個周期函數進行傅里葉級數展開的過程可以認為是先做傅里葉變換再做傅里葉逆變換的過程。

    上圖就是傅里葉變換公式也叫連續傅里葉變換公式，有個很重要的事情，就是傅里葉變換公式和逆變換公式一定要一起給出，不然就會讓人誤解，你們在網上會看到各種各樣的寫法，但這些寫法都是對的，常見的如下圖所示。

    為了方便後面的講解我把角頻率ω換成2πf，如上圖所示，ω是希臘字母讀作omega，大寫是ω，小寫是ω，以後這兩個字母會經常看到，都是等於2πf。不要和電學中的電阻單位搞混了，要明白字母只不過是一個符號而已，在不同學科領域都是混著用的，只要不和自己公式中其他字母沖突就行，例如上圖傅里葉變換公式中的j其實就是虛數單位i，一般時候我們會把虛數單位寫成i，但因為傅立葉變換經常用於電學解決一些問題，為了不和電流符號i混淆，所以公式就把i寫成j 。
    要想了解傅里葉變換公式，首先要了解歐拉公式e^ix=cosx isinx在圖像中的含義。以實部的值cosx作為橫坐標值，虛部sinx的值作為縱坐標值，x的取值從負無窮到正無窮，畫出所有的e^ix點後，你會發現這些點會形成一個周期為2π的圓。如下圖1所示（如果不理解，建議看3blue1brown的視頻，視頻連接：https://www.bilibili.com/video/bv1pw411j7s8）

    所以歐拉公式e^ix其實就是隨著x的增大而在坐標繫上逆時針畫圓的過程，那麼e^-ix就表示順時針畫圓，e^-i2πx就表示畫圓的速度提高2π倍，也就是說x從0到1的過程就是順時針畫出一個完整圓的過程（當然x從1到2或者2到3等等，都能畫出一個完整的圓），把x換成t後，e^-i2πt表示每秒都會順時針畫出一個圓。e^-i2πft表示每秒都會順時針畫出f個圓。f(t)表示t時刻的振幅，f(t)函數畫出來就是時域波形圖。f(t)*e^-i2πft表示每經過1秒會順時針畫出f個圓，並在畫圓的同時，t時刻的圓半徑要乘上t時刻的振幅，其實就是以每秒的音頻振幅數據繞f圈的速度進行旋轉纏繞（為了方便理解，沒有用復雜的音頻數據，用的是一個頻率為3的正弦波音頻做的實驗，請看下圖2，圖的上半部分是時域波形圖，圖的左下角是f等於0.4的時候，用公式f(t)*e^-i2πft在實部和虛部構成的坐標系畫的圖，圖的右下角是頻譜圖，頻譜圖的橫坐標是頻率，縱坐標是振幅，振幅的值就是左下角圖中數據形成的圖案的質心（圖中的紅點）到坐標系原點的距離的2倍）。當改變f的值，你會發現數據大多數時候是和我們想的一樣，以坐標系原點為圓心環繞著，也就是振幅一直都是0，但是當f的值，也就每秒的圈數等於該音頻數據的頻率時，你會發現一個神奇的現象，那就是所有的數據會在實部或虛部坐標軸的一側形成一個圓（如下圖3所示，如此一來就知道這段音頻數據包含了一個頻率為3振幅為0.5的正弦波）。所以將多個正弦波疊加的音頻數據用傅里葉公式，f從負無窮到正無窮遍歷一遍，就可以把這個音頻數據里包含的正弦波都一一找出來。（如果不理解，建議看3blue1brown的視頻，視頻連接：https://www.bilibili.com/video/bv1pw411j7s8）

    平時我們說的對音頻進行傅里葉變換處理，其實說的是短時離散傅里葉變換。短時離散傅里葉變換的公式（也可以直接叫做離散傅里葉變換公式）如下。

    下面將教大家如何理解這個公式。上面說的連續傅里葉變換公式中有兩個原因導致我們無法使用，第一點要求是音頻數據的時間從負無窮到正無窮，第二點要求是任意時間t都要有幅度值x(t)才能代入公式進行計算。所以為了解決這兩個問題，把公式變為短時且離散的傅里葉變換公式，這個公式可以把一段時間（時間假設為ts秒）的離散音頻數據（有n個采樣數據）進行傅里葉變換。你可以把離散傅里葉變換公式理解成連續傅里葉變換的變形，最重要的一點是連續傅里葉變換公式的f和離散傅里葉變換公式的k不是一個意思，他們的關系是k=f*ts。所以離散傅里葉變換公式也可以寫成f(f)=1/n*∑f(t)*e^-j2πf*ts*n/n，其中的ts*n/n對應的就是連續傅里葉變換公式的t，只不過這個t沒辦法取任意時間了，t的取值也就隨著n的取值成為了離散的時間點，所以前面的系數由1/2π變為1/n。這樣這兩個公式就對應起來了。下面將進一步詳細介紹這個公式。
    上一段說了k=f*ts，這段我來解釋下為什麼，其實離散傅里葉變換公式中k表示的是這段ts秒的音頻數據環繞坐標系原點的圈數，所以k並不是連續傅里葉變換公式里的頻率f，而頻率f指的是1秒鍾震盪的次數，在這個公式中頻率f也對應著1秒的音頻數據環繞的圈數，所以真正的頻率f=k/ts。
    有人可能會好奇，那為什麼不把離散傅里葉變換公式的自變數k換成f呢，這樣不是更好理解嗎？是會更好理解，但是沒有必要，用f的話還要做一次無用的換算。因為采樣點只有n個的原因，k的取值范圍就被限制住了，k的取值范圍只能是0~n-1的整數，這也是為什麼用k來做自變數而不是用f的原因。
    還有人可能會好奇，傅里葉逆變換到底是怎麼把頻域的信息還原回時域的，其實公式計算出來的f(k)是一個復數，這個復數包含了這個頻率的周期函數的振幅和相位的信息，假設f(k)=a ib，，f(k)的模|f(k)|=(a^2 b^2)^1/2，頻率f=k/ts時的振幅為|f(k)|*2（因為求出來的值相當於圓心，但實際上振幅是圓離圓心最遠點到坐標原點的距離，所以要乘2），頻率f=k/ts時的相位為arctan(b/a)。所以如果你知道一個周期函數包含了哪些頻率的周期函數，並且你這到這些周期函數的振幅和相位，你就可以像下圖一樣把fa(t)和fb(t)疊加在一起還原回f(t)。傅里葉逆變換的做法略有不同，但意思就是這么個意思，理解了離散傅里葉變換公式的計算，逆變換其實也是差不多代入數值計算就是了。（如果不理解怎麼用離散傅里葉變換公式計算，建議看視頻，視頻里有離散傅里葉變換完整的計算過程，視頻連接：https://www.hu.com/zvideo/1276595628009377792）

快速傅里葉變換推薦看下面兩個視頻
https://www.bilibili.com/video/bv1za411f76u
https://www.bilibili.com/video/bv1jh411d7cn
下面是我用java實現的離散傅里葉變換及逆變換和快速傅里葉變換及逆變換，從他們的運行時間就可以看出來快速傅里葉變換快得多。（學完快速傅里葉變換再想想頻譜為何y軸對稱？為何n/2對稱？）

❻ c語言實現音樂信號的快速傅里葉變換，為什麼要有周期中斷來ad採集音樂，這個周期採集的周期怎麼確定

頻率和周期互為倒數。 f = 1/t; t=1/f;
f = 40khz = 40000 hz = 40000 ( 1 秒 多少次 叫 多少 赫茲）；
t = 1/f = 1.0 / 40000.0; 采樣的時間間隔。
傅里葉變換 -- 時域到頻域變換，用於研究時序信號的頻域特性
快速傅里葉變換 -- 數據點數 必須是 2 的整數次方，例如 1024，2048，4096 。。。。不足時要補點，補點有多種方法，最常用是補0 或 假定信號從頭再來。
-------
你想用 40000 hz 采樣頻率，1秒就要有 40000 點。
總的信號長度若是幾分鍾，點數就嚇人地多，fft 耗時也要很長。
你也許可以把信號分段來fft, 或1次就分析4096點，或 設一個 t0 時步推進，分段信號 重疊 幾分之1，得動態頻譜。。。。看你的需要。

❼ 求fft的c語言程序

快速傅里葉變換 要用c 才行吧 你可以用matlab來實現更方便點啊

此fft 是用vc6.0編寫，由fft.cpp；stdafx.h和stdafx.cpp三個文件組成，編譯成功。程序可以用文件輸入和輸出為文件。文件格式為txt文件。測試結果如下：

輸入文件：8.txt 或手動輸入

8 //n

1

2

3

4

5

6

7

8

輸出結果為：或保存為txt文件。（8out.txt）

8

(36,0)

(-4,9.65685)

(-4,4)

(-4,1.65685)

(-4,0)

(-4,-1.65685)

(-4,-4)

(-4,-9.65685)

下面為fft.cpp文件：

// fft.cpp : 定義控制台應用程序的入口點。

#include "stdafx.h"

#include

#include

#include

#include

#include

#include

#include

using namespace std;

bool inputdata(unsigned long &, vector >&); //手工輸入數據

void fft(unsigned long &, vector >&); //fft變換

void display(unsigned long &, vector >&); //顯示結果

bool readdatafromfile(unsigned long &, vector >&); //從文件中讀取數據

bool saveresulttofile(unsigned long &, vector >&); //保存結果至文件中

const double pi = 3.1415926;

int _tmain(int argc, _tchar* argv[])

{

vector > veclist; //有限長序列

unsigned long uln = 0; //n

char chchoose = ' '; //功能選擇

//功能循環

while(chchoose != 'q' && chchoose != 'q')

{

//顯示選擇項

cout << "\nplease chose a function" << endl;

cout << "\t1.input data manually, press 'm':" << endl;

cout << "\t2.read data from file, press 'f':" << endl;

cout << "\t3.quit, press 'q'" << endl;

cout << "please chose:";

//輸入選擇

chchoose = getch();

//判斷

switch(chchoose)

{

case 'm': //手工輸入數據

case 'm':

if(inputdata(uln, veclist))

{

fft(uln, veclist);

display(uln, veclist);

saveresulttofile(uln, veclist);

}

break;

case 'f': //從文檔讀取數據

case 'f':

if(readdatafromfile(uln, veclist))

{

fft(uln, veclist);

display(uln, veclist);

saveresulttofile(uln, veclist);

}

break;

}

}

return 0;

}

bool is2power(unsigned long ul) //判斷是否是2的整數次冪

{

if(ul < 2)

return false;

while( ul > 1 )

{

if( ul % 2 )

return false;

ul /= 2;

}

return true;

}

bool inputdata(unsigned long & uln, vector >& veclist)

{

//題目

cout<< "\n\n\n==============================input data===============================" << endl;

//輸入n

cout<< "\ninput n:";

cin>>uln;

if(!is2power(uln)) //驗證n的有效性

{

cout<< "n is invalid (n must like 2, 4, 8, .....), please retry." << endl;

return false;

}

//輸入各元素

veclist.clear(); //清空原有序列

complex c;

for(unsigned long i = 0; i < uln; i )

{

cout << "input x(" << i << "):";

cin >> c;

veclist.push_back(c);

}

return true;

}

bool readdatafromfile(unsigned long & uln, vector >& veclist) //從文件中讀取數據

{

//題目

cout<< "\n\n\n===============read data from file==============" << endl;

//輸入文件名

string strfilename;

cout << "input filename:" ;

cin >> strfilename;

//打開文件

cout << "open file " << strfilename << "......." <
ifstream loadfile;

loadfile.open(strfilename.c_str());

if(!loadfile)

{

cout << "\tfailed" << endl;

return false;

}

else

{

cout << "\tsucceed" << endl;

}

veclist.clear();

//讀取n

loadfile >> uln;

if(!loadfile)

{

cout << "can't get n" << endl;

return false;

}

else

{

cout << "n = " << uln << endl;

}

//讀取元素

complex c;

for(unsigned long i = 0; i < uln; i )

{

loadfile >> c;

if(!loadfile)

{

cout << "can't get enough infomation" << endl;

return false;

}

else

cout << "x(" << i << ") = " << c << endl;

veclist.push_back(c);

}

//關閉文件

loadfile.close();

return true;

}

bool saveresulttofile(unsigned long & uln, vector >& veclist) //保存結果至文件中

{

//詢問是否需要將結果保存至文件

char chchoose = ' ';

cout << "do you want to save the result to file? (y/n):";

chchoose = _getch();

if(chchoose != 'y' && chchoose != 'y')

{

return true;

}

//輸入文件名

string strfilename;

cout << "\ninput file name:" ;

cin >> strfilename;

cout << "save result to file " << strfilename << "......" << endl;

//打開文件

ofstream savefile(strfilename.c_str());

if(!savefile)

{

cout << "can't open file" << endl;

return false;

}

//寫入n

savefile << uln << endl;

//寫入元素

for(vector >::iterator i = veclist.begin(); i < veclist.end(); i )

{

savefile << *i << endl;

}

//寫入完畢

cout << "save succeed." << endl;

//關閉文件

savefile.close();

return true;

}

void fft(unsigned long & uln, vector >& veclist)

{

//得到冪數

unsigned long ulpower = 0; //冪數

unsigned long uln1 = uln - 1;

while(uln1 > 0)

{

ulpower ;

uln1 /= 2;

}

//反序

bitset bsindex; //二進制容器

unsigned long ulindex; //反轉後的序號

unsigned long ulk;

for(unsigned long p = 0; p < uln; p )

{

ulindex = 0;

ulk = 1;

bsindex = bitset(p);

for(unsigned long j = 0; j < ulpower; j )

{

ulindex = bsindex.test(ulpower - j - 1) ? ulk : 0;

ulk *= 2;

}

if(ulindex > p)

{

complex c = veclist[p];

veclist[p] = veclist[ulindex];

veclist[ulindex] = c;

}

}

//計算旋轉因子

vector > vecw;

for(unsigned long i = 0; i < uln / 2; i )

{

vecw.push_back(complex(cos(2 * i * pi / uln) , -1 * sin(2 * i * pi / uln)));

}

for(unsigned long m = 0; m < uln / 2; m )

{

cout<< "\nvw[" << m << "]=" << vecw[m];

}

//計算fft

unsigned long ulgrouplength = 1; //段的長度

unsigned long ulhalflength = 0; //段長度的一半

unsigned long ulgroupcount = 0; //段的數量

complex cw; //wh(x)

complex c1; //g(x) wh(x)

complex c2; //g(x) - wh(x)

for(unsigned long b = 0; b < ulpower; b )

{

ulhalflength = ulgrouplength;

ulgrouplength *= 2;

for(unsigned long j = 0; j < uln; j = ulgrouplength)

{

for(unsigned long k = 0; k < ulhalflength; k )

{

cw = vecw[k * uln / ulgrouplength] * veclist[j k ulhalflength];

c1 = veclist[j k] cw;

c2 = veclist[j k] - cw;

veclist[j k] = c1;

veclist[j k ulhalflength] = c2;

}

}

}

}

void display(unsigned long & uln, vector >& veclist)

{

cout << "\n\n===========================display the result=========================" << endl;

for(unsigned long d = 0; d < uln;d )

{

cout << "x(" << d << ")\t\t\t = " << veclist[d] << endl;

}

}

下面為stdafx.h文件：

// stdafx.h : 標准系統包含文件的包含文件，

// 或是常用但不常更改的項目特定的包含文件

#pragma once

#include

#include

// todo: 在此處引用程序要求的附加頭文件

下面為stdafx.cpp文件：

// stdafx.cpp : 只包括標准包含文件的源文件

// fft.pch 將成為預編譯頭

// stdafx.obj 將包含預編譯類型信息

#include "stdafx.h"

// todo: 在 stdafx.h 中

//引用任何所需的附加頭文件，而不是在此文件中引用