算法设计

算法
什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。
算法的特点

有穷性

确切性

输入项

输出项

可行性

一、数据对象的运算和操作：

计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类：

1.算术运算：加减乘除等运算

2.逻辑运算：或、且、非等运算

3.关系运算：大于、小于、等于、不等于等运算

4.数据传输：输入、输出、赋值等运算 [1] 

二、算法的控制结构：

一个算法的功能结构不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。
算法的历史

“算法”即演算法的大陆中文名称出自《周髀算经》；而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi，因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm"。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为"well-defined procedure"缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用。
算法的描述
自然语言案例

自然语言就是人们日常用的语言，这种表示方式通俗易懂，下面通过实例具体介绍。

【实例2.1】 求n！。

（1）定义3个变量i、n及mul，并为i和mul均赋初值为1。

（2）从键盘中输入一个数赋给n。

（3）将mul乘以i的结果赋给mul。

（4）i的值加1，判断i的值是否大于n，如果大于n，则执行步骤（5），否则执行步骤（3）。

（5）将mul的结果输出。

【实例2.2】 任意输入3个数，求这3个数中的最小数。

（1）定义4个变量分别为x、y、z以及min。

（2）输入大小不同的3个数分别赋给x、y、z。

（3）判断x是否小于y，如果小于，则将x的值赋给min，否则将y的值赋给min。

（4）判断min是否小于z，如果小于，则执行步骤（5），否则将z的值赋给min。

（5）将min的值输出。

 
流程图

流程图是一种传统的算法表示法，它用一些图框来代表各种不同性质的操作，用流程线来指示算法的执行方向。由于它直观形象，易于理解，所以应用广泛，特别是在语言发展的早期阶段，只有通过流程图才能简明地表述算法。

【实例2.3】 从键盘中输入3个数分别赋给a、b、c，要求按大小顺序把它们打印出来。流程图如图所示

3种基本结构

Bohra和Jacopini为了提高算法的质量，经研究提出了3种基本结构，即顺序结构、选择结构和循环结构，因为任何一个算法都可由这3种基本结构组成。这3种基本结构之间可以并列，可以相互包含，但不允许交叉，不允许从一个结构直接转到另一个结构的内部去。 

整个算法都是由3种基本结构组成的，所以只要规定好3种基本结构的流程图的画法，就可以画出任何算法的流程图。

顺序结构是简单的线性结构，在顺序结构的程序里，各操作是按照它们出现的先后顺序执行的，如图所示。

在执行完A框所指定的操作后，接着执行B框所指定的操作，这个结构里只有一个入口点A和一个出口点B。

【实例2.4】 输入两个数分别赋给变量i和j，再将这两个数分别输出。

   本实例流程图可以采用顺序结构来实现，如图所示。

选择结构也叫分支结构，如图所示

选择结构中必须包含一个判断框。图中所代表的含义是根据给定的条件p是否成立选择执行A框或者是B框。

下图所代表的含义是根据给定的条件P进行判断，如果条件成立则执行A框，否则什么也不做。

在循环结构中，反复地执行一系列操作，直到条件不成立时才终止循环。按照判断条件出现的位置，可将循环结构分为当型循环结构和直到型循环结构。

当型循环是先判断条件P是否成立，如果成立，则执行A框；执行完A框后，再判断条件P是否成立，如果成立，接着再执行A框；如此反复，直到条件P不成立为止，此时不执行A框，跳出循环。

直到型循环是先执行A框，然后判断条件P是否成立，如果条件P成立则再执行A；然后判断条件P是否成立，如果成立，接着再执行A框；如此反复，直到条件P不成立，此时不执行A框，跳出循环。
N-S流程图

N-S图是另一种算法表示法，是由美国人I.Nassi和B.Shneiderman共同提出的，其根据是：既然任何算法都是由前面介绍的3种结构组成，则各基本结构之间的流程线就是多余的，因此去掉了所有的流程线，将全部的算法写在一个矩形框内。N-S图也是算法的一种结构化描述方法，同样也有3种基本结构，下面分别进行介绍：

顺序结构的N-S流程图

选择结构的N-S流程图

当型循环的N-S流程图

直到型循环的N-S流程图

【实例2.7】 从键盘中输入一个数n，求n！。

该程序流程图如图所示。

【实例2.8】 求两个数a和b的最大公约数。流程图如图所示：

N-S流程图如图所示：

算法举例

目前，算法的应用非常广泛，常用的算法包括递推算法，递归算法，穷举算法，贪婪算法，分治算法，动态规划算法和迭代算法等多种。

1、递推算法
2、递归算法
3、穷举算法
4、贪婪算法
5、分治算法
6、动态规划算法
7、迭代算法