1.算法描述
简单的游戏:有N个人坐成一圈,编号1-N、从编号为1的人开始传递热马铃薯。M次传递之后,持有马铃薯的人退出游戏,圈缩小,然后游戏从退出人下面的人开始,继续进行,最后留下的人获胜。如,M=0, N=5则参加游戏的人依次退出,5号获胜。M=1,N=5则退出顺序是2,4,1,5.
2.算法分析
该算法使用一个没有头指针的循环链表完成,移动的过程计数,如果计数为M,则将其移除并从下一位继续开始,否则继续。过程非常简单,主要考察指针的运用。当然还可以使用数组实现,不过移动所花费开销非常大!不推荐使用数组。
该算法的复杂度为O(n),直接对链表操作。
3.代码
#include <iostream>
#include <ctime>
using namespace std;
const int LNE = 100000;
struct Node{
Node *next;
int data;
};
//创建一个没有头结点的链表
Node* createList(int *a, int n){
Node* first = new Node;
first->data = a[0];
Node* t = first;
for(int i=1; i<n; i++){
Node* r = new Node;
r->data = a[i];
t->next = r;
t = r;
}
t->next = first;
return first;
}
//N个人,传递M次
int josephus(Node *l, int M, int N){
if(M<0 || N < 1) return -1;
if(M >= N) M %= N; //处理M
int count = 0; //用于计数
Node *p = l, *t;
//当M为0的时候处理方式,依次处理,最后一个人即是胜利者
if(M == 0){
while(1){
if(p->next == l) return p->data;
t = p;
//cout<<p->data<<" ";
p = p->next;
delete t;
}
}else{
//循环到只剩最后一个人
while(N != 1){
//计数到M之前的位置
if(count == M-1){
t = p->next;
//只剩最后元素,退出
if(t == p){
break;
}else{ //没有到最后一个
p->next = t->next;
//cout<<t->data<<" ";
delete t;
N --; //总人数减去1
}
count = -1;
}
p = p->next;
count ++; //计数器加1
}
}
return p->data;
}
int main(){
int *a = new int[LNE];
for(int i=0; i<LNE; i++){
a[i] = i+1;
}
int k;
Node *f = createList(a, LNE);
cout<<"输入传递次数:";
cin>>k;
time_t b = time(NULL);
cout<<endl;
cout<<"胜利者是:"<<josephus(f, k, LNE)<<endl;
time_t e = time(NULL);
cout<<"耗时:"<<e-b<<endl;
delete []a;
return 0;
}
分享到:
相关推荐
labview的josephus问题编程
编程求Josephus问题:m个小孩围成一圈,从第一个小孩开始顺时针方向每数到第n个小孩时这个小孩就离开,最后剩下的一个小孩是胜利者。求第几个小孩是胜利者。
教你如何用数据结构的思想来解决Josephus问题 而且是用C来描述的喔
Josephus问题的解答,分别使用不同的方法
用链式存储结构实现Josephus问题,用户按照执行提示输入n、s、m,输出题目要求的出列顺序
生活不易,赚点积分...C语言实现,大二作业...
设有n个人围坐一圈并由1到n编号,从某个人开始报数,数到m的人出列,接着从出列的下一个人开始重新1到n报数,数到m的人又出列,如此反复地报数和出列,直到最后一个人出列为止,设计确定这n个人出列序列的程序
关于Josephus问题数学公式推导和论证的几篇论文
用c++解决了josephus问题:有n个人围在一个圆桌周围,现从第s个人开始报数,数到第m个人又出列…如此反复直到所有的人全部出列为只止。
Josephus 问题的 C 语言代码 ,链表实现,有查找抄作
Josephus问题的顺序表实现 关于Josephus问题的顺序表实现
自己用VC编写的解决Josephus问题,能够根据任何输入得出最终结果,还算健壮,供大家参考,如有好意见欢迎讨论
Josephus问题向量实现,已经运行成功了,代码简单易懂,
这个完全符合课本上习题的要求,我作业交的就是这个,我自己还在里面做了详细的注释
用顺序存储结构实现Josephus问题,用户按照执行提示输入n、s、m,输出题目要求的出列顺序
Josephus问题可以描述为如下的一个游戏:N个人编号从1到N,围坐成一个圆圈,从1号开始传递一个热土豆,经过M次传递后拿着土豆的人离开圈子,由坐在离开的人的后面的人拿起热土豆继续进行游戏,直到圈子只剩下最后一...
数据结构实验报告,用C写的Josephus问题的使用链表和向量的简单实现。