约瑟夫环(Josephus)问题:古代某法官要判决n个犯人的死刑,他有一条荒唐的法律,将犯人站成一个圆圈,从第s个人开始数起,每数到第d个犯人,就拉出来处决,然后再数d个,数到的人再处决……直到剩下的最后一个可赦免.
结点类:OneLinkNode:
package com;
/**
* 结点类
* @author zdw
*
*/
public class OneLinkNode
{
public int data;
public OneLinkNode next;
public OneLinkNode(int k)
{
data = k;
next = null;
}
public OneLinkNode()
{
this(0);
}
}
链表类OneLink:
package com;
public class OneLink
{
//头结点
protected OneLinkNode head;
//构造一个空的单向链表
public OneLink()
{
head = null;
}
//只有一个结点的单向链表
public OneLink(OneLinkNode h1)
{
head = h1;
}
//判断链表是否为空
public boolean isEmpty()
{
return head == null;
}
//用随机数构造n个数的链表
public OneLink(int n)
{
OneLinkNode rear,q;
if(n > 0)
{
int k = (int) (Math.random()*100);
head = new OneLinkNode(k);
rear = head;
for(int i = 1; i < n ;i++)
{
k = (int) (Math.random()*100);
q = new OneLinkNode(k);
rear.next = q;
rear = q;
}
}
}
}
Josephus类:
package com;
public class Josephus2 extends OneLink
{
Josephus2() // 构造空的单向循环链表
{
super();
}
Josephus2(int n) // 建立n个结点的单向循环链表
{ // 链表结点值为1到n
this();
int i = 1;
//q新结点,rear尾结点
OneLinkNode q, rear;
if (n > 0)
{
//先创建只有一个结点的单向循环链表
head = new OneLinkNode(i);
//指向自己
head.next = head;
rear = head;
while (i < n)
{
i++;
//新结点
q = new OneLinkNode(i);
//新结点的next字段指向head
q.next = head;
//这里的near是尾结点(第一次就是head)的next字段指向新结点
rear.next = q;
//保存新节点的地址,以便下次循环使用
rear = q;
}
}
}
//计数起点s,d要跳过的个数
public void display(int s, int d) // 解约瑟夫环
{
int j = 0;
OneLinkNode p = head;
while (j < s - 1) // 指针步进到计数起始点
{
j++;
p = p.next;
}
while (p.next != p) // 多于一个结点时循环
{
j = 0;
while (j < d ) // 计数
{
j++;
p = p.next;
}
delete(p); // 删除p的后继结点
p = p.next;
this.output();
}
}
public void delete(OneLinkNode p) // 删除p的后继结点
{
OneLinkNode q = p.next; // q是p的后继结点
System.out.print("delete: " + q.data + " ");
if (q == head) // 欲删除head指向结点时,
head = q.next; // 要将head向后移动
p.next = q.next; // 删除q
}
public void output() // 输出单向链表的各个结点值
{
OneLinkNode p = head;
System.out.print(this.getClass().getName() + ": ");
do
{
System.out.print(p.data + " -> ");
p = p.next;
} while (p != head);
System.out.println();
}
//测试
public static void main(String args[])
{
int n = 5, s = 2, d = 1;
Josephus2 h1 = new Josephus2(n);
h1.output();
h1.display(s, d);
}
}
测试输出结果没有任何问题:
com.Josephus2: 1 -> 2 -> 3 -> 4 -> 5 ->
delete: 4 com.Josephus2: 1 -> 2 -> 3 -> 5 ->
delete: 2 com.Josephus2: 1 -> 3 -> 5 ->
delete: 1 com.Josephus2: 3 -> 5 ->
delete: 3 com.Josephus2: 5 ->
来源:http://www.blogjava.net/supercrsky/articles/171805.html
其实这个题没多难,但是要是在面试的时候问你,现想就来不及了……
分享到:
相关推荐
循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释
单向循环链表实现约瑟夫环.zip
一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部...
使用c语言中的循环链表及结构体实现约瑟夫环问题
VC++采用单向循环链表实现约瑟夫环,希望和大家共勉。
用C语言编写的约瑟夫环问题解决程序,利用单向循环链表存储结构模拟此过程
用单向循环链表解决约瑟夫问题。使用c++语言,结构体,链表的操作。
通过循环链表实现约瑟夫环问题,用c语言实现。属于数据结构部分内容
基于单向循环链表的约瑟夫环设计.doc
约瑟夫环问题: 编号为1,2,3 n的n个人按顺时针方向围坐一圈,没人持有一个密码。一开始任选一个正整数作为报数上限值m,从第一人开始按顺时针方向报数,报到m停止。报m的人出列,将他的密码作为新的m的值,从他的...
约瑟夫环求解,循环链表的使用,经典问题
用双向循环链表解决约瑟夫环问题的程序清单
本程序是采用带头结点的单向循环链表写成的,当指针指到要出列的结点时,先输出结点的序列号,再删除之,直到所有结点都出列完
循环链表实现约瑟夫环问题 约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又...
利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。 测试数据 M的初值为20;n=7,7各人的密码依次为3,1,7,2,4,8,4,首先m值为6(正确出栈顺序为6,1,4,7,2,3,5)
这是用C写的链表表示的循环链表的程序。匹配的报告随后上传。
利用循环链表实现约瑟夫问题的求解。 约瑟夫问题如下:已知n个人(n>=1)围坐一圆桌周围,从1开始顺序编号。从序号为1的人开始报数,顺时针数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依...
单向循环链表 约瑟夫 c++ 利用单向循环链表存储结构模拟约瑟夫问题,按照出列的顺序印出每个人的编号。
约瑟夫问题,通过类实现的链表,并加以改进,做成双向链表
用单向循环链表解决约瑟夫问题的算法优劣性分析.doc