算法导论fft

① 请大侠给我推荐几个算法的书.因为我没读过,所以请在回答的时候告诉我推荐的理由,最好有内容.

《算法导论》

本书深入浅出，全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣，并保持了数学严谨性。本书的设计目标全面，适用于多种用途。涵盖的内容有：算法在计算中的作用，概率分析和随机算法的介绍。本书专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。本书还介绍了对强连通子图算法正确性的证明，对哈密顿回路和子集求和问题的NP完全性的证明等内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。

目录（Table of Contents）

前言（Preface）

第一部分（Part I） 基础（Foundations）

第一章 计算中算法的角色（The Role of Algorithms in Computing）

第二章 开始（Getting Started）

第三章 函数的增长率（Growth of Functions）

第四章 递归（Recurrences）

第五章 概率分析与随机化算法（Probabilistic Analysis and Randomized Algorithms）

第二部分（Part II） 排序与顺序统计（Sorting and Order Statistics）

第六章 堆排序（Heapsort）

第七章快速排序（Quicksort）

第八章 线性时间中的排序（Sorting in Linear Time）

第九章 中值与顺序统计（Medians and Order Statistics）

第三部分（Part III） 数据结构（Data Structures）

第十章 基本的数据结构（Elementary Data Structures）

第十一章 散列表（Hash Tables）

第十二章 二叉查找树（Binary Search Trees）

第十三章 红-黑树（Red-Black Trees）

第十四章 扩充的数据结构（Augmenting Data Structures）

第四部分（Part IV） 高级的设计与分析技术（Advanced Design and Analysis Techniques）

第十五章 动态规划（Dynamic Programming）

第十六章 贪婪算法（Greedy Algorithms）

第十七章 分摊分析（Amortized Analysis）

第五部分（Part V） 高级的数据结构（Advanced Data Structures）

第十八章 B-树（B-Trees）

第十九章 二项式堆（Binomial Heaps）

第二十章 斐波纳契堆（Fibonacci Heaps）

第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets）

第六部分（Part VI） 图算法（Graph Algorithms）

第二十二章 基本的图算法（Elementary Graph Algorithms）

第二十三章 最小生成树（Minimum Spanning Trees）

第二十四章单源最短路径（Single-Source Shortest Paths）

第二十五章 全对的最短路径（All-Pairs Shortest Paths）

第二十六章 最大流（Maximum Flow）

第七部分（Part VII） 精选的主题（Selected Topics）

第二十七章 排序网络（Sorting Networks）

第二十八章矩阵运算（Matrix Operations）

第二十九章 线性规划（Linear Programming）

第三十章 多项式与快速傅里叶变换（Polynomials and the FFT）

第三十一章 数论算法（Number-Theoretic Algorithms）

第三十二章 字符串匹配（String Matching）

第三十三章 计算几何学（Computational Geometry）

第三十四章 NP-完备性（NP-Completeness）

第三十五章 近似算法（Approximation Algorithms）

第八部分（Part VIII） 附录：数学背景（Mathematical Background）

附录A 求和（Summations）

附录B 集合，等等。（Sets, Etc.）

附录C 计数与概率（Counting and Probability）

参考文献（Bibliography）

索引（Index）

② fft源程序

这个是我上个星期才交的课程设计里面的源代码，绝对可以运行的。本人也觉得应该比较容易看懂吧。

#include<iostream>
#include<math.h>
using namespace std;
#define PI 3.1415927
#define MAX 20000

////////////////////////////////
//以指数形式表示的复数
/////////////////////////////////
struct CompExp
{
float AbValue;
float Angle;
};

//////////////////////////////////////
//以一般形式表示的复数
///////////////////////////////////////
struct Complex
{
float Re;
float Im;
}A[MAX];

int n;
float a[MAX] ;

//////////////////////////////////////////
//将一个数的二进制数反转之后的新数返回
//例如6->110->011->3
//////////////////////////////////////////
int Rev(int i)
{
int index,s; //index为要返回的数
s=(int)log2(n);
index=0;
while(s>0)
{
s--;
index+=(i%2)*(int)pow(2,s);
i=i/2;
}
return index;
}

////////////////////////////////////////////
//将输入的离散数据进行位反置转换，并复制在复数数组A中
////////////////////////////////////////////
void bit(float* a, Complex* A)
{
for(int i=0;i<n;i++)
{
A[Rev(i)].Re=a[i];
A[Rev(i)].Im=0;
}
}

/////////////////////////////////////////////
//复数的加法a+b=c
/////////////////////////////////////////////
void Add(Complex* a, Complex* b, Complex* c)
{
c->Re = a->Re + b->Re;
c->Im = a->Im + b->Im;
}

/////////////////////////////////////////////
//复数的减法a-b=c
/////////////////////////////////////////////
void Sub(Complex* a, Complex* b, Complex* c)
{
c->Re = a->Re - b->Re;
c->Im = a->Im - b->Im;
}

////////////////////////////////////////////
//复数的乘法a*b=c
////////////////////////////////////////////
void Mul(Complex* a, Complex* b, Complex* c)
{
float tempRe,tempIm;
tempRe = a->Re * b->Re - a->Im * b->Im;
tempIm = a->Re * b->Im + a->Im * b->Re;
c->Re = tempRe;
c->Im = tempIm;
}

/////////////////////////////////////////
//将复数从指数形式转化为一般形式
/////////////////////////////////////////
void CompTrans(CompExp* a, Complex* b)
{
b->Re = a->AbValue * cos(a->Angle);
b->Im = a->AbValue * sin(a->Angle);
}

///////////////////////////////////////
//基于迭代的快速傅里叶算法
///////////////////////////////////////
void FFT()
{
Complex Wm,W,u,t;
CompExp wm,w;
bit(a,A);
for(int i=1;i<=(int)log2(n);i++)
{
int m=(int)pow(2,i);
wm.AbValue = 1;
wm.Angle = -2*PI/m;
CompTrans(&wm,&Wm);
for(int k=0;k<n;k+=m)
{
w.AbValue = 1;
w.Angle = 0;
CompTrans(&w,&W);
for(int j=0;j<m/2;j++)
{
Mul(&W,&A[k+j+m/2],&t);
u=A[k+j]; //蝴蝶操作
Add(&u,&t,&A[k+j]);
Sub(&u,&t,&A[k+j+m/2]);
Mul(&W,&Wm,&W);
}
}
}
}

///////////////////////////////////
//测试输入的离散点个数n是否是二的幂
///////////////////////////////////
int test(int i)
{
while(1)
{
if(i==2)break;
if(i/2*2!=i)return 0;
i=i/2;
}
return 1;
}

//////////////////////////////////
//管理输入的函数
//////////////////////////////////
void Input()
{
cout<<"请输入离散数据的个数，合法的输入为2的正整数幂："<<endl;
cin>>n;
while(!test(n))
{
cout<<"序列长度不合法，请重新输入："<<endl;
cin>>n;
}
for(int i=0;i<n;i++)
{
cout<<"x["<<i<<"]= ";
cin>>a[i];
}
}

//////////////////////////////////
//管理输出的函数
//////////////////////////////////
void Output()
{
for(int i=0;i<n;i++)
cout<<"X["<<i<<"]= ("<<A[i].Re<<") + j("<<A[i].Im<<")"<<endl;
cout<<endl;
}

///////////////////////////////////
//程序入口
///////////////////////////////////
int main()
{
while(1)
{
Input();
FFT();
Output();
}
}

③ 计算机科学与技术相关书籍

就计算机科学与技术而言，我知道的《算法导论》这本书挺合适的，这里面涵盖了计算机的几乎所有的算法，对于学习计算机编程的人而言十分重要。学懂了这本书，就可以应付很多的考试和比赛。
附:
目录（Table of Contents）
前言（Preface）
第一部分（Part I） 基础（Foundations）
第一章 计算中算法的角色（The Role of Algorithms in Computing）
第二章 开始（Getting Started）
第三章 函数的增长率（Growth of Functions）
第四章 递归（Recurrences）
第五章 概率分析与随机化算法（Probabilistic Analysis and Randomized Algorithms）
第二部分（Part II） 排序与顺序统计（Sorting and Order Statistics）
第六章 堆排序（Heapsort）
第七章 快速排序（Quicksort）
第八章 线性时间中的排序（Sorting in Linear Time）
第九章 中值与顺序统计（Medians and Order Statistics）
第三部分（Part III） 数据结构（Data Structures）
第十章 基本的数据结构（Elementary Data Structures）
第十一章 散列表（Hash Tables）
第十二章 二叉查找树（Binary Search Trees）
第十三章 红-黑树（Red-Black Trees）
第十四章 扩充的数据结构（Augmenting Data Structures）
第四部分（Part IV） 高级的设计与分析技术（Advanced Design and Analysis Techniques）
第十五章 动态规划（Dynamic Programming）
第十六章 贪婪算法（Greedy Algorithms）
第十七章 分摊分析（Amortized Analysis）
第五部分（Part V） 高级的数据结构（Advanced Data Structures）
第十八章 B-树（B-Trees）
第十九章 二项式堆（Binomial Heaps）
第二十章 斐波纳契堆（Fibonacci Heaps）
第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets）
第六部分（Part VI） 图算法（Graph Algorithms）
第二十二章 基本的图算法（Elementary Graph Algorithms）
第二十三章 最小生成树（Minimum Spanning Trees）
第二十四章 单源最短路径（Single-Source Shortest Paths）
第二十五章 全对的最短路径（All-Pairs Shortest Paths）
第二十六章 最大流（Maximum Flow）
第七部分（Part VII） 精选的主题（Selected Topics）
第二十七章 排序网络（Sorting Networks）
第二十八章 矩阵运算（Matrix Operations）
第二十九章 线性规划（Linear Programming）
第三十章 多项式与快速傅里叶变换（Polynomials and the FFT）
第三十一章 数论算法（Number-Theoretic Algorithms）
第三十二章 字符串匹配（String Matching）
第三十三章 计算几何学（Computational Geometry）
第三十四章 NP-完备性（NP-Completeness）
第三十五章 近似算法（Approximation Algorithms）
第八部分（Part VIII） 附录：数学背景（Mathematical Background）
附录A 求和（Summations）
附录B 集合，等等。（Sets, Etc.）
附录C 计数与概率（Counting and Probability）
参考文献（Bibliography）
索引（Index）

④ 算法导论的作品目录

目录（Table of Contents）
前言（Preface）
第一部分（Part I） 基础（Foundations）
第一章 计算中算法的角色（The Role of Algorithms in Computing）
第二章 开始（Getting Started）
第三章 函数的增长率（Growth of Functions）
第四章 递归（Recurrences）
第五章 概率分析与随机化算法（Probabilistic Analysis and Randomized Algorithms）
第二部分（Part II） 排序与顺序统计（Sorting and Order Statistics）
第六章 堆排序（Heapsort）
第七章快速排序（Quicksort）
第八章 线性时间中的排序（Sorting in Linear Time）
第九章 中值与顺序统计（Medians and Order Statistics）
第三部分（Part III） 数据结构（Data Structures）
第十章 基本的数据结构（Elementary Data Structures）
第十一章 散列表（Hash Tables）
第十二章 二叉查找树（Binary Search Trees）
第十三章 红-黑树（Red-Black Trees）
第十四章 扩充的数据结构（Augmenting Data Structures）
第四部分（Part IV） 高级的设计与分析技术（Advanced Design and Analysis Techniques）
第十五章 动态规划（Dynamic Programming）
第十六章 贪婪算法（Greedy Algorithms）
第十七章 分摊分析（Amortized Analysis）
第五部分（Part V） 高级的数据结构（Advanced Data Structures）
第十八章 B-树（B-Trees）
第十九章 二项式堆（Binomial Heaps）
第二十章 斐波纳契堆（Fibonacci Heaps）
第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets）
第六部分（Part VI） 图算法（Graph Algorithms）
第二十二章 基本的图算法（Elementary Graph Algorithms）
第二十三章 最小生成树（Minimum Spanning Trees）
第二十四章单源最短路径（Single-Source Shortest Paths）
第二十五章 全对的最短路径（All-Pairs Shortest Paths）
第二十六章 最大流（Maximum Flow）
第七部分（Part VII） 精选的主题（Selected Topics）
第二十七章 排序网络（Sorting Networks）
第二十八章矩阵运算（Matrix Operations）
第二十九章 线性规划（Linear Programming）
第三十章 多项式与快速傅里叶变换（Polynomials and the FFT）
第三十一章 数论算法（Number-Theoretic Algorithms）
第三十二章 字符串匹配（String Matching）
第三十三章 计算几何学（Computational Geometry）
第三十四章 NP-完备性（NP-Completeness）
第三十五章 近似算法（Approximation Algorithms）
第八部分（Part VIII） 附录：数学背景（Mathematical Background）
附录A 求和（Summations）
附录B 集合，等等。（Sets, Etc.）
附录C 计数与概率（Counting and Probability）
参考文献（Bibliography）
索引（Index）

⑤ 为什么《算法导论》中的数组序号是从1开始的

c语言下标从零开始是个错误，并且 index 也是一个有误导性的名词，它表示的是偏移量，明明应该用 offset。
然后 c 的徒子徒孙都学了它，导致现在很多人都误以为下标应该从 0 开始。
早期蛮荒时代，很多东西都不科学，算法导论作者致力于与落后文明作斗争，然而却遭到了楼主你的不理解，实乃编程届一大憾事。
我再说一遍，C 是结构化的汇编，下标基 0 是受到了 PDP-11 指令集的影响，更老的语言（比如 Fortran）都是基 1 的。
另外用 0/非 0 代表 false/true 也是 PDP-11 中 TST 指令和 Z 位的行为。
可能是这本书强调算法的求学思想，所以从一更加符合数学的数组规定。
但是编程的时候，指针这个东西会经常用到，如果用a(o)作为第一个元素 那么*a+n就等同于a(n) 比较方便
算法导论上的这个问题呢，我觉得我比较同意楼上的看法，这个书上面的很多的程序并不是可以敲上去直接运行的，他只是伪代码，思想而已，给人看的，人类的普遍思维是从1开始，那么书页就是从1开始了
说编程语言是给机器看而伪代码是给人看的简直是逗大家笑吧...编程语言设计出来就是给人看的....
另外从0开始在很多方便都极好....我觉得写多代码都能体会到吧..
帮算导洗地：
算法导论通篇用的是伪代码 是给人类阅读理解的 不是设计给机器去运行的
而绝大多数情况下， index 从 1 开始更符合人类直觉（如果你对这点有异议请参考的答案 ）
但少数情况下， index 从 0 开始更符合人类直觉。例如书中 hashing 还有 FFT 那块内容， index 是从 0 开始的。
其实写几天 Pascal 你就适应啦。。

⑥ 计算机专业学算法的都学些什么算法，有什么书可以看的学的话需要些什么基础的

计算机算法非常多的
A*搜寻算法
俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。
Beam Search
束搜索(beam search)方法是解决优化问题的一种启发式方法，它是在分枝定界方法基础上发展起来的，它使用启发式方法估计k个最好的路径，仅从这k个路径出发向下搜索，即每一层只有满意的结点会被保留，其它的结点则被永久抛弃，从而比分枝定界法能大大节省运行时间。束搜索于20 世纪70年代中期首先被应用于人工智能领域,1976 年Lowerre在其称为HARPY的语音识别系统中第一次使用了束搜索方法。他的目标是并行地搜索几个潜在的最优决策路径以减少回溯，并快速地获得一个解。
二分取中查找算法
一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。
Branch and bound
分支定界(branch and bound)算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。
数据压缩
数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度，达到增大数据密度，最终使数据的存储空间减少的技术。数据压缩在文件存储和分布式系统领域有着十分广泛的应用。数据压缩也代表着尺寸媒介容量的增大和网络带宽的扩展。
Diffie–Hellman密钥协商
Diffie–Hellman key exchange，简称“D–H”，是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。
Dijkstra’s 算法
迪科斯彻算法（Dijkstra）是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger Wybe Dijkstra）发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示着城市间开车行经的距离，迪科斯彻算法可以用来找到两个城市之间的最短路径。
动态规划
动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。比较着名的应用实例有：求解最短路径问题，背包问题，项目管理，网络流优化等。这里也有一篇文章说得比较详细。
欧几里得算法
在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。
最大期望（EM）算法
在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。
快速傅里叶变换(FFT)
快速傅里叶变换（Fast Fourier Transform，FFT），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如数字信号处理、计算大整数乘法、求解偏微分方程等等。
哈希函数
HashFunction是一种从任何一种数据中创建小的数字“指纹”的方法。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。
堆排序
Heapsort是指利用堆积树（堆）这种数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构，并同时满足堆积属性：即子结点的键值或索引总是小于（或者大于）它的父结点。
归并排序
Merge sort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
RANSAC 算法
RANSAC 是”RANdom SAmpleConsensus”的缩写。该算法是用于从一组观测数据中估计数学模型参数的迭代方法，由Fischler and Bolles在1981提出，它是一种非确定性算法，因为它只能以一定的概率得到合理的结果，随着迭代次数的增加，这种概率是增加的。该算法的基本假设是观测数据集中存在”inliers”（那些对模型参数估计起到支持作用的点）和”outliers”（不符合模型的点），并且这组观测数据受到噪声影响。RANSAC 假设给定一组”inliers”数据就能够得到最优的符合这组点的模型。
RSA加密算法
这是一个公钥加密算法，也是世界上第一个适合用来做签名的算法。今天的RSA已经专利失效，其被广泛地用于电子商务加密，大家都相信，只要密钥足够长，这个算法就会是安全的。
并查集Union-find
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
Viterbi algorithm
寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states)。

⑦ C和C++算法

离散数学比较多，工程数学中涉及到的矩阵啊，多元数等。。

看了你的补充，也来补充一下吧，这下要从1楼掉到几十楼了，说说我的体验，每个人的情况都有所不同，不必完全看我的哈。
我个人是搞游戏开发的，在游戏中我们不断的用到一个概念就是矩阵，这个属于线性代数的内容，向量，这个是高宗数学的内容。
数值分析：说实话吧，对锻炼编程能力有帮助，在实际应用中感觉并不多，至少我并没有遇到很多次。
高等代数：说石化，这个用得更少了，真的，个人觉得高等数学并不是让你学数学了，学的是一种数学理念，是对数学的抽象能力，这对于计算机的学生来说，是很重要的。

高等几何，没怎么听说过，或许有用吧。

我是计算机专业的大学生，算法分析我也学过了，其实感觉就是用到的数学知识真的不是非常多，也不需要非常高深的数学知识，或者是我的接触面不够吧。。。但是数学好对计算机编程水平是很有帮助的

特别注意一点，离散数学是相当有用的，感觉是整个计算机数学的基础。。。

累了一天了，好累，希望对你有帮助！

⑧ 如何用C语言实现FFT算法（比如窗函数算法),求高手指点一二

参见 数字信号处理第三版 程佩清 着，算法导论里也有讲FFT的
英飞凌单片机又不是DSP 应该没有内嵌的算法，所以应该可以直接套用通用的C语言程序

⑨ 除了《算法导论》 还有什么地方可以看到不错的FFT的讲解

数字信号处理。

⑩ 高中生能看懂算法导论吗

算法导论不是一本noi参赛选手应该看的书。理论性太强，学得慢、而且算法不够深刻。如果你只学习了语言，那么ls推荐的《算法艺术》也不适用，你想参加的应该是noip，noi是在noip上一个层次的全国比赛，到了noi水平应该看的是算法艺术而不是算法导论，《算法艺术》在当当网上有买

不过现在关于noip的书几乎都是用pascal语言写的，我当时学的时候也是用pascal，现在转了c＋＋。所以我推荐的书都是pascal写的。。。《奥赛经典》和《全国青少年信息学奥林匹克教程》，如果你不习惯，可以选择买大学的acm教程来看（acm是大学生的全球性信息学竞赛，大学生几乎都用c、c＋＋或者java，书多用c和c＋＋写），配套做poj（1l推荐的那个网站～）

另外你可以关注一下noi、noip竞赛官网 http://www.noi.cn
还有oier经常去的网站 www.oibh.org/bbs 可以上去问题、找资料

ps，数学知识也很重要，其他文化科可以放，数学已经要跟上～

祝成功～