北大《百练》上的题目
http://poj.grids.cn/practice/2746/,用单循环链表模拟了一下。
时间限制: 1000ms 内存限制: 65536kB
描述
约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。
输入
每行是用空格分开的两个整数,第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是:
0 0
输出
对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号
样例输入
6 2
12 4
8 3
0 0
样例输出
5
1
7
下面是AC代码:
import java.util.Scanner;
public class Main< T> {
private int size = 0;
private Node< T> head, tail,current;
public Main() {
head = tail =null;
current=tail;
}
public void add(T data) {
if (size == 0) {
head = new Node< T>(data, null);
head.next=head;
tail=head;
current=tail;
} else {
tail.next = new Node< T>(data, head);
tail = tail.next;
current=tail;
}
size++;
}
public T moveANDremove(boolean flag){
T data=current.next.getData();
if(flag) {
if(current.next==head){
head=current.next.next;
}else if(current.next==tail){
tail=current;
}
current.next=current.next.next;
size--;
return data;
}else{
current=current.next;
return data;
}
}
public int size(){
return size;
}
public String toString(){
if (size < 1) {
return "没有元素";
} else {
Node< T> tmp = head;
StringBuffer sb=new StringBuffer();
do{
sb.append(tmp.getData()+" ");
tmp = tmp.next;
}while (tmp!=head);
return sb.toString();
}
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
while(true){
int k=1;
int n=in.nextInt();
int m=in.nextInt();
if(n==0&m==0) break;
Main< Integer> l = new Main< Integer>();
for(int i=1;i<=n;i++)
l.add(i);
while(true){
if(k%m!=0) {
l.moveANDremove(false);
k++;
}
else{
l.moveANDremove(true);
k=1;
}
if(l.size()==1) {
System.out.println(l.current.getData());
// System.out.println(l);
break;
}
}
}
}
}
class Node< T> {
T data;
Node< T> next;
public Node(T data, Node< T> next) {
this.data = data;
this.next = next;
}
public T getData(){
return data;
}
public void setData(T data){
this.data=data;
}
}
源码下载
分享到:
相关推荐
VC++2012编程演练数据结构《2》单循环链表与约瑟夫问题
循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释
约瑟夫问题,通过类实现的链表,并加以改进,做成双向链表
使用c语言中的循环链表及结构体实现约瑟夫环问题
通过循环链表实现约瑟夫环问题,用c语言实现。属于数据结构部分内容
双向循环链表解决约瑟夫实验报告, 双向循环链表解决约瑟夫实验报告 双向循环链表解决约瑟夫实验报告双向循环链表解决约瑟夫实验报告
用单向循环链表解决约瑟夫问题。使用c++语言,结构体,链表的操作。
用C++做的单循环链表简单表示了约瑟夫问题
利用循环链表实现约瑟夫问题的求解。 约瑟夫问题如下:已知n个人(n>=1)围坐一圆桌周围,从1开始顺序编号。从序号为1的人开始报数,顺时针数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依...
约瑟夫环的问题描述 问题描述:编号为1,2… n的n个人按顺时针方向围坐一圈,每人持有...利用单循环链表作为存储结构模拟此过程; ⑵.键盘输入总人数、初始报数上限值m及各人密码; ⑶.按照出列顺序输出各人的编号。
用双向循环链表解决约瑟夫环问题的程序清单
C++_循环链表实现约瑟夫问题 vc2008 课堂作业!
单向循环链表实现约瑟夫环.zip
用C语言编写的约瑟夫环问题解决程序,利用单向循环链表存储结构模拟此过程
有20个人排成一个圈,从第1个人开始循环报数,报到3或者3的倍数的离开圈子; 请编程计算并输出最后剩下三个人时是哪几个人。
循环链表实现约瑟夫环问题 约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又...
不再采用单向循环链表解决约瑟夫问题,而是双向循环链表解决约瑟夫,并采用一些技巧来解释使用说明,即教程,并且密码可以为正整数,也可以为负数
这是用C写的链表表示的循环链表的程序。匹配的报告随后上传。
利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。 测试数据 M的初值为20;n=7,7各人的密码依次为3,1,7,2,4,8,4,首先m值为6(正确出栈顺序为6,1,4,7,2,3,5)