java使用链表实现约瑟夫环
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。求出出队序列。
采用链表实现，结点数据就是编号。
package com.dm.test;
public class Test2
{
public static void main(String[] args)
{
//头结点
Node root = new Node(1);
int[] order = build(root,9,5);
for(int i =0;i<order.length;i++)
{
System.out.print(order[i]+" ");
}
}
//将约瑟夫环建成一个链表
public static int[] build(Node root,int n, int m)
{
Node current = root;
for(int i = 2; i<=n; i++)
{
Node node = new Node(i);
current.next = node;
current = node;
}
current.next = root;
int[] order = come(root,n,m);
return order;
}
//出队列
//结束条件：只有一个结点时，这个结点的next是它自身
//将出来的数，放在一个数组中，遍历数组就是出队序列
public static int[] come(Node root,int n, int m)
{
int[] order = new int[n];
int j = 0;
Node p = root;
while(p.next!=p)
{
int i = 1;
while(i<m-1)
{
p=p.next;
i++;
}
if(i==m-1)
{
order[j]=p.next.data;
j++;
p.next = p.next.next;
p=p.next;
}
}
order[j]=p.data;
return order;
}
}
class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
next= null;
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
代码详解Java猴子选王问题（约瑟夫环）
关于约瑟夫环的基本知识: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止.约瑟夫和他的朋友并不想自杀,于是约瑟夫想到了一个计策,他们两个同样参数到自杀方案中,但是最后却躲过了自杀.
-
java 实现约瑟夫环的实例代码
复制代码 代码如下: import java.io.BufferedInputStream;import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Josephus { private static class Node{ int No; Node next; public Node(int No){ this
-
Java简单实现约瑟夫环算法示例
本文实例讲述了Java简单实现约瑟夫环算法.分享给大家供大家参考,具体如下: 1.算法背景: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数 仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止. 约瑟夫和他的朋友并不想自杀,于是约
-
java使用链表实现约瑟夫环
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围.从编号为k的人开始报数,数到m的那个人出列:他的下一个人又从1开始报数,数到m的那个人又出列:依此规律重复下去,直到圆桌周围的人全部出列.求出出队序列. 采用链表实现,结点数据就是编号. package com.dm.test; public class Test2 { public static void main(String[] args) { //头结点 Node root = new Nod
-
C语言用循环单链表实现约瑟夫环
用循环单链表实现约瑟夫环(c语言),供大家参考,具体内容如下 源代码如下,采用Dev编译通过,成功运行,默认数到三出局. 主函数: main.c文件 #include <stdio.h> #include "head.h" #include "1.h" int main() { Linklist L; int n; printf("请输入约瑟夫环中的人数:"); scanf("%d",&n); Create
-
Java使用单链表实现约瑟夫环
本文实例为大家分享了Java使用单链表实现约瑟夫环的具体代码,供大家参考,具体内容如下 构建一个单向的环形链表思路 1.先创建第一个节点, 让first指向该节点, 并形成环形 2.后面当我们每创建一个新的节点, 就把该节点加入到已有的环形链表中即可. 遍历环形链表思路 1.先让一个辅助指针(变量)curBoy, 指向first节点 2.然后通过一个while循环遍历该环形链表即可 curBoy.next == first 结束 生成小孩出圈顺序的思路 1.根据用户的输入, 生成一个小孩出圈的顺
-
Java用单向环形链表来解决约瑟夫环Josepfu问题
简单介绍 如果把单链表的最后一个节点的指针指向链表头部,而不是指向NULL,那么就构成了一个单向循环链表,通俗讲就是让尾节点指向头结点. 单向环形链表应用场景:Josephu(约瑟夫.约瑟夫环)问题: 设编号为1, 2, - n的n个人围坐一圈,约定编号为k (1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列. 代码实现 节点类 //节点类 class JNode { private
-
C数据结构循环链表实现约瑟夫环
C数据结构循环链表实现约瑟夫环 本文代码均在turbo C 2.0 的环境下运行通过,并得到正确结果,本程序为用循环链表实现约瑟夫环,即有m个人站成一个圆环,从某人(队列第一个)开始报数,约定从某数开始的第n个人出列,他的下一个再从一开始报,然再一个报道n的人出列,本程序结果为人员出列顺序, #include<stdio.h> #include<conio.h> #define OK 1 #define NULL 0 typedef int status; typedef int
-
C++ 中循环链表和约瑟夫环
循环链表和约瑟夫环 循环链表的实现 单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表.当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head. 代码实现分为四部分: 初始化 插入 删除 定位寻找 代码实现: void ListInit(Node *pNode){ int item; Node *temp,*target; cout<<"输入0完成初始化"&
-
Java输出链表倒数第k个节点
问题描述 输入一个链表,输出该链表中倒数第k个结点.(尾结点是倒数第一个) 结点定义如下: public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } 思路1: 先遍历链表,计算其长度length; 然后计算出倒数第k个结点就是正数第length - k + 1. 最后再遍历链表,找到所求结点 时间复杂度O(2n),需要遍历两次链表 代码如下: public List
-
java 中链表的定义与使用方法
java 中链表的定义与使用方法 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; 实例代码: package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new my
-
Java 数据结构链表操作实现代码
链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表.循环链表.双向链表,下面将逐一介绍.链表在数据结构中是基础,也是重要的知识点,这里讲下Java 中链表的实现, JAVA 链表操作:单链表和双链表 主要讲述几点: 一.链表的简介 二.链表实现原理和必要性 三.单链表示例 四.双链表示例 一.链表的简介 链表是一种比较常用的数据结构,链表虽然保存比较复杂,但是在查询时候比较便捷,在多种计算机语言都相应的应用,链表有多种类别,文章针对单链表和双链表进行分析.链表中数据就像被一个链
-
Java单链表的实现代码
下面是小编给大家分享的一个使用java写单链表,有问题欢迎给我留言哦. 首先定义一个Node类 public class Node { protected Node next; //指针域 public int data;//数据域 public Node( int data) { this. data = data; } //显示此节点 public void display() { System. out.print( data + " "); } } 接下来定义一个单链表,并实现