您的位置: turnitin查重官网> 教学 >> 小学教学 >> 小学数学教学 >> 小学四年级数学教学 >“应用顺序表模拟实现约瑟夫理由”教学设计

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

收藏本文 2022-9-23 点赞:27856 浏览:123752 作者:网友投稿原创标记本站原创

摘要:在大学计算机基础课程“数据结构与算法(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非常大(如上百万、千万)的时候,几乎没有办法在短时间内出结果。如何改善这“应用顺序表模拟实现约瑟夫理由”教学设计相关论文由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。
(编辑:彭远红)

copyright 2003-2022 Copyright©2020 Powered by 网络信息技术有限公司 备案号: 粤2017400971号