程序与算法
4293字,阅读需时15分钟

1、程序与算法

编程,顾名思义就是编写程序。学习之前,要先弄明白什么是程序?解决问题的步骤就是程序吗?算法和程序的关系是什么?本课将一一给出答案。通过本课的学习,你将了解到程序及算法的概念及其关系。

什么是计算机程序?

程序是指完成某些事物的一种既定方式和过程,可以将程序看成是一系列动作的执行过程的描述。在百度百科中,计算机程序被定义为“一组指示计算机执行动作或做出判断的指令,通常用某种程序设计语言编写,运行于某种目标体系结构上。

在生活中,可以见到许多计算机程序实例。下面,我们看一个生活片段:

清晨六点十分,伴随着准时而优美的起床铃声,我迈出宿舍,走进了第一餐厅。餐厅里人很多,没有办法,我只买了两个包子做为我的早餐罢了。随着我的餐卡在打卡机上轻轻掠过,六毛钱便不翼而飞了。当我走到超市的时候,突然感觉只吃包子是不是太单调了,于是在超市里拿了一包早餐奶,但付钱的时候却发现超市的收银机坏掉了,没奈何,我只得忍痛把刚拿到手的早餐奶又放了回去,真郁闷!

在上面的生活片段中,我们能找出几处计算机程序为我们生活服务的痕迹来呢?

●  餐厅打卡机

●  超市收银机

前面关于计算机程序的定义提到了“计算机程序是一组执行动作或做出判断的指令并且运行于某种目标体系结构上”。定义有点晦涩难懂,但是只要我们结合实际运行的程序并稍微略加分析,就能够做到了然于心。

首先考察(餐厅打卡机)

餐厅打卡机一般采用了射频识别技术,“射频识别(RFID)是一种无线通信技术,可以通过无线电讯号识别特定目标并读写相关数据,而无需识别系统与特定目标之间建立机械或者光学接触。”②

打卡机利用射频识别技术将餐卡信息读取到打卡机,由打卡机的处理程序对读取的信息做进一步处理。打卡机中的处理程序就是计算机程序,它需要执行下述动作和指令完成一次打卡操作:

1)  接受输入的餐费金额

2)  读取卡内金额

3)  判断卡内金额是否大于餐费金额

4)  如果卡内金额小于餐费金额,给出余额不足提示

5)  如果卡内金额大于餐费金额,将卡内金额减去餐费金额后,回写到卡内

文字描述其动作或流程不够清晰或理解的话,我们可以用流程图来描述打卡机程序的执行动作或流程:

 01.png

图 1  餐厅打卡机程序流程图

 采用流程图描述打卡机程序的执行动作,是不是更直观和清晰一些。

再来考察(超市收银机)

超市收银机的工作原理类似餐厅打卡机,也是采用射频识别技术读取商品条码,获取商品价格、名称等信息,并由收银机内置的计算机程序对商品价格等信息进行汇总处理,给出所购商品金额等信息。其处理流程要比餐厅打卡机复杂一些,它需要执行下述动作和指令完成一次收费操作:

1) 读取商品条码

2) 获取商品价格、名称等信息并显示到收银机屏幕上

3) 计算所扫商品总金额

4) 等待操作员按键

5) 操作员按下“商品”按键,继续读取商品条码

6) 操作员按下“等金额”或“找零”按键,钱柜自动开启

其流程图描述如下:

 02.png 

图 2  超市收银机程序流程图

从餐厅打卡机和超市收银机的内置的程序可以看出,人们使用计算机,就是要利用计算机程序处理各种不同的问题,为了让计算机能够按照我们的意愿去工作,人们在设计计算机时,为计算机提供了一套指令,其中的每一种指令对应着计算机能执行的一个基本动作,为让计算机完成某项任务而编写的指令序列就称为计算机程序。

2、什么是程序算法?

我们知道,程序是用来解决问题的,是由多个步骤或过程组成的,这些步骤和过程就是解决问题的算法。

同学们都下过象棋吧,图3给出的是《江湖迷局》一书的一个残局棋谱,棋谱给出了每一步棋的走法,按照棋谱规定的步骤行棋,就能破解这个残局,棋谱给出的行棋规则就是算法。

03.png 

图3  棋谱残局

去超市购物时,人们经常会对需要购买的同类商品做价格的比较,例如商品A、商品B、商品C在同样质量的情况下,人们会倾向于比较价格,优先购买价格便宜的商品,这个比较过程是在大脑进行的,比较的过程就是排序算法,从三个数中找出最小的数。

04.png

图4 超市购买货物时进行价格比较

图3的棋谱残局需要走11手,就能破解残局,图4的价格排序也仅需要对3个数进行排序,在大脑比对一下数的大小就完成了。它们都是算法,算法有没有明确的概念和特征呢?

要想弄清楚算法的概念和特征。先看看算法能给人们的生活带来哪些帮助?前面的棋谱残局和价格比对是生活中的算法,可以帮助人们解决生活中的一些问题,让我们变成象棋高手,或者买到最实惠的商品。

如果让计算机执行算法,会给人们带来什么帮助呢?在学习方面,把解方程的步骤输入到计算机,可以帮助人们解方程;在工作方面,把英汉词库及检索算法输入到计算机,可以帮助人们自动进行英汉词语翻译;在生活方面,把游戏规则和算法输入到计算机,可以让人们娱乐等等。计算机有了算法,才有了大脑和灵魂,没有算法的计算机,只能是一台机器。

为了让计算机能够完成前面所说的任务,就需要事先对各类问题进行分析,确定解决问题的具体方法和步骤。再编制好一组让计算机执行的指令,交给计算机,让计算机按人们指定的步骤有效地工作。这些具体的方法和步骤,其实就是一个问题的算法。例如,让计算机帮助我们解方程,就需要把解方程的步骤和方程参数输入到计算机,计算机根据输入的步骤和参数完成方程的求解。

严格来说,计算机程序是为让计算机完成某项任务而编写的指令序列,指令序列就是解决问题的算法。

05.png

图5 算法的概念

 

前面理解了算法的概念,再来看看算法有哪些特征。

算法是由有限多个步骤组成的,它有下述两个基本特征:第一个特征是每个步骤都明确地规定要执行何种操作;第二个特征是每个步骤都可以被人或机器在有限的时间内完成。算法除了上述两个基本特征外,还要具有第三个基本特征:虽然有些步骤可能被反复执行多次,但是在执行有限多次之后,就一定能够得到问题的解答。

06.png 

图6 算法的特征

算法比较抽象,下面讲解一个实际的算法案例,让同学们对算法有个感性认识。对一组无序的数字进行排序,比较经典的排序算法就是冒泡排序。

3、冒泡排序算法

冒泡排序是将一组数字多趟顺序比较,一次比较两个数字,如果他们的顺序错误就把他们交换过来,小数或(大数)逐渐往上冒,当再没有需要交换的数字时,说明该组数已经排序完成。

对下面的一组数用冒泡排序算法,并按照从小到大的顺序排序。

22.png

排序前的一组数,我们称为原始数列,每两个数进行一次比较,称为一轮比较。

07.png

第一轮比较:23与34比较,23小于34,两个数不用交换位置。

08.png


第二轮比较:34与5比较,因为34大于5,因此34和5交换位置。

09.png

10.png

第三轮比较:34与7比较,因为34大于7,因此34与7交换位置。

11.png

12.png


第四轮比较:比较34和56,因为34小于56,两个数不用交换位置。

13.png

在前面的四轮比较中,从数列左侧的第一个数开始,顺序两两比较两个数的大小,如果前面一个数比后面一个数大,就交换两数的位置,直到数列的最后一个数比较完毕。

这四轮比较下来,称为一趟比较。如果在该趟比较中,存在两个数交换位置的情况,就需要进行下一趟比较,直到再没有数字进行交换,算法结束。

因为在第一趟比较中,存在两数的位置交换,因此还需要进行第二趟的比较。

第二趟比较

第二趟比较也是从数列左侧的第一个数开始,顺序两两比较两个数的大小。不过第二趟比较就不需要再比较数列右侧的最后一个数了,因为在第一趟比较的过程中,该数列最大的数已经被交换到数列右侧最后的一个位置了。

14.png

第一轮比较:比较23和5,因为23大于5,因此23和5交换位置。

15.png

16.png

第二轮比较:比较23和7,因为23大于7,因此23和7交换位置。

18.png

18.png


第三轮比较:比较23和24,因为23小于24,两个数不用交换位置。

19.png

至此,第二趟比较完成。最后的一个数56就不用比较了,因为56在第一趟比较中就已经为自己找到了正确的位置。

从第三轮的比较结果来看,排序已经完成,每个数都自己找到了正确的位置。已经不需要再进行第三趟比较了。

4、  算法和程序的关系

算法是解决问题的步骤,在前面也谈到了程序是执行过程的描述,那么,算法和程序是什么关系呢?

先请同学们思考一个计算长方形面积的问题,并给出算法。

第一步,设置num1和num2两个变量,接收用户输入的长度和宽度,并存储到num1和num2两个变量;

第二步,判断num1和num2是否大于0,如果大于0,继续下一个步骤,否则提示用户长度和宽度输入错误,算法结束;

第三步,计算num1和num2的乘积,并将乘积结果存储到result变量;

第四步,显示result变量的值到屏幕。

算法非常简单,四个步骤,如何让计算机执行这个算法呢?

实现算法的伪代码:

Begin(算法开始)
     声明  num1、num2;
     输入  num1、num2;
     IF num1 <=0 || num2 <=0
     {
        Print(“输入的长度和宽度不能小于0”);
       退出程序
     }
     result = num1 * num2;
     Print  result;
End (算法结束)


要让计算机执行算法,就必须要把算法用编程语言编写出来,如Java语言,如实现计算长方形面积算法的伪代码,伪代码是一种算法描述语言,可以很容易地转换为编程语言,如Java、C语言等。可见,程序是算法的实现,算法通过某一种编程语言实现后,就是程序。

5、练习题

1、请列举一些你在生活中经常使用的计算机程序。

2、计算机程序和算法有什么区别?

3、对下面的一组数字用冒泡排序算法进行排序,请用文字详细描述排序过程。

36,29,101,12,33

4、现实问题模拟:《停车场的看门人》   

某大型停车场对于进入该场地的车辆有如下的规定: 

(1)进入该停车场的车辆必须为客运车辆,货运车辆谢绝入内。

(2)如果该车的乘员数量小于等于4人,则收费五元。

(3)如果该车的乘员数量大于4人,则收费八元。

作业要求:请根据该停车场的规定,用文字给出判断进入该场的车辆是否符合规定,应该收费多少的算法。

5、请用文字给出一个计算长方形面积问题的算法。

要求:接受用户输入的长度和宽度,输入的长度和宽度不能为零,如果为零,提示用户重新输入,最后将计算结果显示到显示器上。

读者留言
最新
推荐
阿紫
2020/12/16
习题很容易啊,轻松过关
  • 推荐[0]
  • |
  • 回复
回复评论
喵酱
2020/12/10
练习题有没有答案?
郎宏林回复:
回复日期:2020/12/10

每节课都有作业安排,把练习题写到作业内,然后把作业提交上来,由老师来检查

  • 推荐[0]
  • |
  • 回复
回复评论
孙小伟
2020/12/10
这门课还是不错的,相比python编程基础课,更容易入门。 就是贵了点啊!
  • 推荐[0]
  • |
  • 回复
回复评论
独孤
2020/12/10
写的太好了,一看就懂
  • 推荐[0]
  • |
  • 回复
回复评论
郎宏林
授课老师
授课老师简介
项目经理,系统分析和架构师,从事多年中文信息处理技术。熟悉项目管理、擅长项目需求分析和设计、精通Java、C#、Python等编程语言。