算法——程序的灵魂_算法是程序设计的核心,是程序设计的灵魂

1、程序=算法+数据结构

一个程序主要包含以下两方面的信息：

（1）对数据的描述，在程序中要指定用到哪些数据，以及这些数据的类型和数据的组织形式，这就是数据结构(data structure)。

（2）对操作的描述，要求计算机进行的操作步骤，也就是算法（algorithm)。

数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果，打个比方，厨师制作菜肴，需要有菜谱，菜谱上一般应说明：①所用配料，指出为了做出顾客所指定的菜肴，应该使用哪些材料；②操作步骤，指出有了这些原料，应按什么样的步骤进行加工，才能做出所需的菜肴。
没有原料是无法加工成所需菜肴的，而同一些原料可以加工出不同风味的菜肴。作为程序设计人员，必须认真考虑和设计数据结构和操作步骤(即算法)。著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式：

算法+数据结构=程序

直到今天，这个公式对于过程化程序来说依然是适用的。
 

2、什么是算法

算法是解决“做什么”和“怎么做”的问题。

做任何事情都有一定的步骤，比如：要考大学，首先得要填志愿表，交报名费，拿到准考证，按时参加考试，得到l录取通知书，到指定学校报到注册，这些步骤都是按一定顺序进行得，缺一不可，次序错了也不行。从事各种工作和活动，都必须事先想好进行得步骤，然会按部就班得进行，才能避免产尘错乱，实际上，在人们的日常生活中，由于已经养成习惯，所以人们并没有意识到每件事情都需要事先设计出“行动步骤”，比如吃饭、上学和做作业等等，事实上都是按照一定的步骤进行的，只是人们不必每次都重复考虑他而已。

  不要认为只有“计算”才有算法，广义的来讲，为解决一个问题而采取的方法和步骤就称为算法。

eg:描述太极拳动作的图解就是“太极拳的算法”；一首乐曲的乐谱，也可以称为该乐曲的算法。

对同一问题，可以有不同的解题方法和步骤，例如从1加到100，可以从1开始：1+2再加3再加4........一直加到100，然而也可以采用等差数列求和的方法，当然也还有许多其他的方法。

方法又优劣之分，有的步骤少，简单，有的步骤多，繁琐，一般来说，大家都希望使用步骤少且简单的方法。因此、为了有效的进行解题，不仅要保证算法正确，还要考虑算法的质量，选择合适的算法。

计算机的算法理由分为两大类别：数值运算算法和非数值运算算法。

3、简单的算法举例

例子选自谭浩强谭老师的《c程序设计》

例1：求1*2*3*4*5
可以用最原始的方法进行：

步骤1：先求1乘以2，得到结果2.
步骤2：将步骤1得到的乘积2再乘以3，得到结果6.
步骤3：将6再乘以4，得24.
步骤4：将24再乘以5，得120.这就是最后的结果

这样的算法虽然是正确的，但太烦琐。如果要求1×2×…×1000，则要写999个步骤，显然是不可取的。而且每次都要直接使用上一步骤的具体运算结果(如2，6，24等)，也不方便，应当能找到一种通用的表示方法。
不妨这样考虑：设置两个变量，一个变量代表被乘数，一个变量代表乘数，不另设变量存放乘积结果，而是直接将每一步骤的乘积放在被乘数变量中。今设变量p为被乘数，变量1为乘数。用循环算法来求结果。可以将算法改写如下：

S1：令p=1，或写成1p(表示将1存放在变量p中)
S2：令i=2，或写成2i(表示将2存放在变量1中)
S3：使p与i相乘，乘积仍放在变量p中，可表示为：p*jp
S4：使i的值加1，即i+1i
S5：如果1不大于5，返回重新执行S3及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5！的值。

上面的S1，S…代表步骤1、步骤2……S是Step(步)的缩写。这是写算法的习惯用法。 step1=8
请读者仔细分析这个算法，能否得到预期的结果。显然这个算法比前面列出的算法简练。
如果题目改为：求1×3×5×7×9×11。
算法只须做很少的改动：

S1：1p 
S2：3i
S3:p*ip
S4：i+2i
S5：若i<11，返回S3；否则，结束
其中S5也可以表示为： 
S5：若i>11，结束；否则返回S3。

上面两种写法，作用是相同的。
可以看出用这种方法表示的算法具有一般性、通用性和灵活性。S3～S5组成一个环，在满足某个条件(i≤11)时，反复多次执行S3，S4和S5步骤，直到某一次执行S5步骤时，发现乘数i已超过事先指定的数值(11)而不返回S3为止。此时算法结束，变量p的值就是所求结果。

由于计算机是高速运算的自动机器，实现循环是轻而易举的，所有计算机高级语言中都有实现循环的语句，因此，上面的算法不仅是正确的，而且是计算机能方便实现的较好算法。

4、算法的特性

不要以为任意写出的一些执行步骤就构成一个有效且好的算法一个有效算法应该具有以下特点。
(1)有穷性。一个算法应包含有限的操作步骤，而不能是无限的。

事实上，“有穷性”往往指“在合理的范围之内”。如果让计算机执行一个历时1000年才结束的算法，这虽然是有穷的，但超过了合理的限度，人们也不把它视为有效算法。究竟什么算“合理限度”，由人们的常识和需要判定。

(2)确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。

例如，有一个健身操的动作要领，其中有一个动作：“手举过头顶”，这个步骤就是不确定的，含糊的。是双手都举过头？还是左手或右手？举过头顶多少厘米？不同的人可以有不同的理解。算法中的每一个步骤应当不致被解释成不同的含义，而应是明确无误的。也就是说，算法的含义应当是唯一的，而不应当产生“歧义性”。所谓“歧义性”，是指可以被理解为两种(或多种)的可能含义。

(3)有零个或多个输入。所谓输入是指在执行算法时需要从外界取得必要的信息。

(4)有一个或多个输出。算法的目的是为了求解，“解”就是输出。

算法的输出并不一定就是计算机的打印输出或屏幕输出，一个算法得到的结果就是算法的输出。没有输出的算法是没有意义的。

(5)有效性。算法中的每一个步骤都应当能有效地执行，并得到确定的结果。

例如，若b=0，则执行a/b是不能有效执行的。

对于一般最终用户来说，他们并不需要在处理每一个问题时都要自己设计算法和编写程序，可以使用别人已设计好的现成算法和程序，只须根据已知算法的要求给予必要的输入，就能得到输出的结果。对使用者来说，已有的 算法如同一个“黑箱子”一样，他们可以不了解 “黑箱子”中的结构，只是从外部特性上了解算法的作用，即可方便地使用算法。

例如，对一个“输入3个数，求其中最大值”的算法，可以用图下图表示，只要输入a，b，c这3个数，执行算法后就能得到其中最大的数。

对于程序设计人员来说，必须学会设计常用的算法，并且根据算法编写程序

5、怎样表示一个算法

为了表示一个算法，可以用不同的方法，常用的方法有：自然语言，传统流程图，结构化流程图和伪代码。

5.1、用自然语言来表示算法

自然语言就是人们日常使用的语言，可以是汉语、英语或其他语言。用自然语言表示通俗易懂，但文字冗长，容易出现歧义。自然语言表示的含义往往不大严格，要根据上下文才能判断其正确含义。例如有这样一句话：“张先生对李先生说他的孩子考上了大学”，请问是张先生的孩子考上大学还是李先生的孩子考上大学呢？光从这句话本身难以判断。此外，用自然语言来描述包含分支和循环的算法不大方便。因此，除了那些很简单的问题以外，一般不用自然语言表示算法。

5.2、用流程图表示算法
流程图是用一些图框来表示各种操作。用图形表示算法，直观形象，易于理解。美国国家标准化协会(American National Standard Institute, ANSI)规定了一些常用的流程图符号(如下图)，已为世界各国程序工作者普遍采用。

 连接点（小圆圈）是用于将画在不同地方的流程线连接起来。

用连接点可以避免线路交叉或过长，使流程图清晰，注释框不是流程中必要的部分，不反应流程和操作，只是为了对流程图中某些框的操作做必要的补充说明，以帮助阅读流程图的人更好地理解流程图的作用。

三种基本结构：

1966年，Bohra和Jacopini提出以下三种结构，用这3种基本结构作为表示一个良好算法的基本单元。

分别是：顺序结构、选择结构、循环结构

5.3、用N—S流程图来表示算法

（N-S图如同一个多层的盒子，又称多盒图）

既然用基本结构的顺序组合可以表示任何复杂的算法结构，那么，基本结构之间的流线就是多余的了。
1973年，美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。在这种程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称N-S结构化流程图(N和S是两位美国学者的英文姓氏的首字母)。这种流程图适于结构化程序设计，因而很受欢迎。
N-S流程图用以下的流程图符号。
(1)顺序结构。顺序结构用图2.24形式表示。A和B两个框组成一个顺序结构。
(2)选择结构。选择结构用图2.25表示。当p条件成立时执行A操作，p不成立则执行B操作。注意：图2.25是一个整体，代表一个基本结构。
(3)循环结构。当型循环结构用图2.26形式表示，当pl条件成立时反复执行A操作.直到p1条件不成立为止。
直到型循环结构用图2.27形式表示。

 N-S算法的优点：它比文字描述更加直观形象，便于理解，比传统流程图紧凑易画，尤其是他废除了流程线以后，整个算法结构是由各个基本结构按顺序组成的，流程图中从上到下的顺序就是程序执行的顺序，也就是在图中位置在上面的先执行，在下面的后执行，写算法和看算法只须从上往下进行就可以了，十分方便，用N-S图表示的算法都是结构化的算法（它不可能出现流程无规律的跳转，而只能自上而下的顺序执行）。

归纳起来可知：一个结构化的算法是由一些基本结构顺序组成的；在基本结构之间不存在向前向后的跳转，流程的转移只存在于一个基本结构方位之内（如循环中流程的跳转）；一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变，如果一个算法不能分解为若干个基本机构，那他必然不是一个结构化的算法。

5.4、用伪代码表示算法

用传统的流程图和N-S图表示算法直观易懂，但画起来比较费事，在设计一个算法时，可能需要反复修改，而修改流程图是比较麻烦的，因此，流程图适合一个算法，但在设计算法过程中使用不是很理想（尤其是当算法比较复杂，需要反复修改的时候）。为了设计算法时方便，常使用一种称为伪代码的工具。

伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法，它如同一篇文章一样，自上而下的写下来，每一行（或几行）表示一个基本操作，它不需要用到符号，因此书写方便、格式紧凑、修改方便，容易看懂，也便于向计算机语言算法（程序）过渡。

用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用，只要把意思表达清楚，便于书写和阅读就行，书写的格式也要写成清晰易读的形式。

例如：求5！，用伪代码表示的算法如下：

begin            (算法开始）

   1t

   2i

   while i≤5

{

 t * it

 i + 1i

 }

 print t

end           （算法结束） 

5.5、用计算机语言表示算法

要完成一项工作，包括设计算法和实现算法两个部分。例如，作曲家创作一首乐谱就是设计一个算法，但它仅仅是一个乐谱，并未变成音乐，而作曲家的目的是希望使人们听到悦耳动人的音乐。演奏家按照乐谱的规定进行演奏，就是“实现算法”。在没有人实现它时，乐谱是不会自动发声的。一个菜谱是一个算法，厨师炒菜就是在实现这个算法。设计算法的目的是为了实现算法。因此，不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。
到目前为止，只讲述了描述算法，即用不同的方法来表示操作的步骤。而要得到运算结果，就必须实现算法。实现算法的方式可能不止一种。可以用人工心算的方式实现而得到结果。也可以用笔算或算盘、计算器来求出结果，这都是实现算法。
我们考虑的是用计算机解题，也就是要用计算机实现算法，而计算机是无法识别流程图和伪代码的，只有用计算机语言编写的程序才能被计算机执行，因此在用流程图或伪代码描述一个算法后，还要将它转换成计算机语言程序。用计算机语言表示的算法是计算机能够执行的算法。
用计算机语言表示算法必须严格遵循所用的语言的语法规则，这是和伪代码不同的。

例如求5!用C语言表示：

#include<stdio.h>
int main(){
	int i, t;
	t=1;
	i=2;
	while(i<5){
		t=t*i;
		i=i+1;
		
	}
	printf("%d\n",t);
	return 0;
}

说明：写出了C的程序，任然只是描述了算法，并未实现算法，只有运行程序才是实现算法；

好了，完了！

-END-