【约瑟夫环的问题】

chunhong_198915 2010-05-12 12:21:02
加精
【约瑟夫环的问题】
有17个人（编号从0到16），按编号依次排列成一个圆环（编号16的接着编号为0 的人），从编号为0 的人开始报数，数到3的人退出圆环，如此循环，最后留下的那个人的编号是什么？
0，1，2，3，4，5，6，7，8，，9，10，11，12，13，14，15，16
要求：请用面向对象的思想来处理这个问题并在下面写出具体的代码（可以选择你熟悉的语言，如java/C++/C#等）
...全文
4178 147 打赏 收藏 转发到动态 举报
写回复
用AI写文章
147 条回复
切换为时间正序
请发表友善的回复…
发表回复
jiushiwang 2011-11-04
  • 打赏
  • 举报
 回复
[Quote=引用 79 楼 hanjin8307 的回复:]

Java code


public static int king(int M, int N) {
// 总人数 M ，数到第 N 个排除。
int k = 0;
for (int i = 2; i <= M; i++){
k = (k + N) % i;
}
return ++k……
[/Quote]
靠，的却牛 x
xxzf426214 2011-10-28
  • 打赏
  • 举报
 回复
public class Count3Quit {
public static void main(String[] args) { //约瑟夫环
int[] a = new int[500];
for(int i=0; i<a.length; i++) {
a[i] = 1;
}

int leftCount = 500;
int countNum = 0;
int index = 0;

while(leftCount != 1) {
if(a[index] == 1) {
countNum ++;
if(countNum == 3) {
countNum = 0;
a[index] = 0;
leftCount --;
}
}

index ++;
if(index == a.length) {
index = 0;
}
}

for(int i=0; i<a.length; i++) {
if(a[i] == 1) {
System.out.println(i);
}
}
}
}
灰色小狼 2011-10-12
  • 打赏
  • 举报
 回复 


/**

 *

 * @author crose_1988@163.com 

 */

public class test {

	public static void main(String[] args) {

		int[] array = new int[17];

		int count = 0;

		for (int i=0; i<array.length; i++) 

			array[i] = 1;

		

		boolean left;

		do {

			left = false;

			for (int i=0; i<array.length; i++) {

				if (array[i] == 1) {

					left = true;

					if (count == 2) {

						array[i] = 0;

						count = 0;

						System.out.println(i + " is left");

					} else

						count++;

				}

			}

		} while (left);

	}

}

2 is left
5 is left
8 is left
11 is left
14 is left
0 is left
4 is left
9 is left
13 is left
1 is left
7 is left
15 is left
6 is left
16 is left
12 is left
3 is left
10 is left
a199228 2011-09-26
  • 打赏
  • 举报
 回复
1.方法一：循环单链表
#include<iostream>
#include<exception>
using namespace std;
class DLinkList;
class DNode
{
friend class DLinkList;
private:
int data;
DNode *next;
};
class DLinkList
{
public:
DLinkList();
~DLinkList();
void push(int data);
int GetLength();
bool DeleteList(int pos);
void DisplayList();
private:
DNode *phead;
void DestroyList();
};
DLinkList::DLinkList()
{
phead=new DNode;
if(!phead) throw runtime_error("Memory allocation failure");
phead->next=phead;
}
DLinkList::~DLinkList()
{
DestroyList();
}
void DLinkList::push(int data)
{
DNode *pnode=new DNode;
if(!pnode) throw runtime_error("Memory allocation failure");
pnode->data=data;
DNode *p=phead;
while(p->next!=phead)
{
p=p->next;
}
pnode->next=phead;
p->next=pnode;
}
int DLinkList::GetLength()
{
int size=0;
DNode *pnode=phead->next;
while(pnode!=phead)
{
++size;
pnode=pnode->next;
}
return size;
}
bool DLinkList::DeleteList(int pos)
{
if(phead->next!=phead)
{
DNode *pnode=phead;
int index=0;
while(pnode->next!=phead && index< pos-1)
{
++index;
pnode=pnode->next;
}
if(pnode->next==phead) return false;
else
{
DNode *pdelete=pnode->next;
pnode->next=pdelete->next;
delete pdelete;
return true;
}
}
else return false;
}
void DLinkList::DisplayList()
{
if(phead->next==phead)
{
cout<<"空表"<<endl;
}
else
{
DNode *pnode=phead->next;
while(pnode!=phead)
{
cout<<pnode->data<<" ";
pnode=pnode->next;
}
cout<<endl;
}
}
void DLinkList::DestroyList()
{
DNode *pnode=phead,*pindirect;
while(pnode->next!=phead)
{
pindirect=pnode->next;
delete pnode;
pnode=pindirect;
}
delete pnode;
}
int main()
{
int total,MaxValue;
cin>>total>>MaxValue;
int index;
DLinkList list;
for(index=1;index<=total;++index)
{
list.push(index);
}
list.DisplayList();
int num;
while((num=list.GetLength())!=1)
{
list.DeleteList(num%MaxValue);
}
list.DisplayList();
return 0;
}
2.用双循环链表容器来模拟过程
#include<iostream>
#include<list>
using namespace std;
int LastSolution(int m,int n)
{
if(m<=0 || n<=0 || m<n)
{
cout<<"error"<<endl;
return false;
}
else
{
list<int>Inter;
for(int i=1;i<=m;++i)
{
Inter.push_back(i);
}
list<int>::iterator ite=Inter.begin();
while(Inter.size()!=1)
{
for(int j=1;j!=n;++j)
{
++ite;
if(ite==Inter.end())
{
ite=Inter.begin();
}
}
ite=Inter.erase(ite);
if(ite==Inter.end())
{
ite=Inter.begin();
}
}
return *ite;
}
}
int main()
{
int total,MaxValue;
cin>>total>>MaxValue;
cout<<LastSolution(total,MaxSize)<<endl;
return 0;
}
3.用数学知识推导出公式
include<iostream>
using namespace std;
int SecondSolution(int m,int n)
{
if(m<=0 || n<=0 || m<n)
{
cerr<<"error"<<endl;
return false;
}
else
{
int lastinteger = 0;

// find the last remaining one in the circle with n integers
for (int i = 2; i <= m; i ++)
lastinteger = (lastinteger + n) % i;

++lastinteger;
return lastinteger;
}
}
int main()
{
int total,MaxValue;
cin>>total>>MaxValue;
cout<<LastSolution(total,MaxSize)<<endl;
return 0;
}
Rajon_amani 2010-05-30
  • 打赏
  • 举报
 回复
package test;
import java.util.*;

public class Joseph {

/**
* @param args
*/
List<String> num = new LinkedList<String>();
List<String> temp = new LinkedList<String>();
public Joseph(int m){
for (int i=0;i<=m;i++){
num.add(i+"");
}
}
public void start(int start,int n){
int size = num.size();
if (num.size ()==1){
System.out.println("留下了:"+num.get(size-1));
return;
}

for (int i=1;i<=size;i++){
if((i+start)%n==0){
System.out.println("出 局:"+num.get(i-1));
temp.add(num.get(i-1));
}
}
for (String remove:temp){
num.remove(remove);
}
temp.clear();
start((size+start)%n,n);
}
public static void main(String[] args) {
// TODO Auto-generated method stub

Joseph j = new Joseph(16);
j.start(0, 3);



}
}
wo28lf 2010-05-26
  • 打赏
  • 举报
 回复
79楼不错！
abasky 2010-05-19
  • 打赏
  • 举报
 回复
约瑟夫环，O(∩_∩)O~
lexbios 2010-05-19
  • 打赏
  • 举报
 回复
用循环来实现实际上效率也不咋地，还是用链表实现直接些。
strike2368168 2010-05-19
  • 打赏
  • 举报
 回复
顶个先~~
wx08101010216 2010-05-19
  • 打赏
  • 举报
 回复
JAVA代码。。懂不鸟。
wangqiang315 2010-05-19
  • 打赏
  • 举报
 回复
呵呵，看看
zhangguoliang_1981 2010-05-19
  • 打赏
  • 举报
 回复
谢谢,写得真不错啊
lacus87 2010-05-19
  • 打赏
  • 举报
 回复
我也手痒了。。。


import java.util.ArrayList;



public class TestRound {

	public static void print(int number,int count) {

		ArrayList list = new ArrayList();

		for (int i = 1; i <=number; i++) {

			list.add(i);

		}

		for (int i = 1; list.size() > 1; i++) {

			if (i % count == 0) {

				System.out.print(list.remove(0) + "-->");

			} else {

				list.add(list.remove(0));

			}

		}

		System.out.println(list.get(0));

	}

	public static void main(String[] args) {

		print(20,3);

	}

}
tillicollapse 2010-05-18
  • 打赏
  • 举报
 回复
学习了
xx314327475 2010-05-18
  • 打赏
  • 举报
 回复
[Quote=引用 10 楼 tingajava 的回复:]
public class Count3Quit {
public static void main(String[] args) {
PersonCircle pc = new PersonCircle(17);
int countNum = 0; //0,1,2,3报数
Person p = pc.first;
while (pc.count > 1) {
countNum++;
……
[/Quote]


你是马士兵么？
能不能自己写啊？
icecream87 2010-05-18
  • 打赏
  • 举报
 回复
再顶一下!!!!!!!
icecream87 2010-05-18
  • 打赏
  • 举报
 回复
都是些狠人啊!!!佩服!!佩服!!!
aytgfyhgr 2010-05-18
  • 打赏
  • 举报
 回复
来学习的。。膜拜
lookvc 2010-05-18
  • 打赏
  • 举报
 回复

class CPerson
{
public:
CPerson(int nIndex);
~CPerson() {}
public:
int GetIndex() { return m_nIndex; }

private:
int m_nIndex;
};

CPerson::CPerson(int nIndex) : m_nIndex(nIndex)
{

}

int Func(int nCount)
{
list<CPerson> q,p;
for(int i=0; i<nCount; i++)
{
CPerson p(i);
q.push_back(p);
}

while (q.size() > 1)
{

int iSize = q.size();
list<CPerson>::iterator it= q.begin();

vector<list<CPerson>::iterator> temp;

for(int j=0; j<iSize; j++)
{
if(j%3 != 0)
{
p.push_back(*it);
}
it++;
}

q.clear();
q = p;
p.clear();
}

CPerson lastPerson = q.front();
return lastPerson.GetIndex();
}
Jacketcat 2010-05-18
  • 打赏
  • 举报
 回复
昨天看的，调试了很久···链表
java code
import java.util.*;
class Link{
int iData;
Link next;
public Link(){
iData=0;

}
}
class LinkArray{
int nItems=0;
Link current;
Link previous;
public LinkArray(){
current=new Link();
previous=new Link();
}
public void insert(int i){
Link newLink=new Link();
newLink.iData=i;
if(!isEmpty()){
newLink.next=current.next;
current.next=newLink;
previous=current;
current=newLink;
}else{
newLink.next=newLink;
current=newLink;
}
nItems++;
System.out.println("inserting "+i);
System.out.println("current= "+current.iData);
System.out.println("previous= "+previous.iData);
System.out.println("nItems= "+nItems);
System.out.println();
}
public boolean isEmpty(){
return (nItems==0);
}
public void step(){
current=current.next;
previous=previous.next;
}
public void delete( int n){
while(nItems>1){
for(int i=0;i<n-1;i++)
step();
System.out.println("deleting "+current.iData);
previous.next=current.next;
current=current.next;
System.out.println("current= "+current.iData);
System.out.println("previous= "+previous.iData);
System.out.println();
nItems--;
}
}
public void displayLink(){
int n=nItems;
Link now=current;
while(n != 0){
System.out.print(now.iData+" ");
now=now.next;
n--;
}
}
}
public class Jessus{
public static void main(String[] args){
LinkArray jessus=new LinkArray();
System.out.println("Enter the queue number :");
Scanner in=new Scanner(System.in);
int m=in.nextInt();
System.out.println("Enter the dead number :");
Scanner de=new Scanner(System.in);
int n=de.nextInt();
for(int i=0;i<m;i++)
jessus.insert(i);
jessus.previous=jessus.current;
jessus.current=jessus.current.next;
jessus.displayLink();
System.out.println();
jessus.delete(n);
System.out.print("the last one left : #");
jessus.displayLink();
}
}
加载更多回复（127）
用单链表解决约瑟夫环问题
用单链表解决约瑟夫环问题，数据结构实验报告。约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
用循环链表实现约瑟夫环问题
使用c语言中的循环链表及结构体实现约瑟夫环问题
图解Java数据结构和算法
1.算法是程序的灵魂，优秀的程序在对海量数据处理时，依然保持高速计算，就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少，但存在两个问题：1)授课方式单一，大多是照着代码念一遍，数据结构和算法本身就比较难理解，对基础好的学员来说，还好一点，对基础不好的学生来说，基本上就是听天书了2)说是讲数据结构和算法，但大多是挂羊头卖狗肉，算法讲的很少。 本课程针对上述问题，有针对性的进行了升级 3)授课方式采用图解+算法游戏的方式，让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外，还包括程序员常用10大算法：二分查找算法（非递归）、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题，让你秒杀其他面试小伙伴3.如果你不想永远都是代码工人，就需要花时间来研究下数据结构和算法。教程内容：本教程是使用Java来讲解数据结构和算法，考虑到数据结构和算法较难，授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。学习目标：通过学习，学员能掌握主流数据结构和算法的实现机制，开阔编程思路，提高优化程序的能力。
c++多种方法解决约瑟夫环问题
多种方法解决约瑟夫环问题，1.顺序表2.循环链表3.循环队列4.普通一位数组
约瑟夫环问题用循环队列解决
用循环队列解决约瑟夫环问题减少用顺序表在出对是循环移动带来的空间复杂度
Java SE

62,614

社区成员

307,319

社区内容

发帖
与我相关
我的任务
社区描述
Java 2 Standard Edition
社区管理员
  • Java SE
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章