算法合集之《一类算法复合的方法》共17页文档

常用算法一. 基本概念：1. 算法：就是解决问题方法的精确描述。

并不是所有问题都有算法，有些问题经研究可行，则相应有算法；而有些问题不能说明可行，则表示没有相应算法。

算法具有以下性质：是一有穷动作的序列；动作序列仅有一个初始动作；序列中每个动作的后继动作是确定的；序列的终止表示问题得到解答或问题没有解答2. 算法的分类：数值的和非数值的数值的算法是以数学方式表示的问题求数值解的方法，如：代数方程计算、矩阵计算、线性方程组求解、函数方程求解等；非数值的算法是求非数值解的方法，如排序查找、模式匹配、排列模拟、表格处理、文字处理等。

3. 算法设计：主要是针对各类具体问题设计良好的算法及研究设计算法的规律和方法。

4. 常用的算法设计方法：数值算法：迭代法、递归法、插值法等；非数值算法：分治法、贪婪法、回溯法等。

5. 算法分析：是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度。

算法的复杂度分时间复杂度和空间复杂度。

二. 常用数值计算算法1. 迭代法迭代法适用于方程(或方程组)求解，是使用间接方法求方程近似根的一种常用算法。

(参见清华版《PASCAL 程序设计P89练习4.23》设方程f(x)=0，该方法将方程表示为等价形式：x=g(x)，或一般地将f(x)拆成两个函数f 1、f 2，即f(x)= f 1(x)-f 2(x) =0，因而有f 1(x)=f 2(x)。

其中f 1(x)是这样一个函数，对于任意数c ，容易求出f 1(x)=c 的精确度很高的实根。

迭代法求解算法如下：(1). 首先选一个x 的近似根x 0，从x 0出发，代入右面函数，并解方程f 1(x)=f 2(x 0)得到下一个近似根x 1;(2). 将上次近似根x 1代入右面函数，并解方程f 1(x)=f 2(x 1)，得到又一个近似根x 2(3). 重复(2)的计算，得到一系列近似根x 0,x 1,x 2,…,x i ,x i+1,…,x n ,…； 若方程有根，这数列收敛于方程的根，若满足ε 1--n n x x ，则认为x n 是方程的近似根。

经典算法实例范文算法是一系列解决问题的步骤或规则，是计算机科学中非常重要的概念。

经典算法是指在计算机科学领域被广泛应用并被证明相对高效的算法。

本文将介绍几个经典算法的实例。

一、排序算法排序算法是最基本、最常用的算法之一、下面将介绍两个经典的排序算法。

1.冒泡排序冒泡排序是一种简单的排序算法，它的基本思路是多次遍历数组，每次将相邻的两个元素逐个比较，如果顺序不对则交换位置。

这样一次遍历后，最大的元素会被移到最后。

重复n-1次遍历，就可以完成排序。

冒泡排序的时间复杂度是O(n^2)。

2.快速排序快速排序是一种高效的排序算法，它的基本思路是选择一个基准元素，通过一趟排序将待排序的序列分成两个独立的部分，其中一部分的所有元素都小于基准，另一部分的所有元素都大于等于基准。

然后对这两个部分分别进行递归排序，最后合并两个部分得到有序序列。

快速排序的时间复杂度是 O(nlogn)。

二、查找算法查找算法是在给定的数据集合中一些特定元素的算法。

下面将介绍两个常用的查找算法。

1.二分查找二分查找也称为折半查找，是一种在有序数组中查找一些特定元素的算法。

它的基本思路是首先确定数组中间位置的元素，然后将要查找的元素与中间元素进行比较，如果相等则返回位置，如果小于则在左部分继续查找，如果大于则在右部分继续查找。

二分查找的时间复杂度是 O(logn)。

2.哈希查找哈希查找是通过哈希函数将关键字映射到哈希表中的位置，然后根据映射位置在哈希表中查找关键字。

哈希查找的时间复杂度是O(1)。

三、图算法图是由节点和边组成的一种数据结构，图算法主要用于解决与图相关的问题。

下面将介绍两个常用的图算法。

1.广度优先广度优先是一种用于图的遍历和的算法。

它的基本思路是从图的其中一顶点出发，遍历所有与之相邻的顶点，然后再依次遍历这些相邻顶点的相邻顶点，以此类推，直到访问完所有顶点，或者找到目标顶点。

广度优先使用队列来实现，时间复杂度是O(，V，+，E，)，其中，V，表示图的顶点数，E，表示图的边数。

束优化算法——复合形法•一、基本原理复合形法的基本思路是在n维空间的可行域中选取K个设计点（通常取）作为初始复合形（多面体）的顶点。

然后比较复合形各顶点目标函数的大小，其中目标函数值最大的点作为坏点，以坏点之外其余各点的中心为映射中心，寻找坏点的映射点，一般说来此映射点的目标函数值总是小于坏点的，也就是说映射点优于坏点。

这时，以映射点替换坏点与原复合形除坏点之外其余各点构成K个顶点的新的复合形。

如此反复迭代计算，在可行域中不断以目标函数值低的新点代替目标函数值最大的坏点从而构成新复合形，使复合形不断向最优点移动和收缩，直至收缩到复合形的各顶点与其形心非常接近、满足迭代精度要求时为止。

最后输出复合形各顶点中的目标函数值最小的顶点作为近似最优点。

现以图5所示二维不等式约束优化问题来作进一步说明。

其数学模型为D：其中，，可称为隐式约束条件，而边界约束，可称为显式约束条件。

在可行域内先选定四个点、、、(这里取)作为初始复合形的顶点，计算这四个点的目标函数值，并作比较，得出坏点和好点：(7)(8)由图5,可以看出点为好点，点为坏点，即。

以、、三点的中心为映射中心，寻找坏点的映射点：（9）式中，a为映射系数，一般，通常取a=1.3。

然后计算映射点处目标函数与坏点目标函数值相比是否下降，并同时检查是否在可行域内。

如果下降性、可行性这两方面都得到满足，则以点替换点，由与、、共四个点构成一个新复合形（如图5中虚线所示)。

这个新复合形肯定优于原复合形；如果上述两个条件不能同时满足.则可将映射系数缩半，即，仍按式(9 )迭代，重新取得新的映射点，使其同时满足下降性、可行性条件。

有时甚至要经过多次缩减映射系数才能使回缩的映射点最后满足这两个条件。

这时以回缩成功的映射点和、、构成新复合形。

构成新复合形就完成了一轮迭代。

以后再按上述方法进行迭代搜索，不断地使复合形向着目标函数减小的方向移动和收缩，直到逼近最优解。

通过以上说明，复合形寻优可以归为两大步骤：第一步是在可行域内构成初始复合形，第二步是通过复合形的收缩和移动不断调优，逐步逼近最优点。

什么是算法？简而言之，任何定义明确的计算步骤都可称为算法，接受一个或一组值为输入，输出一个或一组值。

（来源：homas H. Cormen， Chales E. Leiserson 《算法导论第3版》）可以这样理解，算法是用来解决特定问题的一系列步骤（不仅计算机需要算法，我们在日常生活中也在使用算法）。

算法必须具备如下3个重要特性：［1］有穷性。

执行有限步骤后，算法必须中止。

［2］确切性。

算法的每个步骤都必须确切定义。

［3］可行性。

特定算法须可以在特定的时间内解决特定问题，其实，算法虽然广泛应用在计算机领域，但却完全源自数学。

实际上，最早的数学算法可追溯到公元前1600年-Babylonians有关求因式分解和平方根的算法。

那么又是哪10个计算机算法造就了我们今天的生活呢请看下面的表单，排名不分先后：1. 归并排序（MERGE SORT），快速排序（QUICK SORT）和堆积排序（HEAP SORT）哪个排序算法效率最高这要看情况。

这也就是我把这3种算法放在一起讲的原因，可能你更常用其中一种，不过它们各有千秋。

归并排序算法，是目前为止最重要的算法之一，是分治法的一个典型应用，由数学家John von Neumann于1945年发明。

快速排序算法，结合了集合划分算法和分治算法，不是很稳定，但在处理随机列阵（AM-based arrays）时效率相当高。

堆积排序，采用优先伫列机制，减少排序时的搜索时间，同样不是很稳定。

与早期的排序算法相比（如冒泡算法），这些算法将排序算法提上了一个大台阶。

也多亏了这些算法，才有今天的数据发掘，人工智能，链接分析，以及大部分网页计算工具。

2. 傅立叶变换和快速傅立叶变换这两种算法简单，但却相当强大，整个数字世界都离不开它们，其功能是实现时间域函数与频率域函数之间的相互转化。

能看到这篇文章，也是托这些算法的福。

因特网，WIFI，智能机，座机，电脑，路由器，卫星等几乎所有与计算机相关的设备都或多或少与它们有关。

32个计算机经典算法计算机科学中最重要的32个算法(转）来源：Marvin（马文韬）的日志奥地利符号计算研究所（Research Institute for Symbolic Computation，简称RISC）做了一个调查，投票选出32个最重要的算法：搜索算法图形搜索算法，从给定起点到给定终点计算出路径。

其中使用了一种启发式的估算，为A* ——每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。

算法以得到的次序访问这些节点。

因此，A*搜索算法是最佳优先搜索的范例。

集束搜索（又名定向搜索，Beam Search——）最佳优先搜索算法的优化。

使用启发式函数评估它检查是固定数字的每个节点的能力。

不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m——集束的宽度。

）在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

二分查找（Binary Search——）在多种最优化问题中寻找特定最优化解决方案的算法，特别分支界定算法（Branch and Bound——是针对离散、组合的最优化。

算法一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统 Buchberger——中高斯消元法的泛化。

——数据压缩采取特定编码方案，使用更少的字节数（或是其他信息承载单元）对信息编码的过程，又叫来源编码。

密钥交换算法一种加密协议，允许双方在事先不了解对方的情况下，在不安全的Diffie-Hellman——通信信道中，共同建立共享密钥。

该密钥以后可与一个对称密码一起，加密后续通讯。

算法针对没有负值权重边的有向图，计算其中的单一起点最短算法。

Dijkstra——离散微分算法（Discrete differentiation））展示互相覆盖的子问题和最优子架构算法动态规划算法（Dynamic Programming——欧几里得算法（Euclidean algorithm——）计算两个整数的最大公约数。

程序员最需要了解的64种算法作为一个程序员，算法是非常重要的知识，因为算法是实现计算机程序的基础。

在今天的计算机领域，有许多不同的算法，每个都有其独特的用途和优缺点。

因此，在许多情况下，程序员必须根据特定需求选择最适合的算法。

下面是64种程序员最需要了解的算法：一、查找算法1.线性查找算法线性查找算法是最基本的查找算法，可以在列表中查找给定的元素。

2. 二分查找算法二分查找算法也称为折半查找算法，它可以在有序列表中查找给定的元素。

3.哈希表查找算法哈希表查找算法是通过计算散列值来查找元素，具有快速查找的优点。

二、排序算法4.冒泡排序算法冒泡排序算法是一种交换排序算法，它通过不断交换相邻的元素来进行排序。

5.选择排序算法选择排序算法是一种简单的排序算法，将序列中的元素按指定顺序排列。

6.插入排序算法插入排序算法是一种通过改变数组元素位置来对数组进行排序的算法。

7.快速排序算法快速排序算法是一种分治算法，通过递归依次划分数组，直到每个部分只剩下一个元素。

8.归并排序算法归并排序算法是一种通过将两个有序数组合并成一个单一的有序数组来排序的算法。

9.堆排序算法堆排序算法是一种基于堆栈实现的排序算法，它将一个无序序列变成一个有序序列。

10.希尔排序算法希尔排序算法是一种改进的插入排序算法，它通过分组对元素进行排序。

11.计数排序算法计数排序算法是一种线性时间的排序算法，通过确定每个元素出现的次数来实现排序。

12.鸡尾酒排序算法鸡尾酒排序算法是一种改进的冒泡排序算法，它通过在每次循环中来回移动排序的区域来实现排序。

三、查找与排序的组合算法13.基数排序算法基数排序算法是一种根据数字位来排序的算法，通过分别对每一位进行排序来实现排序。

14.桶排序算法桶排序算法是一种通过将元素分配到不同的桶中来排序的算法。

四、字符串算法15.字符串匹配算法字符串匹配算法是一种用于在一个文本中查找特定字符串的算法。

16.KMP算法KMP算法是一种字符串匹配算法，它通过部分匹配表来实现匹配。

一类排序问题的近似算法排序是一类重要的组合最优化问题，广泛应用于管理科学，计算机科学和工程技术等很多领域。

本文主要研究任务具有不同准备时间，加工过程不能被中断的单机排序问题1，这是一类最大延误问题，与任务的工期有关，本文通过利用分枝定界法对问题给出了算法。

第一章我们简要介绍了排序问题的三参表示法和分类，以及我们所要重点研究的单击排序问题中的最大延误问题。

第二章对没有准备时间的最大延误问题1||给出EDD法则，然后研究有不同准备时间，加工过程可以中断的1问题，根据EDD规则给出最优多项式算法。

最后，我们在前两种问题的基础上提出出问题（2.3）的一种近似算法——分枝定界法，。

第三章我们对问题（2.3）的分枝定界算法进行算法设计，并对其证明得到最优排序，举例实现。

排序问题产生的背景主要是机械制造，后来被广泛应用于计算机系统，运输调度，生产管理等领域。

从普通的生产部门计划安排，人员调度，学校课程表的制定，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法。

本文讨论的问题是没有准备时间的最大延误问题1||（2.1），有不同准备时间，加工过程可以中断的1（2.2）问题，并且重点研究了任务具有不同准备时间、加工不允许中断的单机排序问题：1(2.3)。

问题（2.3）是强NP-难的，本文给出了证明，并且经常用分枝定界法来求解。

而目前对于问题（2.3）给出的分枝定界法比较模糊，因此本文对分枝定界算法进行重新设计并且在具体分枝时采取了一些重要的策略，即将深探法和每层选取下界最小的节点进行分枝相结合，这样作的好处在于可以迅速产生较好的可行排序，从而更快地除去无用的分枝，以这样可以较快地得到最优排序，并且对本文给出的分枝定界法得到的序列为最优排序进行了证明。

并给出例子进行运算，得到最优序列。

第一章绪论1.1排序问题简介1.1.1研究背景及意义排序论是组合优化中的一个分支，有着广阔的应用前景。

深入来看，排序论对提高效率、资源的合理配置、工程进展统筹安排以及经济运行等方面都起到了辅助决策的作用，所以管理层和决策层必须了解排序问题的的理论和应用。

算法设计方法的分类及经典算法作者：黄友亮来源：《科学导报·学术》2020年第68期简单来说，所谓算法就是定义良好的计算过程，他取一个或一组值作为输入，并产生一个或者一组值作为输出。

亦即，算法就是一系列的计算步骤，用来将输入数据转换为输出结果。

我们还可以将算法看作一种工具，用来解决一个具有良好规格说明的计算问题。

有关该问题的表述可以用通用语言，来规定所需要的输入/输出关系。

与之对应的算法则描述了一个特定的计算过程，用于实现这一输入/输出关系。

计算机科学经过几十年的发展，孕育出许多算法设计的方法以及运用这些方法设计的算法，他们广泛运用于计算机研究领域以及计算机意外的现实生活中的各个领域。

其中，算法设计的方法包含有一下几类：一、分治法有很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的子问题。

这些算法通常采用分治策略：将问题划分成n个规模较小而结构与原问题相似的子问题;递归地解决这些iwenti，然后再合并其结果，就得到原问题的解。

分治模式在每一层递归上都有三个步骤：分解（Divide）：将原问题分解成一系列子问题;解决（Conquer）：递归地解决各子问题。

若子问题足够小，则直接求解;合并（Combine）：将子问题的结果合并成原问题的解。

﹒分治法的经典算法——合并排序（merge sort）。

合并排序是建立在归并操作上的一种有效的排序算法。

该算法是采用分治法的一个非常典型的应用。

合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。

然后再把有序子序列合并为整体有序序列。

将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表合并排序直观地操作如下：分解：将n个元素分成n/2个元素的子序列;解决：用合并排序法对两个子序列递归地排序;合并：合并两个已排序的子序列以得到排序结果。

常⽤经典算法（整理中）Ｃ语⾔经典算法及程序算法（Algorithm）：计算机解题的基本思想⽅法和步骤。

算法的描述：是对要解决⼀个问题或要完成⼀项任务所采取的⽅法和步骤的描述，包括需要什么数据（输⼊什么数据、输出什么结果）、采⽤什么结构、使⽤什么语句以及如何安排这些语句等。

通常使⽤⾃然语⾔、结构化流程图、伪代码等来描述算法。

⼀、⼀些简单算法1.求两个整数的最⼤公约数、最⼩公倍数2.判断素数3.验证哥德巴赫猜想4.超级素数5.猴⼦选⼤王6.数的全排列7.迭代法求平⽅根⼆、排序算法1.选择排序2.冒泡排序3.插⼊排序4.快速排序5.第K⼩元素6.⼆分查找法三、⾼精度数算法1.已知Ｐ，且P×S=11...1，求Ｓ及１的个数2.⾼精度数加法3.⾼精度数减法4.⾼精度数乘法5.⾼精度数除法6.⾼精度数阶乘7. Fibonacci数列四、数据结构相关问题1.左右括号配对2.多项式相加3.N叉树五、复杂算法1．N⼥王问题六、动态规划实例应⽤1．求序列的最⼤连续序列和2．求序列的最长下降⼦序列长度3．数塔问题（解法⼀）4．数塔问题（解法⼆）⼀、⼀些简单算法1.求两个整数的最⼤公约数、最⼩公倍数最⼤公约数算法：(最⼩公倍数=两个整数之积/最⼤公约数)(1) 对于已知两数m，n，使得m>n；(2) m除以n得余数r；(3) 若r=0，则n为求得的最⼤公约数，算法结束；否则执⾏(4)；(4) m←n，n←r，再重复执⾏(2)。

程序：#include "stdio.h"int main( ){ int nm,r,n,m,t;printf("please input two numbers:\n");scan f("%d,%d”,&m,&n);nm=n*m;if (mn*/r=m%n;while (r!=0){ m=n; n=r; r=m%n; }printf("最⼤公约数:%d\n",n);printf("最⼩公倍数:%d\n",nm/n);return 0;}2.判断素数(只能被1或本⾝整除的数称为素数)算法：把m作为被除数，将2—INT（sqrt(m) ）作为除数，如果都除不尽，m就是素数，否则就不是。

高级算法：解决复杂计算问题的常用方法随着科技的发展，我们生活中的计算问题日益复杂，对算法的要求也越来越高。

为了解决这些复杂的计算问题，人们提出了许多高级算法。

高级算法是指在解决计算问题时使用的一些比较复杂和智能的算法。

它们通常能够有效地解决一些复杂的问题，提高计算的效率和精度。

本文将对几种常用的高级算法进行介绍，以及它们在实际问题中的应用。

一、分治算法分治算法是一种将问题分解成若干个小问题，然后分别解决的算法。

通常情况下，分治算法会将原问题划分成几个规模较小的子问题，然后递归地解决每个子问题，最后将各个子问题的解合并起来得到原问题的解。

这种算法在解决一些复杂的计算问题时表现出了很高的效率。

1.1应用案例分治算法的应用非常广泛，比如在计算机视觉中，图像分割问题可以使用分治算法进行处理。

由于图像分割需要对图像进行分区，并找出图像中各个区域的边界，因此问题的规模较大。

采用分治算法可以将图像分割问题划分成若干个小的图像区域，然后递归地对每个小区域进行处理，最后将每个小区域的处理结果合并起来，从而得到整个图像的分割结果。

1.2算法流程分治算法的流程一般包括三个步骤：分解、解决和合并。

在分解步骤中，原问题被划分成若干个规模较小的子问题；在解决步骤中，递归地解决每个子问题；在合并步骤中，将各个子问题的解合并起来，得到原问题的解。

分治算法的成功与否主要取决于解决步骤的效率和合并步骤的正确性。

二、动态规划算法动态规划算法是一种通过把原问题分解成相互重叠的子问题，然后利用子问题的解来解决原问题的算法。

它通常用于优化计算问题的解，提高算法的效率和精度。

动态规划算法的优势在于能够避免重复的计算，从而提高计算的效率。

2.1应用案例动态规划算法在资源调度领域有着广泛的应用。

比如在生产调度中，需要对生产资源进行合理的调度，以最大程度地提高生产效率。

动态规划算法可以对生产资源的使用情况进行分析，然后利用子问题的解来优化资源调度，从而达到提高生产效率的目的。

10种常用典型算法什么是算法？简而言之，任何定义明确的计算步骤都可称为算法，接受一个或一组值为输入，输出一个或一组值。

（来源：homas H.Cormen，Chales E.Leiserson《算法导论第3版》）可以这样理解，算法是用来解决特定问题的一系列步骤（不仅计算机需要算法，我们在日常生活中也在使用算法）。

算法必须具备如下3个重要特性：［1］有穷性。

执行有限步骤后，算法必须中止。

［2］确切性。

算法的每个步骤都必须确切定义。

［3］可行性。

特定算法须可以在特定的时间内解决特定问题，其实，算法虽然广泛应用在计算机领域，但却完全源自数学。

实际上，最早的数学算法可追溯到公元前1600年-Babylonians有关求因式分解和平方根的算法。

那么又是哪10个计算机算法造就了我们今天的生活呢？请看下面的表单，排名不分先后：1.归并排序（MERGE SORT），快速排序（QUICK SORT）和堆积排序（HEAP SORT）哪个排序算法效率最高？这要看情况。

这也就是我把这3种算法放在一起讲的原因，可能你更常用其中一种，不过它们各有千秋。

归并排序算法，是目前为止最重要的算法之一，是分治法的一个典型应用，由数学家John von Neumann于1945年发明。

快速排序算法，结合了集合划分算法和分治算法，不是很稳定，但在处理随机列阵（AM-based arrays）时效率相当高。

堆积排序，采用优先伫列机制，减少排序时的搜索时间，同样不是很稳定。

与早期的排序算法相比（如冒泡算法），这些算法将排序算法提上了一个大台阶。

也多亏了这些算法，才有今天的数据发掘，人工智能，链接分析，以及大部分网页计算工具。

2.傅立叶变换和快速傅立叶变换这两种算法简单，但却相当强大，整个数字世界都离不开它们，其功能是实现时间域函数与频率域函数之间的相互转化。

能看到这篇文章，也是托这些算法的福。

因特网，WIFI，智能机，座机，电脑，路由器，卫星等几乎所有与计算机相关的设备都或多或少与它们有关。

经典算法解析⼀、什么是算法算法是⼀系列解决问题的清晰指令，也就是说，能够对⼀定规范的输⼊，在有限时间内获得所要求的输出。

算法常常含有重复的步骤和⼀些⽐较或逻辑判断。

如果⼀个算法有缺陷，或不适合于某个问题，执⾏这个算法将不会解决这个问题。

不同的算法可能⽤不同的时间、空间或效率来完成同样的任务。

⼀个算法的优劣可以⽤空间复杂度与时间复杂度来衡量。

算法的时间复杂度是指算法需要消耗的时间资源。

⼀般来说，计算机算法是问题规模n 的函数f(n)，算法执⾏的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

时间复杂度⽤“O（数量级）”来表⽰，称为“阶”。

常见的时间复杂度有： O（1）常数阶；O（log2n）对数阶；O（n）线性阶；O（n2）平⽅阶。

算法的空间复杂度是指算法需要消耗的空间资源。

其计算和表⽰⽅法与时间复杂度类似，⼀般都⽤复杂度的渐近性来表⽰。

同时间复杂度相⽐，空间复杂度的分析要简单得多。

⼆、算法设计的⽅法1.递推法递推法是利⽤问题本⾝所具有的⼀种递推关系求问题解的⼀种⽅法。

设要求问题规模为N的解，当N=1时，解或为已知，或能⾮常⽅便地得到解。

能采⽤递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的⼀系列解，构造出问题规模为I的解。

这样，程序可从i=0或i=1出发，重复地，由已知⾄i-1规模的解，通过递推，获得规模为i的解，直⾄得到规模为N的解。

【问题】阶乘计算问题描述：编写程序，对给定的n（n≦100），计算并输出k的阶乘k！（k=1，2，…，n）的全部有效数字。

由于要求的整数可能⼤⼤超出⼀般整数的位数，程序⽤⼀维数组存储长整数，存储长整数数组的每个元素只存储长整数的⼀位数字。

如有m 位成整数N⽤数组a[ ]存储：N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100并⽤a[0]存储长整数N的位数m，即a[0]=m。

⼏种常见的算法和⼏种常⽤的排序算法算法: 解决问题的⽅法总结⼀下常⽤的⼏种算法1.递推法递推是序列计算机中的⼀种常⽤算法。

它是按照⼀定的规律来计算序列中的每个项，通常是通过计算机前⾯的⼀些项来得出序列中的指定项的值。

其思想是把⼀个复杂的庞⼤的计算过程转化为简单过程的多次重复，该算法利⽤了计算机速度快和不知疲倦的机器特点。

例如如果你⼿⾥4个球分别: 红、蓝、⿊、黄, ⽽现在只有⼀个球⾥⾯装有答案, 你需要⼀个⼀个的打开去尝试那个球⾥⾯有答案, 这个过程就是递推法, 逐⼀排查2. 递归法程序调⽤⾃⾝的编程技巧称为递归（recursion）。

⼀个过程或函数在其定义或说明中有直接或间接调⽤⾃⾝的⼀种⽅法，它通常把⼀个⼤型复杂的问题层层转化为⼀个与原问题相似的规模较⼩的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，⼤⼤地减少了程序的代码量。

递归的能⼒在于⽤有限的语句来定义对象的⽆限集合。

⼀般来说，递归需要有边界条件、递归前进段和递归返回段。

当边界条件不满⾜时，递归前进；当边界条件满⾜时，递归返回。

注意：(1) 递归就是在过程或函数⾥调⽤⾃⾝;(2) 在使⽤递归策略时，必须有⼀个明确的递归结束条件，称为递归出⼝。

例如程序员都应该知道递归的意思, ⽅法⾥⾯调⽤⾃⼰3. 穷举法穷举法，或称为暴⼒破解法，其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从⽽得到问题的解。

它也常⽤于对于密码的破译，即将密码进⾏逐个推算直到找出真正的密码为⽌。

例如⼀个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。

理论上利⽤这种⽅法可以破解任何⼀种密码，问题只在于如何缩短试误时间。

因此有些⼈运⽤计算机来增加效率，有些⼈辅以字典来缩⼩密码组合的范围。

4. 贪⼼算法贪⼼算法是⼀种对某些求最优解问题的更简单、更迅速的设计技术。

超级经典算法大集合：老掉牙河内塔费式数列巴斯卡三角形三色棋老鼠走迷官（一）老鼠走迷官（二）骑士走棋盘八个皇后八枚银币生命游戏字串核对双色、三色河内塔背包问题（Knapsack Problem）数、运算蒙地卡罗法求PIEratosthenes筛选求质数超长整数运算（大数运算）长PI最大公因数、最小公倍数、因式分解完美数阿姆斯壮数最大访客数中序式转后序式（前序式）后序式的运算关于赌博洗扑克牌（乱数排列）Craps赌博游戏约瑟夫问题（Josephus Problem）集合问题排列组合格雷码（Gray Code）产生可能的集合m元素集合的n个元素子集数字拆解排序得分排行选择、插入、气泡排序Shell 排序法- 改良的插入排序Shaker 排序法- 改良的气泡排序Heap 排序法- 改良的选择排序快速排序法（一）快速排序法（二）快速排序法（三）合并排序法基数排序法搜寻循序搜寻法（使用卫兵）二分搜寻法（搜寻原则的代表）插补搜寻法费氏搜寻法矩阵稀疏矩阵多维矩阵转一维矩阵上三角、下三角、对称矩阵奇数魔方阵4N 魔方阵2(2N+1) 魔方阵1.河内之塔说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。

解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。

如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。