本站原创
摘要：在大学计算机基础课程“数据结构与算法（B）”教学中，案例应用有助于学生融会贯通数据的逻辑结构、存储结构和相关算法。文章通过“应用顺序表模拟实现约瑟夫理由”这一案例，讲述在解决约瑟夫理由过程中，应用顺序表的理由、过程和关键算法，并对主要教学内容的讲授时间和注意事项等给出倡议。
关键词：数据结构；微课；顺序表；约瑟夫理由；教学设计
（1）从逻辑结构、一组基本运算和存储（实现）3个方面去理解、掌握数据结构；
（2）对算法的时间和空间复杂性有一定的分析能力；
（3）针对简单的应用理由，应能选择合适的数据结构及设计有效的算法解决。
课程中第一个讲授的数据结构是顺序表，见图1，它也是在软件开发中应用最为广泛的一种数据结构。其讲授难点是如何让学生用学到的顺序表基本知识（相关算法和存储实现）编程解决与线性表有关的应用理由。约瑟夫（Josephus）理由是一个非常经典的计算理由。讲授如何使用顺序表编程实现约瑟夫理由，有助于学生进一步了解顺序表的基本知识点和特点，了解如何应用顺序表进行有效的算法设计。
（1）复习并掌握顺序表的存储实现策略以及顺序表上的基本运算；
（2）了解约瑟夫理由的背景和由来，理解计算机编程实践过程中需求分析的作用；
（3）能应用顺序表编程实现约瑟夫理由以及类似理由；
（4）遇到理由能有意识应用数据结构与算法中所学知识。
Josephus把他的存活归因于运气或天意，但实际上对于任意给定的n（n个人）、s（第s个人开始报数）和m（第m个人出列），可以通过一个计算模型推断出所有人员的序列。微课程讲授了解决约瑟夫理由的计算模型，并给出基于顺序表来实现约瑟夫理由的算法和相关程序代码。其中，所有参与游戏的人员可以通过顺序表进行存储和表示。图2给出了一个基于顺序表的数据表示实例。
与约瑟夫理由类似的还有17世纪法国数学家加斯帕在《数目的游戏理由》一文中讲述的一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难。于是他们想了一个办法：30个人围成一圆圈，从第1个人开始依次报数，每数到第9个人就将他扔人大海，如此循环进行直到仅余l 5个人为止。问怎样排法，才能使每次投入大海的都是非教徒？综合这个理由，可以提示学生如何进行需求分析和理由建模，锻炼学生的思维能力。
在讲授中，教师应注意将理由进行简化和扩展以提供课堂练习和课后练习，并留下课堂深思理由。如Josephus理由基于顺序表实现的算法复杂性较大：要模拟整个游戏过程，时间复杂度大概在O（n×m）。当n、m非常大（如上百万、千万）的时候，几乎没有办法在短时间内出结果。如何改善这“应用顺序表模拟实现约瑟夫理由”教学设计相关论文由www.udooo.com收集个算法？教师可以启发学生打破常规，运用数学策略。
课程的主要教学内容和知识点见表1，教师还应注意到不同知识点上时间的划分以增强学生的掌握能力。同时，基于课堂规模的大小（学生人数的不同），教师还需注意适当调整教授内容的时长。总体来说，课堂规模越大，内容与知识点教授的时间应适当延长，课堂与课后练习的讲解也要分类并进行针对性分析；反之，讲授的时间则可以适当缩短。
（1）重视清楚理解和深入掌握基本概念、基本原理和基本策略等三个基本内容。
（2）多方位教学。从回顾、理由介绍、理由实践、实例、类似理由、课堂练习、课后练习、深思与总结等多方面逐步进行知识点强化。
（3）立体化教学。提供讲义、程序、在线平台、参考资料等多种学习资源，扩展学习内容。
（2）《数据结构与算法》（张铭等著，高等教育出版社2008年出版）。
（3）《C++编程思想》（Bruce Eckel著，刘宗田等译，机械工业出版社2000年出版）。
（4）Introduction to Algorithms（Thomas H.Cormen等著，MIT Press出版，高等教育出版社影印2002年）。
（5）在线平台：http：//hxsg.openjudge.cn/。
（6）在线练习：http：//hxsijg.openjudge.cn/2013 hxtest02/E/。
（7）在线练习：http：//poj.grids.cn/practice/1012。
（编辑：彭远红）
关键词：数据结构；微课；顺序表；约瑟夫理由；教学设计
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非常大（如上百万、千万）的时候，几乎没有办法在短时间内出结果。如何改善这“应用顺序表模拟实现约瑟夫理由”教学设计相关论文由www.udooo.com收集个算法？教师可以启发学生打破常规，运用数学策略。
课程的主要教学内容和知识点见表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：//hxsg.openjudge.cn/。
（6）在线练习：http：//hxsijg.openjudge.cn/2013 hxtest02/E/。
（7）在线练习：http：//poj.grids.cn/practice/1012。
（编辑：彭远红）