文档介绍：刘师少
Tel: 86613747(h)
E-mail:lss@
授课: 51学时
学分: 3
教学目标:
知识、能力、素质
算法的概念
简单算法举例
算法的特性
怎样表示一个算法
结构化程序设计方法
第2章程序的灵魂——算法
一个程序应包括以下两方面内容:
(1) 对数据的描述。在程序中要指定数据的类型
和数据的组织形式,即
数据结构(data structure)。
(2) 对操作的描述。即操作步骤, 也就是
算法(algorithm)。
数据是操作的对象,操作的目的是对数据进行加工处理,以得到期望的结果。作为程序设计人员,必须认真考虑和设计数据结构和操作步骤(即算法)。因此,著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式
数据结构+ 算法= 程序
实际上,一个程序除了以上两个主要要素之外,还应当采用结构化程序设计方法进行程序设计,并且用某一种计算机语言表示。因此,可以这样表示:
程序= 算法+ 数据结构+ 程序设计方法
+ 语言工具和环境
也就是说,以上4个方面是一个程序设计人员所应具备的知识。在设计一个程序时要综合运用这几方面的知识。在这4个方面中,算法是灵魂,数据结构是加工对象,语言是工具,编程需要采用合适的方法。算法是解决“做什么”和“怎么做”的问题。程序中的操作语句,实际上就是算法的体现。显然, 不了解算法就谈不上程序设计
我们的目的是通过学习本书,能够知道怎样编写一个C程序,并且能够编写出不太复杂的C程序。书中将通过一些实例把以上4个方面的知识结合起来,介绍如何编写一个C程序。
由于算法的重要性,在本章中先介绍有关算法的初步知识,以便为后面各章的学习建立一定的基础。
算法的概念
从事各种工作和活动,都必须事先想好进行的步骤,然后按部就班地进行,才能避免产生错乱。不要认为只有“计算”的问题才有算法。广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”。
对同一个问题,可以有不同的解题方法和步骤。方法有优劣之分。有的方法只需进行很少的步骤,而有些方法则需要较多的步骤。一般说,希望采用简单的和运算步骤少的方法。因此,为了有效地进行解题,不仅需要保证算法正确, 还要考虑算法的质量, 选择合适的算法
我们所关心的当然只限于计算机算法,即计算机能执行的算法。
计算机算法可分为两大类别:数值算法和非数值算法。数值运算的目的是求数值解。非数值运算包括的面十分广泛,最常见的是用于事务管理领域。目前,计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。由于数值运算有现成的模型,可以运用数值分析方法,因此对数值运算的算法研究比较深入,算法比较成熟。对各种数值运算都有比较成熟的算法可供选用。人们常常把这些算法汇编成册(写成程序形式),或者将这些程序存放在磁盘或磁带上,供用户调用。
而非数值运算的种类繁多,要求各异,难以规范化,因此只对一些典型的非数值运算算法(例如排序算法)作比较深入的研究。其他的非数值运算问题,往往需要使用者参考已有的类似算法重新设计解决特定问题的专门算法。
我们将通过一些典型算法的介绍,帮助同学们了解如何设计一个算法,推动大家举一反三。希望同学们通过本章介绍的例子了解怎样提出问题,怎样思考问题,怎样表示一个算法。
简单算法举例
求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为被乘数,i为乘数。用循环算法来求结果。可以将算法改写如下:
S1: 使p=1
S2: 使i=2
S3: 使p×i,乘积仍放在变量p中,可表示为
p×i=>p
S4: 使i的值加1,即i+1 => i
S5: 如果i不大于5,返回重新执行步骤S3以及
其后的步骤S4和S5;否则,算法结束。最
后得到p的值就是5!的值。