算法与算法分析计算机与算法有着不可分割的关系，可以说，没有算法就没有计算机，计算机无法独立于算法而存在，因此算法被誉为计算机的灵魂。

但是，算法不一定依赖于计算机而存在。

算法可以是抽象的，实现算法的主体可以是计算机，也可以是人。

只是多数时候，很多算法对于人来说过于复杂，计算工作量太大且常常重复，人脑难以胜任，算法就通过计算机来实现。

1.算法的概念日常生活中到处都在使用算法，例如，到商店购物，首先确定要购买的东西，然后进行挑选、比较，最后去付款，这一系列活动就是购物的“算法”。

算法就是解决问题的方法和步骤。

方法不同，对应的步骤自然也不一样。

算法设计时，首先应该考虑采用什么方法，确定后再考虑具体的求解步骤。

所以，通常把解题过程准确而完整的描述称为解该问题的算法。

进一步说，程序就是用计算机语言表达的算法，流程图就是图形化了的算法。

程序的目的是加工数据，而如何加工数据是算法的问题。

程序是算法与数据结构的统一。

算法是对事物本质的数学抽象，看似深奥却体现着点点滴滴的朴素思想。

因此，学习和研究算法能锻炼思维，使思维变得更加清晰、更有逻辑，对日后的学习和生活都会产生深远的影响。

【例1】交换两瓶墨水。

有一瓶红墨水、一瓶蓝墨水，现要求把原来装红墨水的瓶子改装蓝墨水，把原来装蓝墨水的瓶子改装红墨水。

【解】这个问题的解决办法是找一个空瓶子来倒腾一下，算法（也就是解决问题的步骤）如下：第一步：将红墨水倒入空瓶子中；第二步：将蓝墨水倒入原来装红墨水的瓶子中；第三步：将已倒入空瓶子中的红墨水倒入原来装蓝墨水的瓶子中；第四步：结束。

以上算法是用自然语言来写的，容易理解，但比较繁琐。

如果用变量a表示装有红墨水的瓶子，变量b表示装有蓝墨水的瓶子，变量t表示空瓶子，用符号“←”表示把一个变量的值放入另一个变量中（此处指把一个瓶子中的墨水倒入另一个瓶子中），那么上述算法表示如下：t ←aa ←bb ←t这就是常用的两个变量交换的算法，这样的算法简洁、明了。

【例2】求s = a + aa + aaa + aaaa + ...... 的值。

其中，a是一个数字（0≤a ≤9），n是最后一项中a的个数（n ≽1），a和n的值从键盘输入。

例如，若a = 7，n = 5，则s = 7+77+777+7777+77777。

【解】 这是一个求n 个数据项累加的问题，当输入n 的值后，算法可以用确定循环次数的循环结构实现。

设置一个存储累加和的变量s ，其初值为0；设置循环控制变量i 表示求和的项数（i ≤n ）；设置数据项为t ，其初值为0，在重复执行的循环体中逐次将t * 10 + a 的值累加到变量s 中。

算法流程图如图1所示。

图1 例2的流程图YN开始t ←0, s ←0i ←1t ←t*10 + ai ←i+1输出s 结束i ≤n 输入a,n s ←s +t由以上例子可以看出，一个算法由一些操作组成，这些操作是按一定的控制结构所规定的次序执行的。

这些操作包括：①逻辑运算：与、或、非；②算术运算：加、减、乘、除；③数据比较：大于、小于、等于、不等于；④数据传送：输入、输出、赋值。

算法中的每一步都必须能分解成这些基本操作，否则算法是不可行的。

算法的功能不仅取决于所选用的操作，还取决于各操作之间的执行次序，即控制结构。

任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成。

用流程图可以形象地表示出算法的控制结构。

2.算法的基本特性著名计算机科学家Knuth把算法的性质归纳为以下五点。

（1）有穷性（Finiteness）一个算法必须在执行有穷步之后结束，即任何算法必须在有限时间内完成。

算法的执行步数是有限的，解必须在有限步内得到，不能出现“死循环”，任何不会终止的算法都是没有意义的。

算法执行时间应该合理，这种合理性应该具体问题具体分析。

如果一个算法在计算机上要运行上千年，那就失去了实用价值，尽管它是有穷的。

（2）确定性（Definiteness）组成算法的每个步骤都是确定的、明确无误的。

也就是说，算法中的每一步必须有确切的含义，理解时不能产生二义性，不能模棱两可，不能含糊不清。

例如，生活中假定照着菜谱学做菜，这道菜的做法是这样的：第一步：锅中放入少许油，加花椒爆香；第二步：放入切好的肉片，煎炒到适当的时候放水；第三步：煮沸时，加入少量调味品；第四步：淋入适量香油，出锅。

生活中可以按照这样的菜谱做菜，但让计算机执行这样的“算法”就不行，因为其中有“少许”、“适当”、“少量”、“适量”等不确定性的词汇。

如果把这个菜的做法看成一个“算法”，那么这个算法是不满足确定性的。

（3）可行性（Effectiveness）算法中的每一步操作都应是可以执行的，或者都可以分解成计算机可执行的基本操作。

典型的、不可行的操作如下：①“公鸡下蛋”式的操作：比如以0做分母，即便在数学中也是不可行的。

②想当然的操作：例如算法中某一步要求方程f（x）=0的根。

计算机只是帮助人们计算，至于如何计算这是算法设计者或程序员的事，也就是说，如果我们不知道怎么求解一个问题，计算机也无能为力。

但像两个变量交换这样的算法步骤“A⇔B”是可行的，因为它可以分解成下面三个可执行的基本操作“T⇐A，A⇐B，B⇐T”。

（4）输入（Input）算法开始前，允许有若干个输入量，也可以没有输入量。

（5）输出（Output）每种算法必须有确定的结果，产生一个或多个输出。

否则，“只开花不结果”的算法是没有意义的。

可见，算法是一个过程，这个过程由一套明确的规则组成，这些规则制定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答。

3.算法的表示（描述）面对一个待求解的问题，求解的方法首先源于人的大脑，经思考、论证而产生。

算法表示（描述）就是把这种大脑中求解问题的方法和思路用一种规范的、可读性强的、容易转换成程序的形式（语言）描述出来。

算法描述出来是为了交流和共享，一是提交给程序设计人员，作为编写程序代码的依据，二是供算法研究、设计与学习用。

经过多年的研究和实践，描述算法大致有4种方法。

（1）自然语言自然语言就是我们生活中所使用的语言，如汉语、英语等。

用自然语言描述算法的特点是熟悉、方便和容易理解。

【例3】求3个数中值最大的一个。

算法用自然语言可描述如下：第一步：输入3个数a、b、c；第二步：如果a>=b，则将a放到max中，否则将b放到max中；第三步：如果c>=max，则将c放到max中；第四步：输出max，即为三个数中最大的一个。

此例中设置了一个变量max，用于存放两个数比较后的值较大的数。

【例4】输入一个大于1的正整数，求出该数的所有因数并输出。

算法用自然语言可描述如下：第一步：输入一个大于1的正整数n；第二步：依次以1、2、3、4…n-1、n为除数去除n；第三步：依次检查余数是否为0，若为0，则是n的因数；若不为0，则不是n的因数；第四步：输出n的所有因数。

用自然语言描述算法，其缺点和不足也相当明显，主要表现在以下三个方面。

①易产生歧义。

自然语言往往要根据上下文才能判别其含义，书写没有严格的标准，只有人类才能理解和接受。

②语句比较繁琐冗长，并且很难清楚地表达算法的逻辑流程。

如果算法中包含判断、循环处理，尤其是这些处理的嵌套层数增多，自然语言描述其流程既不直观又很难表达清楚。

③自然语言表示的算法不便翻译成计算机程序设计语言。

因此，自然语言常用于粗略地描述某个算法的大致情况。

（2）计算机语言计算机语言是一种人工语言，即人为设计的语言，如Pascal、VB、C、C++等。

用计算机语言来描述算法，得到的结果既是算法也是程序，直接可以上机运行。

【例5】求三个数中最大的数。

【解】用C语言描述的算法如下：#include <stdio.h>main(){int x,y,z,max;scanf(“%d,%d,%d”,&x,&y,&z);if(x>y)max=x;elsemax=y;if(z>max)max=z;printf(“最大值为:%d\n”,max);}计算机语言的语法非常严格，描述出来的过程过于复杂，对于学习算法设计的初学者来说，过早陷入程序设计语言的语法泥潭，难以抓住问题的本质。

此外，计算机语言很多，且各有特点，到底用哪一种语言来描述算法，把算法变成程序又用哪一种语言，都要根据具体情况来分析。

（3）图形化工具为了形象地描述算法，人们设计了许多专用的图形工具来描述算法，即以一种比较直观的方法展示算法的操作流程，如流程图、N-S图等。

流程图是使用最早的算法和程序描述工具。

它符号简单，表现直观、灵活（例如可用箭头线来表示程序中的goto操作），不依赖于任何具体的计算机和计算机程序设计语言。

由于流程线可以比较随意地跳转，很容易出现不符合结构化设计原则的现象，并且对于功能较复杂的算法，绘制流程图的规模会过于庞大，绘制过程也会过于繁杂，影响对算法的阅读理解。

N-S图也被称为盒图。

1973年，美国学者I. Nassi 和B. Shneiderman提出了一种在流程图中完全去掉流程线，全部算法写在一个矩形框内，在框内还可以包含其他框的流程图形式，称为N-S结构流程图（以两个人的名字的头一个字母组成）。

它比文字描述直观、形象、易于理解；比传统流程图紧凑易画，尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，不可能出现流程无规律的跳转，而只能自上而下地顺序执行，表示的算法都是结构化的算法。

但因为完全取消了“跳转”，可能使某些情况下简单的处理过程复杂化了。

【例6】 计算10！【解】 用流程图和N-S 图描述如下：图2 例6的流程图和N-S 图（4）伪代码为了避免自然语言的含混不清和防止歧义性，人们往往采用意义准确唯一且已形式化的类计算机语言来描述算法。

伪代码是一种介于自然语言和程序设计语言之间的代码，它表述Y N开始n ←1i ←2n ←n * i i >10i ←i+1输出n结束n ←1i ←2i ≤10n ←n * i输出n简洁、结构清晰、易于阅读。

伪代码不拘泥于程序设计语言的具体语法和实现细节，着重以灵活的形式表现被描述对象。

程序设计语言中一些与表达算法关系不大的部分往往被伪代码省略了，如变量定义等。

有时调用某些函数或处理简单任务也用一句自然语言代替，并不给出具体实现过程，如“找出3个数中的最大数”。

由于伪代码在语法结构上的随意性，目前并不存在一个通用的伪代码语法标准。

人们以某些高级程序设计语言为基础，例如Pascal、C、C++等，经简化后进行伪代码的编写，这种编写出来的语言称为“类Pascal语言”、“类C语言”等。

【例7】输入一个年份，判断是否为闰年，并输出结果。

算法主体用伪代码描述如下：scanf ( y );if (((y mod 4=0) and (y mod 100≠0)) or (y mod 400=0))printf (y”是闰年”);elseprintf (y”不是闰年”);【例8】输入3个数，判断能否构成三角形。