前言
传说在公元1 世纪的犹太战争中,犹太历史学家弗拉维奥·约瑟夫斯和他的40 个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏,于是商量出了一个自杀方案。他们围成一个圈,从一个人开始,数到第三个人时将第三个人杀死,然后再数,直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏,他们快速地计算出了两个位置,站在那里得以幸存。写一段程序将n 个人围成一圈,并且第m个人会被杀掉,计算一圈人中哪两个人最后会存活。使用循环链表解决该问题。
看到这个问题首先想到的是要用到循环链表,还有就是要计算链表中有多少个元素,这两点很重要。再有就是找到当前节点和在链表中向前移动m个节点。下面一一分析:循环链表很容易实现,就是初始化的时候使链表的头节点的下一个指向它自己,这样初始化一个空节点,注意链表的头不是节点。写法如下:this.head.next = this.head;
计算链表中有多少个元素也很简单,只需要找到头节点,然后往下走直到再次回到头结点
代码如下:
var node = this.head; var i = 0; while (!(node.next.element == "head")){ node = node.next; i++; } return i;
在初始化链表的时候我们定义一个当前节点,将它赋值为头节点this.currentNode = this.head;
,这样在移动节点的时候就可以用它指向下一个节点。向前移动节点的时候有个地方需要注意,如果当前移动到头节点上需要再向前移动一个节点this.currentNode.next.next
。
代码如下:
while (n>0){ if(this.currentNode.next.element == "head"){ this.currentNode = this.currentNode.next.next; }else{ this.currentNode = this.currentNode.next; } n--; }
代码实现
/** * 使用循环链表实现解决约瑟夫环问题 * */ //链表节点 function Node(element){ this.element = element; this.next = null; } //定义链表类 function LList(){ this.head = new Node("head"); this.head.next = this.head; this.find = find; this.insert = insert; this.findPrevious = findPrevious; this.remove = remove; this.currentNode = this.head; //从链表当前节点向前移动n个节点 this.advance = advance; //当前链表中有多少个元素 this.count = count; this.display = display; } //查找节点 function find(item){ var currNode = this.head; while (currNode.element != item){ currNode = currNode.next; } return currNode; } //插入新节点 function insert(newElement, item){ var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; current.next = newNode; } //查找当前节点的上一个节点 function findPrevious(item){ var currNode = this.head; while (!(currNode.next == null) && (currNode.next.element != item)){ currNode = currNode.next; } return currNode; } //移除当前节点 function remove(item){ var prevNode = this.findPrevious(item); if(!(prevNode.next == null)){ prevNode.next = prevNode.next.next; } } //向前移动n个节点 function advance(n){ while (n>0){ if(this.currentNode.next.element == "head"){ this.currentNode = this.currentNode.next.next; }else{ this.currentNode = this.currentNode.next; } n--; } } //当前链表中有多少个元素 function count(){ var node = this.head; var i = 0; while (!(node.next.element == "head")){ node = node.next; i++; } return i; } //输出所有节点 function display(){ var currNode = this.head; while (!(currNode.next == null) && !(currNode.next.element == "head")){ document.write(currNode.next.element + " "); currNode = currNode.next; } } var person = new LList(); person.insert('1','head'); person.insert('2', '1'); person.insert('3', '2'); person.insert('4' , '3'); person.insert('5' , '4'); person.insert('6' , '5'); person.insert('7' , '6'); person.insert('8' , '7'); person.insert('9' , '8'); person.insert('10' , '9'); person.display(); document.write('<br>'); var n = 3; while (person.count() > 2){ person.advance(n); person.remove(person.currentNode.element); person.display(); document.write('<br>'); }
这里我们假设有10个人,每次数到第三个人的时候这个人自杀,最后输出的结果如下:
最后结果是约瑟夫和他的同伴一个站在队伍的第4个,一个站在队伍的第10个,最后只剩下他们两个人。不知道历史上有没有这件事,如果真的有这件事,在这么短的时间内解决这个问题,约瑟夫真他么是个天才,不知道当时他有没有用指针来解决这个问题,还是用普通的数组递归解决。
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。
约瑟夫环,js约瑟夫环
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
《魔兽世界》大逃杀!60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容,新游玩模式《强袭风暴》即将于3月21 日在亚服上线,届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕,并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时,他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中,玩家将会进入一个全新的海盗主题大逃杀式限时活动,其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场,作为一个独立于主游戏之外的活动,玩家可以用大逃杀的风格来体验《魔兽世界》,不分职业、不分装备(除了你在赛局中捡到的),光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式,玩家在加入海盗主题的预赛大厅区域前,可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹,《巨龙崛起》和《魔兽世界:巫妖王之怒 经典版》的玩家都可以获得奖励。