约瑟夫问题c++代码（C++ 约瑟夫环问题 代码求解释~）

本文目录

• C++ 约瑟夫环问题 代码求解释~
• C++利用顺序表实现约瑟夫问题
• 用C++编写约瑟夫环的代码，也就是出圈问题，n个人，数到k出圈，接着从1开始数，一直到最后一个人，
• 要求定义类，用C++面向对象的思想解决约瑟夫环问题，下面是我的代码没有定义类，求大神修改
• 求c++程序设计“约瑟问题”的算法
• 关于数据结构 约瑟夫死亡游戏的代码C++

C++ 约瑟夫环问题 代码求解释~

首先，这个代码输出的是，约瑟夫环到达的最后位置。输出结果是15。
//把iostream这个文件中的内容复制到这个地方。
#include《iostream》
using namespace std;
int main()
{
//定义一个常量的整形100，表示人的个数。
const int n=100;
//定义约瑟夫环的参数。
int m=30;
//定义一个数组，用于计算约瑟夫环的位置。
int a;
//给数组赋值，让数组的每个值就是这个元素的编号。
for(int j=0;j《n;j++)
a=j+1;
//定义一个标志k，当K等于N的时候，表示到达约瑟夫环的最后位置。
int k=1;
int i=-1;
while(1)
{
for(int j=0;j《m;)
{
//不停的取数组的下一个元素。
i=(i+1)%n;
//如果这个元素没有被标记为0，说明这个位置还没有被排除，j加1，进入下一个循环
if(a!=0)
j++;
}
//如果标志K等于n，说明约瑟夫环的循环到达最后一个位置，跳出While死循环。
if(k==n)
break;
//否则，把这个位置的元素设为零，标志它被排除。
a=0;
//标志+1。
k++;
}
//输出约瑟夫环到达的最后一个位置。
cout《《a《《endl;
return 0;
}

C++利用顺序表实现约瑟夫问题

#include《iostream》
#define MaxSize 50
#define ElemType int
using namespace std;
typedef struct //定义顺序表结构体类型
{
ElemType data; //存放每个人的编号
int length;
}SqList;
void CreateList(SqList&L,int n) //创建顺序表
{
int i;
for(i=0;i《n;i++)
L.data
L.length=n; //共n个人
}
void DispList(SqList L) //显示顺序表中的记录
{
cout《《"\n\n 幸存者的位置 :\n";
for(int i=0;i《L.length;i++)
cout《《L.data《《"\t";
cout《《endl;
}
int ListDelete(SqList&L,int i,ElemType &e) //从顺序表中删除所选定的人的编号
{
int j;
if(i《1||i》L.length)
return 0;
i--;
e=L.data;
for(j=i;j《L.length-1;i++)
L.data;
L.length--;
return 1;
}
void Josephus(SqList&L,int m,int k) //约瑟夫问题实现过程
{
ElemType
int i,n=0; //用n记录下标，下标从0开始
cout《《"被杀者的位置 ：\n";
for(i=1;i《=k;i++) //将k个人抛入大海
{
for(int j=1;j《m;j++) //每报数到m时，此人被扔入大海
{
n=n%L.length;
n++;
}
ListDelete(L,n+1,e); //位置=下标+1
cout《《e《《’\t’;
}
}
int main(
{
SqList sql;
CreateList(sql,30); //将30人的编号存入顺序表
Josephus(sql,9,15); //每数到第9个人就将他扔入大海，如此循环进
//行，直到仅余15个人为止
DispList(sql); //输出剩余的15人的位置
return 0;
}

用C++编写约瑟夫环的代码，也就是出圈问题，n个人，数到k出圈，接着从1开始数，一直到最后一个人，

#include 《iostream》 
using namespace std; 
int main() 
{ 
 int n,s,m; 
    cout《《"please input the valuse of n,m,s"《《endl;
 cin》》n》》m》》s;
    if(n《=0||s《=0||m《=0)
 { 
 cout《《"error"《《endl;
 } 
 int i,j,k,temp;//k为次数 
 int A; 
 for(i=0;i《n;i++)
 { 
  A=i+1;
 }//建立数组 
 i=s-1;//设定开始报数的起始位置 
 for(k=n;k》1;k--)
 { 
  i=((i+m-1)%k);//计算要报数人序号 
  if(i!=k-1)
  { 
   temp=A; 
   for(j=i;j《k-1;j++) 
   A;//将i位置一直到k-1位置元素向前移一位 
   A=temp;//将报数的人移动至数组最后 
  } 
 } 
    cout《《"the jodephus order is"《《endl;
 for(k=n-1;k》=0;k--)
 {   
        
  cout《《A《《" ";//反向输出输出数组元素即为所求数列 
 } 
  return 0; 
}

要求定义类，用C++面向对象的思想解决约瑟夫环问题，下面是我的代码没有定义类，求大神修改

#include 《iostream》 
using namespace std; 
class Solution {
public: typedef struct Node{ 
int num,pwd; 
struct Node *next; 
}Node,*LinkList; 
public: static LinkList getnode(int n) 
{ 
//head为开头指针,tail为末尾指针,p为当前指针的前一个指针,q为当前指针. 
LinkList head,tail,p,q; 
int i; 
head=new Node; 
p=head; 
for(i=1;i《n;i++) 
{ 
q=new Node; 
p-》next=q; 
p=q; 
} //建立一个n个结点的链表. 
tail=q; 
tail-》next=head; 
p=head; 
for(i=1;i《=n;i++) 
{ 
p-》num=i; 
cout《《"Please enter No."《《i《《"’s password:"; 
cin》》p-》pwd; 
p=p-》next; 
} //输入个人持有密码. 
return head; 
} 
public: static void display(Node *p, int n, int m) 
{ 
int i,j; 
LinkList q;
for(i=0;i《n;i++)p=p-》next;
for(i=1;i《=n;i++) 
{ 
for(j=1;j《m;j++)p=p-》next; 
q=p-》next; 
m=q-》pwd; 
if(i==n) 
{ 
cout《《q-》num《《endl; 
break; 
} 
cout《《q-》num《《" "; 
p-》next=q-》next; 
delete q; 
} //输出序列
} 
public: static int main() 
{ 
int m=0,n=0; //m为初始密码,n为人数. 
cout《《"Please enter m="; 
cin》》m;
cout《《"Please enter n="; 
cin》》n; 
LinkList head; //head为开头指针. 
head=getnode(n); 
cout《《"result:"《《endl; 
display(head,n,m);
return 0;
}
};
int main(){return Solution::main();}

求c++程序设计“约瑟问题”的算法

C++ 的一个约瑟夫环问题函数(自己调用即可):
void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数
{
/* p为当前结点 r为辅助结点，指向p的前驱结点 list为头节点*/
LinkList p,r,list;
/*建立循环链表*/
for(int i=0,i《n,i++)
{
p=(LinkList)malloc(sizeof(LNode));
p-》data=i;
if(list==NULL)
list=p;
else
r-》link=p;
r=p;
}
p-》link=list; /*使链表循环起来*/
p=list; /*使p指向头节点*/
/*把当前指针移动到第一个报数的人*/
for(i=0;i《k;i++)
{
r=p；
p=p-》link;
}
/*循环地删除队列结点*/
while(p-》link!=p)
{
for(i=0;i《m-1;i++)
{
r=p;
p=p-》link;
}
r-》link=p-》link;
printf("被删除的元素：%4d ",p-》data);
free(p);
p=r-》link;
}
printf("\n最后被删除的元素是：％4d",P-》data);
}
数学方法解决:
Josephus(约瑟夫)问题的数学方法
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出
，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是(m-1)%n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。
现在我们把他们的编号做一下转换：
k --》 0
k+1 --》 1
k+2 --》 2
...
...
k-3 --》 n-3
k-2 --》 n-2
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x‘=(x+k)%n
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f.
递推公式:
f=0;
f=(f+m)%i; (i》1)
有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f+1由于是逐级递推，不需要保存每个f，程序也是异常简单：
#include 《stdio.h》
int main(void)
{
int n, m, i, s=0;
printf ("N M = ");
scanf("%d%d", &n, &m);
for (i=2; i《=n; i++)
s=(s+m)%i;
printf ("The winner is %d\n", s+1);
return 0 ;
}
这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。

关于数据结构 约瑟夫死亡游戏的代码C++

#include《iostream》
using namespace std;
template《class T》
struct LinkNode
{
T data;
LinkNode《T》*link;
LinkNode( T item)
{
data=item;
link=NULL;
}
};
template《class T》
class List
{
public:
List() //构造函数
{
first=new LinkNode《T》;
first-》link=first;//头尾相连，循环链表，用它可以让你数到最后一个人的时候，他的下一个人就是队伍的第一个家伙
}
List(T x)
{
first=new LinkNode《T》(x);
first-》link=first;
}
List(List《T》&L);
~List(){}
void Insert(int i,T x);
T getHead(){return first-》data;}
LinkNode《T》* getfirst(){return first;}
void xiuf(LinkNode《T》* a){first=a;}
LinkNode《T》*Locate(int i);
protected:
LinkNode《T》*first;
};
template《class T》
List《T》::List(List《T》&L) //复制构造函数，就是用来复制
{
T value;
LinkNode《T》*srcptr=L.getHead();
LinkNode《T》*destptr=first=new LinkNode《T》;
destptr-》data=srcptr-》data;
while(srcptr-》link!=first)
{
value=srcptr-》link-》data;
destptr-》link=new LinkNode《T》(value);
destptr=destptr-》link;
srcptr=srcptr-》link;
last=srcptr;
}
};
template《class T》
LinkNode《T》* List《T》::Locate(int i) //搜索含数值为i的结点，就是找第i个顶点
{
if(i《0)return NULL;
LinkNode《T》* current=first;
int k=1;
while(k《i)
{
current=current-》link;
k++;
if(current==first)return NULL;
}
return current;
};
template《class T》
void List《T》::Insert(int i,T x) //添加顶点。。i是用来找到链表的末尾。。
{
LinkNode《T》* current=Locate(i);
if(current==NULL)return;
LinkNode《T》*newNode=new LinkNode《T》(x);
if(newNode==NULL) //当前指针为空，未取到数据的值
{
cout《《"存储分配错误!"《《endl;
exit(1);
}
newNode-》link=current-》link;
current-》link=newNode;
};
template《class T》
void Josephus(List《T》& Js,int n,int m)
{
LinkNode《T》 *p=Js.Locate(1),*pre;
int i,j;
for(i=1;i《=n/2;i++) //要扔入水里的人，一共是n/2=15人
{
if(m==1) //如果没次只扔序号为1那个家伙,按顺序把每次第一个人扔下去
{
cout《《"出列的人是:"《《p-》data《《endl;
pre=p-》link;
//这个用来让first指向当前first下一个家伙
Js.xiuf(p-》link);
delete p;
p=pre;
}
else
{
//从当前位置开始数m个人，这个人是p,pre是p的前一个家伙
for(j=1;j《m;j++)
{
pre=p;
p=p-》link;
}
cout《《"出列的人是"《《p-》data《《endl;
//让pre连接着p
pre-》link=p-》link;
//如果是第一个家伙就把first改成first的下一个
if(p==Js.getfirst())Js.xiuf(p-》link);
//if(p=Js.getlast())Js.movelast(pre);
delete p;
p=pre-》link;
}
}
}
void main()
{
List《int》 clist(1);
int i,n,m;
cout《《"输入游戏者的人数和报数间隔："《《endl;
cin》》n》》m;
for(i=1;i《n;i++)
{ clist.Insert(i,i+1);
}
Josephus(clist,n,m);
}