算法的案例教学探析

刘晓庆+陈仕鸿

"

"

摘要：算法是计算思维培养的核心内容之一，但目前因各种原因并未在非计算机专业的计算机教学中普及。该文将生活案例引入到算法教学中，这些生活案例分别对应动态规划、并行计算等类别的算法问题，生动形象的展示算法的思维，解决了算法教学需要多门课程基础的问题。

关键词：算法；案例；计算思维；教学

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）21-0134-02

1 引言

随着信息化的进展，计算机已经逐渐成为人们日常生活和工作不可缺少的工具。计算机科学将从前沿高新技术学科变成各专业、各行业均需要普及的基础学科。算法是计算机科学基础内容，也是计算思维培养的核心内容之一。计算机算法的学习，不仅可以让学生体会到计算机的计算能力的强大性，还能够增加学生的解决问题的技能。例如现今新闻、金融、语言等，几乎每个领域都有很多的大数据，挖掘大数据的工作不仅仅属于计算机专业的人员，相关专业的人员也要参与进来，因此掌握计算机算法，对解决类似大数据这类的大规模的、或者很复杂的问题有很大的帮助。

然而算法的学习需要有编程语言、数据结构等课程的学习基础，算法内容生涩难懂，枯燥乏味，非计算机类的专业，特别是文科类专业的计算机教学都避开它。这导致学生无法接触到算法的学习。本文将以生活案例的形式，避开编程语言、数据结构等专业知识，生动形象的介绍算法和算法的思维，以提高学生的学习兴趣，增强学生的计算思维能力。

2 算法的含义

什么是算法呢？简单来说，算法就是解决问题方法。算法处理的内容必然是问题所涉及的数据，算法和数据是程序设计中的核心内容。因此有这一说法：程序=算法+数据结构。

我们生活中也存在许多“算法”。举一例来说，煎一个蛋，厨师首先锅里滴上几滴油，鸡蛋磕破直接把蛋液倒入锅内，用勺子稍稍往鸡蛋上分散撒些食盐，小火等蛋清蛋黄凝固，然后，翻面再煎另一面，这样就做好了煎蛋。这个事例中，鸡蛋、食盐等食材是“数据结构”的话，厨师的烹饪过程便是“算法”。

针对同一问题，很有可能有多种不同的算法。例如，著名的数学家高斯在他小学的时候发生了一件很有名的故事，就是小学老师出于惩罚目的，出了一道算术难题：“计算1+2+3…+100=？”。作为初学算术的学生，高斯的同学都是被难住了，因为他们的解题思路是把这100个数做99次加法运算，需要大量的计算。但是高斯却在几秒后将答案解了出来，他所使用的方法是：对50对构造成和101的数列求和（1+100，2+99，3+98…），同时得到结果：5050。

高斯在小小年纪便能运用巧妙的解题方法，使得他的故事广为流传。人对解决问题与计算机在思维方法上的差异。那么，同样针对这个问题，用计算机程序算法来完成，又应该如何实现呢？

设1～100的累加和放在变量s中，那么让程序重复累加执行：s=s+i，让加数项从1逐步增加到100。这在计算机程序很容易实现。算法的流程和图1所示。

3 排序的应用

排序在生活中是很常见的。比如人员列队时按高矮排列；电影中的票房排行榜；字典或词典里的字词条排序；网上购物时多个推荐商品的前后排序等。

排序对于数据操作来说非常重要。例如：表1中有两组1～10的数字，A组数字是无序的，而B组是有序的。那么随机查找A组中的一个数字，查找方法是从头到尾依次查找，平均要查找5.5次。如果是查找1～10以外的数字，例如-5，则需要查找10次后才能确认它不在表中。而针对B组中有序的数字，我们可以采用折半查找法进行查找，即不是从头到尾依次查找，而是从中间开始查找。中点m=（s+e）/2，s和e分别为数组序号的上限和下限。例如，要查找数字4，一开始，s为1，e为10，m为5，B组中第5个数是5，没有找到4，但是这一次查找，我们可以确定的是，中点的数字是5，我们要找的数字4小于5，所示，它不可能会在数组的后半部分，那么我们可以排队第5～10的数字，只要在前4个数字中查找就可以了。于是第二步，在前4个数中，再次从中间找，s，e，m的值分别为1，4，2。中间的数字是2，也是没有找到，但可以排队第1、2个数字；接着第三步，在剩下的第3、4个数中找，s，e，m的值分别为3，4，3，查到的数字是3，也没找到，剩下只有第4个数了；最后一步，比较第4个数，当然，就找到了我们要查找的数字4。如果要查找1～10以外的数字，则最多4次便可以确定查找失败。因此可以确定，B组有序的数字查找快于A组。

由上述可知，数据的有序对操作的重要性。那么如何对数据进行排序呢？排序的算法有很多，如选择排序法、冒泡法、直接插入排序法、归并排序法、快速排序法、希尔排序法等。

4 穷举法

穷举法也称为枚举算法，其基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能情况逐一验证，直到全部情况验证完毕。若全部情况验证后都不符合题目的全部条件，则本题无解[1]。

生活中也存在许多穷举法的案例。例如，小明是新来的机房管理员，他要管理的是n间机房，有n把钥匙，但他不清楚哪条钥匙对应哪间机房，那么他便每扇门逐条钥匙的去试，直到确认每把钥匙对应的机房。

用穷举法来破解密码，也称暴力破解法，是密码破解技术中最基本的方法。简单来说就是将密码进行逐个推算直到找出真正的密码为止。比如一个四位并且全部由数字组成其密码共有10000种组合，也就是说最多我们会尝试9999次才能找到真正的密码。利用这种方法我们可以运用计算机来进行逐个推算，也就是说用我们破解任何一个密码也都只是一个时间问题。破解过程可以用网上免费的暴力破解软件演示给学生看。

穷举法在求解一个较小规模的问题时，可以根据问题中的约束条件把可能的情况一一列举出来，然后注意尝试从中找到满足约束条件的解。若该问题规模较大，比如破译一个有位数很长，且有多种符号可能的密码，其组合方法可能有万亿种组合。用普通的电脑可能会用掉几年甚至更多的时间去计算，这样长的时间显然是不能接受的。因此规模太大的求解问题穷举法并不适合，应考虑用其他效率更高的算法。