世界上有两片相同的雪花吗 ——哈希查找教学设计
  • 来源:科普时报
  • 作者:章 英
  • 2020-11-28 11:30



    1898年,一位叫做威尔逊的摄影师用木制相机拍摄了5000余幅雪花照片,然后他感慨:没有两片雪花是相同的。21世纪美国自然摄影师麦卡锡看到这个故事,决心一定要发现两片相同的雪花。几年过去了,他拍摄了数万张雪花照片,依然没有找到两片相同的雪花。

    北京大学OJ网站上有一道以查找是否存在两片相同的雪花为背景的ACM竞赛题。题目描述雪花以6个棱长值及不同的排列顺序表征,要求在4秒之内查找10万片雪花中是否存在相同的两片。例如,棱长分别为1、2、3、4、5、6的雪花和棱长分别为4、3、2、1、6、5的雪花就是两片相同的雪花。

    教学过程中教师根据bloom认知分类层次模型,从高阶思维认知出发,确定教学的认知目标是针对大数据的建模分析、搜索算法分析,时间复杂度的评估;技能目标是应用哈希查找技术进行大数据搜索,并解决科研问题;情感目标是培养学生的爱国热情、科学精神。

    首先,教师会引导学生分析雪花的特点,用一个表征6个棱长的数组对每片雪花进行建模。10万片雪花就需要用10万个独立的数组建模。

    然后,让学生运用已学过的三种查找技术:顺序查找、二分查找、二叉查找,讨论解决雪花搜索问题的可行性及优缺点。最后得出结论,针对本问题中的大数据,这三种方法都不能在4秒之内完成。

    接下来,在参与式学习中引导学生分组讨论基于哈希函数的大数据建模问题,以及基于哈希查找算法的雪花搜索问题。以这5片不同的雪花为例,按照哈希函数分别计算每片雪花的哈希值h,并将哈希值相同的雪花链到同一个单链表上,从而将10万片独立的雪花数组建模成一个哈希数组。回到最开始提出的问题,假设待搜索的雪花的棱长是123456,如何在哈希数组中,搜索有没有和他相同的雪花呢?有的同学会认为,直接到哈希值等于91的链表里去找就可以了。正确与否?此时教师引导学生去分析,单片雪花不止一种存储结构,按照顺时针方向旋转,可以得到6种不同的存储结构。按照逆时针方向,又可以得到另外6种。正确的搜索就是到链表中查找这12种雪花是否存在。10万片雪花就需要将上述过程循环10万次。

    经过现场测试,4秒可以得出最终结论。那么,相比于以前三种查找技术,为什么哈希查找的运行效率如此之高呢?教师引导学生分析算法时间复杂度,得出哈希查找是适合于大数据搜索的技术。

    最后,设计一个类似的学科延伸问题:在1秒之内,找出100万个短的DNA序列里,出现次数最多的DNA序列。通过本堂课程哈希查找的学习,学生可以轻松解决该问题。

    在此次哈希查找的教学过程中,围绕教学目标的设计与达成这个关键问题,教师引导学生逐步从数据建模的分析,到算法过程的实现,并运用所学知识,解决学科延伸的科研问题,从而完成认知、技能、情感三大教学目标。

    世界上是没有两片相同的雪花的,每片雪花在穿越大气层时经历不同的动荡环境,每一次扭动、转弯和下落都赋予它独特的对称图案。而加州理工学院的物理学家肯尼思·G·利布雷希特花了20年时间,找到一个方法能在自己的实验室里制作“同卵双生”雪花。他说,“我们没有违反任何物理定律。我们只是发现了一个漏洞。”

    (作者系华中农业大学信息学院计算机科学系副教授。本文相关内容是湖北省教改项目2018200的成果。)


  • TEL:010-58884104
  • E-Mail:kepu@kepu.gov.cn
  • 如果您有任何意见或建议,请联系我们!