本科系列课程参见:《》
约瑟夫(Joeph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数报m的人出列,将他的密码作为新的m值从他在顺时针方向上的下一个囚开始重新从1报数,如此下去直至所有人全部出列为止。试设计一个程序求出出列顺序
利用单向循环链表存储结构模拟此过程,按照絀列的顺序印出各人的编号
游戏实现的关键是游戏信息的储存包括玩家座位信息,玩家所报数信息以及密码信息我们通过自定义单向循环链表Joeph_list存储结构来实现游戏过程的模拟。链表以结点连接结点Node存储的信息包括每个人手中的密码、每个人的位置以及下一个结点在计算机中的存储位置,及指向下一个结点的指针值得注意的是,信息“每个人的位置”是必不可少的因为他不等同于结点在链表中的位置——但一个玩家被移除之后,链表后的元素位置会“前进”而我们需要的玩家的位置始终是不变的。
玩家的报数我们通过循环中计數器的递增实现,当顺序递增到链表中最后一个结点而循环仍没有结束时,我们继续从第一个元素开始递增——及相当于最后一个玩家仍没有报数到m我们就从第一个玩家重头开始报数直到计数器累加到m,则发现我们要移除的结点记录并输出移出结点的信息,继续游戏直到链表中元素被清空,程序结束
算法的关键是将实际游戏场景抽象到链表中的元素的查找和移除上,要掌握清楚哪些数据代表哪些信息并熟悉程序运行中各种判断的流程。
在这个游戏中假定每个人都是一个节点,这样有利于程序的理解
Joeph_list类:储存游戏中玩家座位、密码等信息的数据结构
List类:以链表的方式存储图片等数据结构
1、游戏开始,初始m为6从第一个玩家开始自动报数,报到数的人出列
2、以絀列人手中的密码为密码(不大于6)继续游戏
3、直到所有人出列游戏结束
(*点击图片可跳转到Youku视频)