几种常用的算法简介

[钓鱼技巧介绍几种常用的拴钩方法]1、朝天钩。朝天钩钓采用朝天钩和七星漂，是野钓的一种有效钓法。这种拴钩方法最要注意的就是，钩绑起来下到水里后要达到钩尖朝天的效果。如果钓钩买回来有好丑之分，最好用小锉...+阅读

几种常用的算法简介

1、穷举法穷举法是最基本的算法设计策略，其思想是列举出问题所有的可能解，逐一进行判别，找出满足条件的解。穷举法的运用关键在于解决两个问题：在运用穷举法时，容易出现的问题是可能解过多，导致算法效率很低，这就需要对列举可能解的方法进行优化。以题1041--纯素数问题为例，从1000到9999都可以看作是可能解，可以通过对所有这些可能解逐一进行判别，找出其中的纯素数，但只要稍作分析，就会发现其实可以大幅度地降低可能解的范围。

根据题意易知，个位只可能是

3、

5、7，再根据题意可知，可以在

3、

5、7的基础上，先找出所有的二位纯素数，再在二位纯素数基础上找出三位纯素数，最后在三位纯素数的基础上找出所有的四位纯素数。

2、分治法分治法也是应用非常广泛的一种算法设计策略，其思想是将问题分解为若干子问题，从而可以递归地求解各子问题，再综合出问题的解。

分治法的运用关键在于解决三个问题：我们熟知的如汉诺塔问题、折半查找算法、快速排序算法等都是分治法运用的典型案例。以题1045--Square Coins为例，先对题意进行分析，可设一个函数f(m, n)等于用面值不超过n2的货币构成总值为m的方案数，则容易推导出： f(m, n) = f(m-0*n*n, n-1)+f(m-1*n*n, n-1)+f(m-2*n*n, n-1)+...+f(m-k*n*n, n-1) 这里的k是币值为n2的货币最多可以用多少枚，即k=m/(n*n)。

也很容易分析出，f(m, 1) = f(1, n) = 1 对于这样的题目，一旦分析出了递推公式，程序就非常好写了。所以在动手开始写程序之前，分析工作做得越彻底，逻辑描述越准确、简洁，写起程序来就会越容易。

3、动态规划法动态规划法多用来计算最优问题，动态规划法与分治法的基本思想是一致的，但处理的手法不同。动态规划法在运用时，要先对问题的分治规律进行分析，找出终结子问题，以及子问题向父问题归纳的规则，而算法则直接从终结子问题开始求解，逐层向上归纳，直到归纳出原问题的解。

动态规划法多用于在分治过程中，子问题可能重复出现的情况，在这种情况下，如果按照常规的分治法，自上向下分治求解，则重复出现的子问题就会被重复地求解，从而增大了冗余计算量，降低了求解效率。而采用动态规划法，自底向上求解，每个子问题只计算一次，就可以避免这种重复的求解了。动态规划法还有另外一种实现形式，即备忘录法。

备忘录的基本思想是设立一个称为备忘录的容器，记录已经求得解的子问题及其解。仍然采用与分治法相同的自上向下分治求解的策略，只是对每一个分解出的子问题，先在备忘录中查找该子问题，如果备忘录中已经存在该子问题，则不须再求解，可以从备忘录中直接得到解，否则，对子问题递归求解，且每求得一个子问题的解，都将子问题及解存入备忘录中。

例如，在题1045--Square Coins中，可以采用分治法求解，也可以采用动态规划法求解，即从f(m, 1)和f(1, n)出发，逐层向上计算，直到求得f(m, n)。在竞赛中，动态规划和备忘录的思想还可以有另一种用法。有些题目中的可能问题数是有限的，而在一次运行中可能需要计算多个测试用例，可以采用备忘录的方法，预先将所有的问题的解记录下来，然后输入一个测试用例，就查备忘录，直接找到答案输出。

这在各问题之间存在父子关系的情况下，会更有效。例如，在题1045--Square Coins中，题目中已经指出了最大的目标币值不超过300，也就是说问题数只有300个，而且各问题的计算中存在重叠的子问题，可以采用动态规划法，将所有问题的解先全部计算出来，再依次输入测试用例数据，并直接输出答案。

4、回溯法回溯法是基于问题状态树搜索的求解法，其可适用范围很广。

从某种角度上说，可以把回溯法看作是优化了的穷举法。回溯法的基本思想是逐步构造问题的可能解，一边构造，一边用约束条件进行判别，一旦发现已经不可能构造出满足条件的解了，则退回上一步构造过程，重新进行构造。这个退回的过程，就称之为回溯。回溯法在运用时，要解决的关键问题在于：回溯法的经典案例也很多，例如全排列问题、N后问题等。

5、贪心法贪心法也是求解最优问题的常用算法策略，利用贪心法策略所设计的算法，通常效率较高，算法简单。贪心法的基本思想是对问题做出目前看来最好的选择，即贪心选择，并使问题转化为规模更小的子问题。如此迭代，直到子问题可以直接求解。基于贪心法的经典算法例如：哈夫曼算法、最小生成树算法、最短路径算法等。

推介一本对培养写算法能力有帮助的书要切合基础的

新华书店文轩网搜索的，供参考：C 语言算法速查手册作者：程晓旭等编著出版：人民邮电出版社出版日期：2009年10月本书用C语言编写了科研和工程中最常用的166个算法，这些算法包括复数运算、多项式的计算、矩阵运算、线性代数方程组的求解、非线性方程与方程组的求解、代数插值法、数值积分法、常微分方程（组）初值问题的求解、拟合与逼近、特殊函数、极值问题、随机数产生与统计描述、查找、排序、数学变换与滤波等。同时结合这些算法列举了将近100个应用实例，对其进行验证和分析。本书适用于C语言算法的初学者，也可以作为高等院校师生的学习参考用书。妙趣横生的算法（C语言实现）（配光盘）作者：杨峰编著出版：清华大学出版社出版日期：2010年04月本书理论与实践相结合，旨在帮助读者理解算法，并提高C语言编程能力，培养读者的编程兴趣，并巩固已有的C语言知识。

全书分为2个部分共10章，内容涵盖了编程必备的基础知识（如数据结构、常用算法等），编程实例说明，常见算法和数据结构面试题等。本书最大的特色在于实例丰富，题材新颖有趣，实用性强，理论寓于实践之中。通过本书的学习，可以使读者开阔眼界，提高编程的兴趣，提高读者的编程能力和应试能力。本书附带1张光盘，内容为本书源代码和作者为本书录制的5.5小时多媒体教学视频。本书可作为算法入门人员的算法设计与分析：C++语言描述作者：出版：电子工业出版社2 出版日期：2006年06月本书内容分为3部分：算法和算法分析，算法设计策略及求解困难问题。第1部分说明问题求解方法、算法复杂度和分析、递归算法和递推关系；第2部分讨论常用的算法设计策略：基本搜索和遍历方法、分治法、贪心法、动态规划法、回溯法和分枝限界法；第3部分说明NP完全问题、随机算法、近似算法和密码算法。

书中还说明了两种新的数据结构：跳表和伸展树，以及它们特定的算法分析方法，并对现代密码学做了简要论述。本书结构清晰、内容翔实、逻辑严谨、深入浅出。书中算法有完整的C++程序，程序构思精巧，且有详细注释，所有程序都已算法：C语言（第1~4 部分）作者：（美）塞奇威克著出版：机械工业出版社出版日期：2009年10月本书细腻讲解计算机算法的C语言实现。全书分为四部分，共16章。包括基本算法分析原理，基本数据结构、抽象数据结构、递归和树等数据结构知识，选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序方法，并比较了各种排序方法的性能特征，在进一步讲解符号表、树等抽象数据类型的基础上，重点讨论散列方法、基数搜索以及外部搜索方法。

书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习，还包含大量简洁的实现将理论和实践成功地相结合数据结构与算法C#语言描述作者：（美）麦克米伦（McMillan,M）著；吕秀锋，崔睿译出版：人民邮电出版日期：2009年05月本书是在.NET框架下用C#语言实现数据结构和算法的第一本全面的参考书。本书说明的方法非常实用，采用了时间测试而非大O表示法来分析算法性能。内容涵盖了数据结构和算法的基本原理，涉及数组、广义表、链表、散列表、树、图、排序搜索算法以及更多概率算法和动态规则等高级算法。此外，书中还提供了.NET框架类库中的C#语言实现的数据结构和算法。本书适合作为C#数据结构课程的教材，同时也适合C#专业人士阅读。

算法策略设计要解决的问题是啥

理论上，许多问题可以用穷举搜索的办法来求解。这种解题策略会直截了当地试遍所有的可能解，直接找到问题的解为止。采用穷举搜索时，很少需要独具匠心的设计，因此，如果一个问题确定要用这种策略来求解的话，就很少需要人工计算，而基本上是为计算机准备的。穷举搜索的最大局限性在于它的效率低下，通常，如果可能解的数量随着问题规模而呈指数增长或更快的话，那么这条途径不仅对人类来说遥不可及，计算机也只能望而兴叹了。

策略模式（Strategy Pattern），定义了一系列的算法，将每一种算法封装起来并可以相互替换使用，策略模式让算法独立于使用它的客户应用而独立变化。

策略模式是处理算法的不同变体的一种行为模式，通过在抽象策略中定义算法接口或封装算法标识，实现该抽象策略的具体子类成为一个单独的算法，即具体策略。策略模式使用多个类来区别不同的行为，使用策略模式避免暴露复杂的、与算法相关的内部数据结构。当一个类中的操作以多个条件分支语句的形式出现的时候，可以使用策略模式将相关的条件分支移入各自的具体策略类中以代替这些条件语句，从而减少系统处理的复杂度。

采用哪些算法或设计方案来提高fib表的查询速度

(m, n)间连续整数的算法快多少倍？请估算一下。 a. gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618) =gcd(1618, 1513) = gcd(1513, 105) = gcd(1513, 105) = gcd(105, 43) =gcd(43, 19) = gcd(19, 5) = gcd(5, 4) = gcd(4, 1) = gcd(1, 0) = 1. b.有a可知计算gcd(31415,14142)欧几里德算法做了11次除法。连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1·14142 和 2·14142之间，所以欧几里德算法比此算法快1·14142/11 ≈ 1300 与 2·14142/11 ≈ 2600 倍之间。 6.证明等式 gcd(m,n)=gcd(n,m mod n)对每一对正整数 m,n 都成立. Hint：根据除法的定义不难证明：？如果 d 整除 u 和 v，那么 d 一定能整除 u±v；？如果 d 整除 u，那么 d 也能够整除 u 的任何整数倍 ku. 对于任意一对正整数 m,n，若 d 能整除 m 和 n，那么 d 一定能整除 n 和 r=m mod n=m-qn；显然，若 d 能