算法是程序的灵魂,只有掌握了算法,才能轻松地驾驭程序开发。软件开发工作不是按部就班,而是选择一种最合理的算法去实现项目功能。算法能够引导开发者在面对一个项目功能时用什么思路去实现,有了这个思路后,编程工作只需要遭循这个思路去实现即可。本章将详细讲解计算机算法的基础知识,为读者步入后面的学习打下基础。
1.1 算法的基础
自然界中的很多事物并不是独立存在的,而是和许多其他事物有着千丝万缕的联系。就拿算法和编程来说,两者之间就有着必然的联系。在编程界有一个不成文的原则,要想学好编程,就必须学好算法。要想获悉这一说法的原因,先看下面对两者的定义。
算法是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对符合一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。
编程是让计算机为解决某个问题而使用某种程序设计语言编写程序代码,并最终得到结果的过程。为了使计算机能够理解人的意图,人类就必须将需要解决的问题的思路、方法和手段通过计算机能够理解的形式"告诉"计算机,使计算机能够根据人的指令一步一步去工作,完成某种特定的任务。编程的目的是实现人和计算机之间的交流,整个交流过程就是编程。
在上述对编程的定义中,核心内容是思路、方法和手段等,这都需要用算法来实现。由此可见,编程的核心是算法,只要算法确定了,后面的编程工作只是实现算法的一个形式而已。
1.1.1算法的特征
在1950年,算法(Algorithm )一词经常同欧几里得算法联系在一起。这个算法就是在欧几里得的《几何原本》中所阐述的求两个数的最大公约数的过程,即辗转相除法。从此以后,算法这一叫法一直沿用至今。
随着时间的推移,算法这门学科得到了长足的发展,算法应该具有如下5个重要的特征。
有穷性：保证执行有限步骤之后结束。
确切性:每一步骤都有确切的定义。
输入:每个算法有零个或多个输入,以刻画运算对象的初始情况。所谓零个输入,是指算法本身舍弃了初始条件。
输出:每个算法有一个或多个输出,显示对输入数据加工后的结果,没有输出的算法是室无意义的。
可行性:原则上算法能够精确地运行,进行有限次运算后即可完成一种运算。
1.1.2 何为算法
为了理解什么是算法,先看一道有趣的智力题。"烧水泡茶"有如下5道工序: 1、烧开水, 2、洗茶壶, 3、洗茶杯, 4、拿茶叶,5、泡茶。烧开水、洗茶壶、洗茶杯、拿茶叶是泡茶的前提。其中,烧开水需要15min ,洗茶壶需要2min ,洗茶杯需要1min ,拿茶叶需要1min ,泡茶需要1min.下面是"烧水泡茶"的两种方法。
方法1的步骤如下。
第1步:烧水。
第2步:水烧开后,洗刷茶具,拿茶叶。
第3步:沏茶。
方法2的步骤如下。
第1步：烧水。
第2步:烧水过程中,洗刷茶具,拿茶叶。
第3步:水烧开后沏茶。
习题:比较这两种方法有何不同,并分析哪种方法更优。
上述两种方法都能最终实现“烧水泡茶的功能,每种方法的3个步骤就是一种算法。算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算法。
1.2计算机中的算法
众所周知,做任何事情都需要一定的步骤。计算机虽然功能强大,能够帮助人们解决很多问题,但是计算机在解决问题时,也需要遵循一定的步骤。在编写程序实现某个项目功能时,也需要遭循一定的算法。在本节的内容中,将一起探寻算法在计算机中的地位,探索算法在计算机中的基本应用知识。
1.2.1认识计算机中的算法
计算机中的算法可分为如下两大类。
数值运算算法:求解数值。
非数值运算算法:事务管理领域。
假设存在如下运算: 1x2x3x4x5,为了计算上述运算结果,最普通的做法是按照如下步骤进行计算。
第1步:先计算1乘以2,得到结果2。
第2步:将步骤1得到的乘积2乘以3,计算得到结果6。
第3步:将6再乘以4,计算得24。
第4步:将24再乘以5,计算得120。
最终计算结果是120,上述第1步到第4步的计算过程就是一个算法。如果想用编程的方式来解决上述运算,通常会使用如下算法来实现。
第1步:假设定义t=1。
第2步：令i=2。
第3步:把x的乘积仍然放在变量中,可表示为txi——t。
第4步:把的值加1,即i+1——i。
第5步:如果i≤5,返回重新执行步骤3以及其后的步骤4和步骤5 ;否则,算法结束。
由此可见,上述算法方式就是数学中的"n,公式。既然有了公式,在具体编程的时候,只需要使用这个公式就可以解决上述运算问题。
再看下面的一个数学应用问题。
假设有80个学生,要求打印输出成绩在60分以上的学生。
在此用n表示学生学号,用n表示第个学生的学号;用cheng表示学生成绩,用chengi表示第i个学生的成绩。根据题目要求,可以写出如下算法。
第1步: 1——i。
第2步:如果chengi≥60,则输出ni和chengi,否则不输出。
第3步: i+1——i。
第4步:如果i≤80,返回步骤2 ;否则,结束。
由此可见,算法在计算机中的地位十分重要。所以在面对一个项目应用时,一定不要立即编写程序,而是要仔细思考解决这个问题的算法是什么。想出算法之后,以这个算法为指导思想来编程。
1.2.2为什么说算法是程序的灵魂
算法是计算机处理信息的基础,因为计算机程序本质上就是算法,告诉计算机确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。通常,当算法在处理信息时,数据会从输入设备读取,写入输出设备,也可能保存起来供以后使用。
著名计算机科学家沃思提出了下面的公式。
数据结构+算法=程序
实际上,一个程序应当采用结构化程序设计方法进行程序设计,并且用某种计算机语言来表示。因此,可以用下面的公式表示。
程序=算法+数据结构+程序设计方法+语言和环境
上述公式中的4个方面是一种程序设计语言所应具备的知识。在这4个方面中,算法是灵魂,数据结构是加工对象,语言是工具,编程需要采用合适的方法。其中,算法是用来解决“做什么"和怎么做"的问题。实际上程序中的操作语句就是算法的体现,所以说,不了解算法就谈不上程序设计。数据是操作对象,对操作的描述便是操作步骤,操作的目的是对数据进行加工处理以得到期望的结果。举个通俗点的例子,厨师做菜肴,需要有菜谱。菜谱上一般应包括: 1、配料(数据) , 2、操作步骤(算法)。这样,面对同一原料可以加工出不同风味的菜肴。
本文节选自《Python算法详解》
全书共13章，基于Python分别讲解了算法是程序的灵魂，数据结构，常用的算法思想，线性表、队列和栈，树，图，查找算法，内部排序算法，经典的数据结构问题，解决数学问题，经典算法问题，解决图像问题，游戏和算法等内容。全书内容以“技术解惑”贯穿全书，引领读者全面掌握算法的核心技术。
