“算法设计过程”的教学设计及反思

    摘 要：“算法设计与分析”是计算机相关专业的核心主干课程。“算法设计过程”是“算法设计与分析”课程中的一个重要知识点。算法设计过程内容的掌握程度和应用水平，对课程后续章节的学习效果有直接影响。本文对“算法设计过程”的教学环节进行设计，阐述多种教学方法在教学过程中的运用形式和技巧。课程教学目标是让学生通过学习掌握算法设计的4个基本步骤，培养学生分析问题、寻找数量关系、通过符号化过程建立数学模型和编写计算机程序的能力。

    关键词：教学设计;算法设计过程;教学环节

    0 引言

    算法是计算的灵魂，在计算科学和工程实践中扮演着重要角色。作为计算机相关专业的核心主干课程，“算法设计与分析”的目的是培养学生的计算思维能力，使学生掌握算法设计的基本方法和算法性能分析的基本技术。[1]该课程要求学生具备较好的数学基础和较强的逻辑思维能力，实现算法时还需要学生具备较强的编程能力。

    “算法设计过程”是“算法设计与分析”课程中一个重要的知识点。算法设计过程是一个抽象思维的过程，是对实际问题本质特征的逻辑概括，从而选择和设计合适的算法框架。算法设计过程这个知识点的掌握程度，对学生泛化该课程所学知识，以解决实际应用和工程问题有重要影响。

    本文将“算法设计过程”这一知识点分解为4个步骤：问题分析、抽象、符号化、计算机程序编写。教学重点是在抽象步骤中找到问题背后隐藏的数量关系。教学设计综合采用多种教学方法。

    1 课堂教学环节设计

    1.1 课程导入

    教师陈述：在前面章节中，我们了解了应用于语音识别的维特比算法，应用于人脸识别的主分量分析算法，还有求最短路径的迪杰斯特拉算法。这些算法改变了我们的生活。教师提问：同学们，你们想设计属于自己的算法吗？学生自答：略。教师陈述：下面我们就随着一对兔子走进算法设计的世界。案例引入：19世纪中叶，澳大利亚一个农场主放养了几只兔子，经过短短60年，兔子数量增长到了100亿只。如何设计一个算法，描述兔子的繁殖过程并计算兔子繁殖的数量呢？

    1.2 问题描述

    教师讲解：草原上最初只有一对小兔子，一年后草原上一共有多少对兔子？围绕这个问题有3个假设条件：一是小兔子一个月以后成为老兔子;二是一对老兔子每月生一对小兔子;三是兔子不死亡。教师陈述：算法设计流程包含相互关联的4个步骤，即问题分析、抽象、符号化和编写计算机程序。

    1.3 算法设计过程第一个步骤：问题分析

    教师讲解：为使分析过程形象具体，利用画图法。第一个月，只有1对小兔子，到了第二个月它们变成了老兔子。到了第三个月有2对兔子，因为老兔子生下了1对小兔子。第四个月，又出生了1对小兔子，兔子总数变成了3对。我们还可以画出第五个月、第六个月、第七个月的兔子（此处使用动画演示）。学生活动：手工画出第四个月兔子的情况。教师设问：如果要画出第100个月以后的兔子，会遇到什么样的难题？学生活动：讨论、回答。教师点评：即使有天安门广场那么大的纸可能也画不下这么多兔子。为此，必须用抽象的方法，找出隐藏在这张图背后的规律，从中挖掘出数量关系。

    1.4 算法设计过程第二个步骤：抽象

    教师讲解：以第五个月的兔子为例进行分析。第五个月的老兔子有3对，等于第四个月兔子总对数。因为第四个月的兔子无论是老的还是小的，到了第五个月都变成了老兔子。得到推论1：本月老兔子对数等于上月兔子的总对数。再看第五个月的小兔子共有2对，而第四个月的老兔子也是2对，这两个数量相等。因为，第四个月的老兔子，到了第五个月每对会生1对小兔子。得到推论2：本月小兔子对数等于上月老兔子的对数。

    教师讲解：本月兔子总对数=本月老兔子对数+本月小兔子对数，这是自然成立的。这个数量关系太平淡无奇了，就像是一杯白开水。下面，我们在其中加入推论1和推论2，看看能发生什么样的化学反应？

    学生活动：让学生思考并回答，利用推论2，本月小兔子的对数等于上月老兔子的对数;在此基础上利用推论1，上月老兔子的对数等于再上一个月兔子的总对数。推论3变成了这样一种形式：本月兔子对数=上月兔子总对数+上上月兔子总对数。

    教师点评：这个数量关系简洁、深刻、漂亮。至此，一杯白开水变成了一杯咖啡。推论3是用自然语言描述的数量关系，如果在此基础上进行符号化，形成数学模型，将有助于计算机程序的编写。

    1.5 算法设计过程第三个步骤：符号化

    教师讲解：第n个月兔子对数表示成F（n）的形式。教师提问：请问如果F（n）表示当本月兔子总对数，那么上月兔子对数和上上月兔子对数怎么表示呢？学生回答：F（n-1）、F（n-2）。教师点评：至此，得到了一个简洁漂亮的数学公式，F（n）=F（n-1）+F（n-2）。根据前面的分析，F（1）=1，F（2）=1，据此可计算出F（3）=2，以此类推，可得F（12）=144。但是要计算F（100），手工计算不太现实，只能交给计算机程序去完成。

    教师讲解：根据前面的分析，我们得到了完整的数学模型，包含3种情况，分别是：n=1时，F（n）=1;n=2时，F（n）=1;n>2时，F（n）=F（n-1）+F（n-2）。在此数学模型基础上编写计算机程序就容易多了。

    1.6 算法设计过程第四个步骤：编写计算机程序

    教师提问：第一个条件用C语言程序怎么表示？学生回答：if（n==1）? return 1。教师提问：第二个条件用C语言程序怎么表示？学生回答：if（n==2）? return 1。教师提问：第三个條件用C语言程序怎么表示？学生回答：if（n==1）? return F（n-1）+F（n-2）。教师点评：这是一个递归形式的程序。下面，我们尝试把这个递归程序改写成非递归的程序。

    教师讲解：本月兔子对数、上月兔子对数和上上月兔子对数分别用变量F3、F2、F1表示。例如，在求第四个月的兔子总对数时需用到第2个月和第3个月兔子总对数，这两个值上一次计算中已经分别保存在F2和F3中，因此要用上一次的F2和F3值对F1和F2的值进行更新。根据这个递推准则，得到用循环语句实现的计算机程序（该部分动画演示和代码演示）。

    1.7 课堂练习

    教师提出问题：围绕一对小兔子一年能繁殖成多少对兔子这个问题，把第二个条件改为：一对老兔子每月生两对小兔子，其他两个条件不变。学生活动：思考、作答并现场编程。

    1.8 课堂小结

    学生活动：让学生回顾本节课内容，锻炼学生总结知识的能力。教师点评：设计算法需要经过相互关联的4个步骤，问题分析是基础（理清概念和条件），抽象是关键（目的是发现规律，也是本次课的重点），符号化是桥梁（方便编写程序），经过桥梁到达的彼岸就是计算机程序（难点）。

    1.9 布置课后思考题

    思考题1：假设草原上最开始只有1对小兔子，问两年后兔子共有多少对？条件：一是每对老兔子1个月生一对小兔子;二是小兔子2个月以后变为老兔子;三是兔子不死亡。用课堂上所讲算法设计过程的4个步骤解决问题，编写递归和非递归形式的程序。该问题从本节课所讲例子修改而来，体现了循序渐进的原则，该思考题可以检测学生对本知识点的推广运用能力。

    思考题2：斐波那契数列在生活中还有哪些应用？

    2 教学反思

    一提到算法，同学们普遍的感觉就是“难”“枯燥”，从而产生排斥心理。如何让算法课讲起来生动活泼，让学生乐于学习，变“要我学”为“我要学”，是笔者一直思考的问题。

    在“算法设计过程”知识点各教学环节中，笔者始终坚持学生主体、能力本位的教学理念，主要从两方面入手。

    首先，巧妙设计教学内容，找准教学切入点。在教学内容的设计上，讲究分层设计、循序渐进，合理地运用多种教学方法，可以将枯燥难懂的理论概念形象化、生动化，利于学生理解。“算法设计过程”的教学过程分为课程导入、算法设计过程4个步骤的理论讲解、计算机程序讲解和演示、课堂练习、归纳小结和课后思考，主要运用了如下7种教学方法：

    第一，形象教学法。整节课内容用一对兔子的故事串起来。设定一个问题：一对兔子一年能繁殖出多少对兔子？然后讲解如何通过设计算法解决这个问题。通过讲故事的方式诠释算法设计过程这一抽象概念，学生听起来不觉得枯燥。

    第二，案例导入法。在新课导入时笔者选择了广泛使用的3个著名算法，利用设问用方式，激发学生对算法设计过程的好奇心和学习兴趣。

    第三，层层递进法。笔者把算法设计过程分成4个步骤。第一个步骤是问题分析，利用图例进行分析，然后指出其中的不足之处，即推广难，从而引入第二个步骤——抽象。抽象可以找到图背后隐藏的规律，解决推广难的问题;抽象步骤得到的是自然语言描述的数量关系，但是自然语言描述的数量关系转换成计算机程序还是不方便，因此引入了第三个步骤——符号化。符号化以后得到了数学模型，以数学模型为桥梁，为了实现智能化运算，避免烦琐的人工计算，引入了第四个步骤——编写计算机程序。这样的讲解过程逻辑清楚，抽丝剥茧，层层递进，引人入胜。

    第四，图例教学法。兔子繁殖规律的分析通过一张图实现，把抽象概念以图示的方式清晰地展示给学生们看，并带他们一起进行兔子繁殖过程的推算。在把计算机递归程序改成非递归形式时也使用了图示的方法。

    第五，比喻教学法。对学生难以理解的概念利用通俗易懂的例子进行比喻。例如：推论3是一个平淡无奇的数量关系，就像是一杯白开水。但是在这杯白开水中加入推论1和推论2，就会起化学反应，白开水变成了一杯咖啡。这样的比喻形象而生动。

    第六，演示教学法。利用计算机程序和动画演示，让学生对知识的印象更深刻，让学生对程序的执行效果有一个直观的认识。

    第七，课堂练习教学法。为了加深学生对所学知识的理解，检验学生的学习效果，笔者改变了原问题3个条件中的一个条件，让学生根据新的假设条件找到新的数量关系并推导新的数模模型，然后写出计算机程序，学生跳一跳能“够得着”。

    其次，巧妙设计提问环节，引导学生主动思考。采用案例驱动教学法，使用兔子繁殖的例子贯穿始终，充分调动学生学习的积极性、主动性与创造性，让学生在学习中积极思考、主动探究、分析问题和寻找答案。在课堂上推进讨论式和启发式教学。随着问题讨论的不断深入，学生逐步掌握了“算法设计过程”这个知识点。课后思考题笔者选择了开放性题目，让学生自主查阅资料，提出解决问题的方案和思路。

    3 結语

    “算法设计与分析”是计算机专业的主干核心课程，算法设计方法和理论是该课程的主要内容。文本围绕“算法设计的过程”这一知识点进行教学设计，综合运用多种教学方法层层递进开展教学。教学环节中，注重突出以学生为中心，调动学生的主观能动性。本文阐述的教学方案在实践中取得了比较好的效果，得到了学生的认可，以后还可以尝试引入移动信息化教学手段，[2]进一步活跃课堂气氛，增加互动环节。[3]

    参考文献：

    [1] 安思，柯春艳.算法设计与分析课程“混合式学习”教学改革[J].福建电脑，2018，34（08）：75+96.

    [2] 刘俊梅，马永刚.移动信息化教学在线性代数教学中的应用——以蓝墨云班课为例[J].科教导刊（下），2019（03）：97-98.

    [3] 牛为华，程晓荣，袁和金，庞春江.基于互动式的“算法设计与分析”课程教学改革[J].数学学习与研究，2019（04）：14.

    作者简介：张明键（1976—），男，江苏扬州人，博士，湖南警察学院教授，研究方向：优化算法，大数据与人工智能。