FFT 템 플 릿 (교체 / 재 귀적)
5298 단어 FFT
#include
#include
#include
#include
#include
using namespace std;
#define pi acos(-1.0)
const int maxn=300010;
typedef complex<double>C;
C a[maxn],b[maxn];
void fft(C *x,int n,int type){
if(n==1) return;
C l[n>>1],r[n>>1];
for(int i=0;i2) l[i>>1]=x[i],r[i>>1]=x[i+1];
fft(l,n>>1,type);fft(r,n>>1,type);
C wn(cos(2*pi/n),sin(type*2*pi/n)),w(1,0);
for(int i=0;i>1);i++,w*=wn)
x[i]=l[i]+w*r[i],x[i+(n>>1)]=l[i]-w*r[i];
}
int rev[maxn];
int n,m;
void init(){
for(int i=0;i>1]>>1)|((i&1)?(n>>1):0);
}
void FFT(C *x,int n,int type){
for(int i=1;iif(ifor(int k=2;k<=n;k<<=1){
C wn(cos(2*pi/k),sin(type*2*pi/k));
for(int i=0;i1,0);
for(int j=0;j>1);j++){
C l=x[i+j],r=x[i+j+(k>>1)];
x[i+j]=l+w*r;
x[i+j+(k>>1)]=l-w*r;
w*=wn;
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) scanf("%lf",&a[i].real());
for(int i=0;i<=m;i++) scanf("%lf",&b[i].real());
m+=n;
for(n=1;n<=m;n<<=1);
init();
FFT(a,n,1);FFT(b,n,1);
for(int i=0;i<=n;i++) a[i]*=b[i];
FFT(a,n,-1);
for(int i=0;i<=m;i++) printf("%d ",(int)(a[i].real()/n+0.5));
return 0;
}
^_^
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Matlab 이미지 처리 "주파수 필터"(2D FFT)첫 투고입니다. 대전 잘 부탁드립니다. 이미지 처리에는 다양한 방법이 있지만, 이 기사에서 소개하는 것은 주파수 필터 처리입니다. 원래 모르겠어! 라고 사람은 이쪽의 기사가 참고가 될까 생각합니다. matlab에서 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.