javascript循环链表之约瑟夫环的实现方法_网络技术

javascript循环链表之约瑟夫环的实现方法

发布时间 - 2026-01-10 22:33:52 点击率：次

前言

传说在公元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 + "&nbsp;");
 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约瑟夫环 # 一个报数游戏js版(约瑟夫环问题) # JavaScript三种方法解决约瑟夫环问题的方法 # 链表 # 约瑟夫 # 中有 # 犹太 # 站在 # 多少个 # 出了 # 这件事 # 递归 # 解决这个问题 # 围成 # 的是 # 数到 # 是个 # 有个 # 罗马 # 只需 # 上有 # 这个问题 # 很容易

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：关于网站服务器托管费用，你必须知道的几个关键因素！

下一篇：利用Webman实现网站的响应式图片显示

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：关于网站服务器托管费用，你必须知道的几个关键因素！

下一篇：利用Webman实现网站的响应式图片显示