1.2 算法
学习计算机程序设计语言的目的,是要用语言作为工具,设计出可供计算机运行的程序。
在拿到一个需要求解的问题之后,怎样才能编写出程序呢?除了选定合理的数据结构外,一般来说,十分关键的一步是设计算法,有了一个好的算法,就可以用任何一种计算机高级语言把算法转换为程序(编写程序)。
算法是指为解决某个特定问题而采取的确定且有限的步骤。一个算法应当具有以下五个特性:
1.有穷性。一个算法包含的操作步骤应该是有限的。也就是说,在执行若干个操作步骤之后,算法将结束,而且每一步都在合理的时间内完成。
2.确定性。算法中每一条指令必须有确切的含义,不能有二义性,对于相同的输入必能得出相同的执行结果。
3.可行性。算法中指定的操作,都可以通过已经验证过可以实现的基本运算执行有限次后实现。
4.有零个或多个输入。在计算机上实现的算法是用来处理数据对象的,在大多数情况下这些数据对象需要通过输入来得到。
5.有一个或多个输出。算法的目的是为了求“解”,这些“解”只有通过输出才能得到。
算法可以用各种描述方法来进行描述,最常用的是伪代码和流程图。
伪代码是一种近似于高级语言但又不受语法约束的一种语言描述方式。这在英语国家中使用起来更为方便。
流程图也是描述算法的很好的工具,一般的流程图由图1.2中所示的几种基本图形组成。
由这些基本图形中的框和流程线组成的流程图来表示算法,形象直观,简单方便。但是,这种流程图对于流程线的走向没有任何限制,可以任意转向,在描述复杂的算法时所占篇幅较多,费时费力且不易阅读。
随着结构化程序设计方法的出现,1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式,这种流程图表余去掉了流程线,算法的每一步都用一个矩形框来描述,把一个个矩形框按执行的次序连接起来就是一个完整的算法。这种流程图界两位学者名字的第一个英文字母命名,称为N-S流程图。在下一节中将结合结构化程序设计中的三种基本结构来介绍这种流程图的基本结构。