“应用顺序表模拟实现约瑟夫问题”教学设计

摘要：在大学计算机基础课程“数据结构与算法（B）”教学中，案例应用有助于学生融会贯通数据的逻辑结构、存储结构和相关算法。文章通过“应用顺序表模拟实现约瑟夫问题”这一案例，讲述在解决约瑟夫问题过程中，应用顺序表的原因、过程和关键算法，并对主要教学内容的讲授时间和注意事项等给出建议。

关键词：数据结构；微课；顺序表；约瑟夫问题；教学设计

1.课程定位

“数据结构与算法（B）”是北京大学面向非计算机专业学生、培养计算思维与编程能力的一门本科生主干基础课，目前在北京大学的所有理科院系开设。课程要求掌握的常用数据结构包括顺序表、链表、字符串、栈、队列、二叉树、Huffmn树、树、堆以及图。针对每一种常用数据结构，我们要求学生：

（1）从逻辑结构、一组基本运算和存储（实现）3个方面去理解、掌握数据结构；

（2）对算法的时间和空间复杂性有一定的分析能力；

（3）针对简单的应用问题，应能选择合适的数据结构及设计有效的算法解决。

课程中第一个讲授的数据结构是顺序表，见图1，它也是在软件开发中应用最为广泛的一种数据结构。其讲授难点是如何让学生用学到的顺序表基本知识（相关算法和存储实现）编程解决与线性表有关的应用问题。约瑟夫（Josephus）问题是一个非常经典的计算问题。讲授如何使用顺序表编程实现约瑟夫问题，有助于学生进一步了解顺序表的基本知识点和特点，了解如何应用顺序表进行有效的算法设计。

2.教学目标

讲授内容围绕一个编程案例，帮助学生：

（1）复习并掌握顺序表的存储实现方法以及顺序表上的基本运算；

（2）了解约瑟夫问题的背景和由来，理解计算机编程实践过程中需求分析的作用；

（3）能应用顺序表编程实现约瑟夫问题以及类似问题；

（4）遇到问题能有意识应用数据结构与算法中所学知识。

3.教学内容与知识点

约瑟夫问题是以弗拉维奥·约瑟夫斯（FlaVius Josephus）命名的，他是一世纪的一名犹太历史学家。在Josephus留下的日记中，描述了这样一个故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁死也不要被敌人抓到，于是决定了一个自杀方式：41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

Josephus把他的存活归因于运气或天意，但实际上对于任意给定的n（n个人）、s（第s个人开始报数）和m（第m个人出列），可以通过一个计算模型推断出所有人员自杀的序列。微课程讲授了解决约瑟夫问题的计算模型，并给出基于顺序表来实现约瑟夫问题的算法和相关程序代码。其中，所有参与游戏的人员可以通过顺序表进行存储和表示。图2给出了一个基于顺序表的数据表示实例。

与约瑟夫问题类似的还有17世纪法国数学家加斯帕在《数目的游戏问题》一文中讲述的一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难。于是他们想了一个办法：30个人围成一圆圈，从第1个人开始依次报数，每数到第9个人就将他扔人大海，如此循环进行直到仅余l 5个人为止。问怎样排法，才能使每次投入大海的都是非教徒？综合这个问题，可以提示学生如何进行需求分析和问题建模，锻炼学生的思维能力。

在讲授中，教师应注意将问题进行简化和扩展以提供课堂练习和课后练习，并留下课堂思考问题。如Josephus问题基于顺序表实现的算法复杂性较大：要模拟整个游戏过程，时间复杂度大概在O（n×m）。当n、m非常大（如上百万、千万）的时候，几乎没有办法在短时间内出结果。如何改进这个算法？教师可以启发学生打破常规，运用数学策略。

课程的主要教学内容和知识点见表1，教师还应注意到不同知识点上时间的划分以增强学生的掌握能力。同时，基于课堂规模的大小（学生人数的不同），教师还需注意适当调整教授内容的时长。总体来说，课堂规模越大，内容与知识点教授的时间应适当延长，课堂与课后练习的讲解也要分类并进行针对性分析；反之，讲授的时间则可以适当缩短。

4.课程特色

课程要求学生在熟悉顺序表存储结构以及基本运算的基础上，能够针对具体应用问题的要求和性质，设计出相应的有效算法解决实际问题。其课程特色包括：

（1）重视清楚理解和深入掌握基本概念、基本原理和基本方法等三个基本内容。

（2）多方位教学。从回顾、问题介绍、问题实践、实例、类似问题、课堂练习、课后练习、思考与总结等多方面逐步进行知识点强化。

（3）立体化教学。提供讲义、程序、在线平台、参考资料等多种学习资源，扩展学习内容。

5.课程学习资源

（1）《算法与数据结构——C语言描述（第2版）》（张乃孝著，高等教育出版社2006年出版）。

（2）《数据结构与算法》（张铭等著，高等教育出版社2008年出版）。

（3）《C++编程思想》（Bruce Eckel著，刘宗田等译，机械工业出版社2000年出版）。

（4）Introduction to Algorithms（Thomas H.Cormen等著，MIT Press出版，高等教育出版社影印2002年）。

（5）在线平台：http：///。

（6）在线练习：http：///2013 hxtest02/E/。

（7）在线练习：http：///practice/1012。