本课件是noi2019第二课堂培训资料，题目为快速傅里叶变换 noi2019课件 宋新波，欢迎大家下载和交流。
2019-12-21 19:48:12
644KB
1
注意：实验报告不全，参考价值：函数实现。
1.1 用C++实现复数类，并为其定义必要的运算符。
struct Complex{
double real_;
double image_;
Complex (void);
Complex (double const& real);
Complex (double const& real, double const& imag);
Complex (Complex const& v);
Complex operator+ (Complex const& a) const;
Complex operator- (Complex const& a) const;
Complex operator* (Complex const& a) const;
Complex operator/ (int n) const;
……
};
1.2 void fft (Comples* dst, Complex* src, int p);快速傅里叶变换。
求复数数组src[0, 2p)的傅里叶变换，结果存放在dst[0, 2p)中。
1.3 void ifft(Complex* dst, Complex* src, int p); 快速傅里叶逆变换。
求复数数组src[0, 2p)的逆傅里叶变换，结果存放在dst[0, 2p)中。
1.4 利用快速傅里叶变换计算长整数乘法。
typedef std::vector Integer;
void multiply( Integer* rst, Integer const& a, Integer const& b);
假设向量 a[0, n) 表示一个长整数：
其中 2≤β≤256 为基底，函数将两个长整数 a, b 相乘，结果放在*rst 向量中。
利用上面的长整数乘法程序计算结果
(123456789ABCDEF)16 256^500×(FEDCBA987654321)16 256^500
(987654321)10 10^800×(123456789)10 10^800
2019-12-21 19:46:20
22KB
1
快速傅里叶变换 (fast Fourier transform), 即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。
这篇PPT非常详细的讲述了快速傅里叶变换的步骤和原理，非常值得一读。
2019-12-21 19:39:39
1.84MB
1
快速傅里叶变换的C++源代码。用matlab自带的fft进行了测试，结果数据非常吻合。最后用FFT处理了一幅位图。
2019-12-21 19:26:17
100KB
1