ACM常用算法(8)

ACM常考算法

void m_of_n(int m,int n1,int m1,int* a,int head) {

int i,t;

if(m1<0 || m1>n1)return; if(m1==n1) {

for(i=0;i<m;i++) cout<<a[i]<<' '; // 输出序列 cout<<'\n'; return; }

m_of_n(m,n1-1,m1,a,head); // 递归调用

t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t; m_of_n(m,n1-1,m1-1,a,head+1); // 再次递归调用 t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t; }

9.快速傅立叶变换（FFT）

语法：kkfft(double pr[],double pi[],int n,int k,double fr[],double fi[],int l,int il); 参数：

pr[n]： 输入的实部 pi[n]： 数入的虚部 n，k： 满足n=2^k fr[n]： 输出的实部 fi[n]： 输出的虚部

l： 逻辑开关，0 FFT，1 ifFT

il： 逻辑开关，0 输出按实部/虚部；1 输出按模/幅角 返回

null 值： 注意： 源程序：

需要 math.h

void kkfft(pr,pi,n,k,fr,fi,l,il)int n,k,l,il;double pr[],pi[],fr[],fi[]; {

int it,m,is,i,j,nv,l0;

double p,q,s,vr,vi,poddr,poddi; for (it=0; it<=n-1; it++) {

m=it; is=0;

for (i=0; i<=k-1; i++)

{j=m/2; is=2*is+(m-2*j); m=j;} fr[it]=pr[is]; fi[it]=pi[is]; }

pr[0]=1.0; pi[0]=0.0; p=6.283185306/(1.0*n);

pr[1]=cos(p); pi[1]=-sin(p);