约瑟夫环问题编一段C++程序,将军士兵共15人并围成圆,数到三将淘汰一个人,请编程序求出将军坐哪里不会出局

#include<stdioh>

#include<stringh>

int main()

{

int n=15,k=3,i,x; //n为开始人数 k表示数到三将淘汰一个人 x表示将军能存活的位置

int c[16]={0}; //c[16]表示15个人c[i]=0为活 c[i]=1为已死 由于下面循环是从标号一开始所以数组要多出一个

int s=0,value=0; //s在下面循环中发挥作用当s=k=3时淘汰一人 value表示已经死亡人数

while(value!=n-1)

{

for(i=1;i<=n;i++)

{

if(c[i]==0&&s<k)// 若c[i]=0 读数继续s+1

{

s++;

if(s==k) //当s=3时淘汰当前人c[i]令c[i]=1

{

c[i]=1;

s=0;

value++;//死亡人数增加

}

}

}

}

for(i=1;i<=n;i++) //循环找出存活位置

if(c[i]==0)

x=i;

printf("%d",x);

return 0;

}

这是我自己写的程序，直接运行就是正确结果了，要是有哪里有不懂的地方，再问吧……

#include<stdioh>

#include<stdlibh>

typedef struct node{

int data;

struct node link;

}LNode,LinkList;

int main()

{

LinkList p,r,list=NULL;

int i,n,num,start;

//此处n是指所有人数

//此处start是指从编号为start的人开始报数

//此处num是指数到num的人出列

scanf("%d%d%d",&n,&num,&start);

for(i=1;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;

//以上是构建了一个循环链表，链表不带头结点

for(i=1;i<start;i++)

{

r=p;

p=p->link;

}

//以上是得到了起始编号start的指针p，其前缀指针为r

while(p->link!=p)

{

for(i=1;i<num;i++)

{

r=p;

p=p->link;

}

//此时p是应当被删除的一位，r是p的前缀指针

r->link=p->link;

printf("%d ",p->data);

free(p);

p=r->link;

}

printf("\n最后被删除的结点是%d\n",p->data);

}

void InitList(LinkList &head)改成void InitList(LinkList head)，同时该函数中head全部改成head

void CreateListA同样处理。

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

链表方法：这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head 解决问题的核心步骤：（程序的基本算法） 1建立一个具有n个链结点，无头结点的循环链表； 2确定第1个报数人的位置； 3不断地从链表中删除链结点，直到链表为空。 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); }

#include<iostream>

using namespace std;

struct LinkList

{

int number; //编号

int key; //持有密码

LinkList next; //指针

};

LinkList CreateList(LinkList L,int &n); //创建循环链表

void Joseph(LinkList L,int n); //约瑟夫环解决方案

LinkList DeleteList(LinkList L,int i,LinkList q); //删除以L为头第i个结点,返回结点

/

注意！！修改链表头指针，必须传入指向链表头指针的指针，否则相当于形参

这样子函数返回后头指针仍然没有改变，所以每次删除到头指针时会出错

/

int LengthList(LinkList L); //求循环链表长度

void main()

{

LinkList L;

L=NULL;

int n;

cout<<"请输入人数：";

cin>>n; //设置人数

L=CreateList(L,n); //创建循环链表

Joseph(L,n); //约瑟夫环解决方案

}

LinkList CreateList(LinkList L,int &n)

{

cout<<"将这"<<n<<"个人编号为1-"<<n<<"号。"<<endl<<"请依次输入这"<<n<<"个人的密码:";

LinkList q;

for(int i=1;i<=n;i++)

{

LinkList p;

p=new LinkList; //创建新结点用p指向它

p->number=i; //编号

cin>>p->key; //输入持有密码

p->next=NULL;

if(i==1) L=q=p; //若是第一个结点，直接用头指针指向它

else

{

q->next=p; //将p指向的结点加入链表

q=q->next; //q始终保持指向最后的结点

}

}

q->next=L; //q指向的最后的结点指针域指向头结点，则成为循环链表

return(L);

}

/

约瑟夫环解决方案

/

void Joseph(LinkList L,int n)

{

int m;

cout<<"请输入第一个报数上限值:"; //设置第一轮报数上限值

cin>>m;

cout<<"\n出列顺序:\n";

for(int i=1;i<n;i++)

{

LinkList q = new LinkList;

q=DeleteList(&L,m,q); //删除L开始第m个结点，修改头指针位置，q返回信息

/

这里传入头指针的地址，也就是指向头指针的指针

/

cout<<"号数："<<q->number<<"所持密码为："<<q->key<<endl;//打印相关信息

m=q->key; //修改报数上限值为被删除结点的密码值

delete q;

}

cout<<"号数："<<L->number<<"所持密码为："<<L->key<<endl;;

}

/

删除以L为头第i个结点，返回结点指针,改变表头位置

/

LinkList DeleteList(LinkList L,int i,LinkList q)

{

/

i==1时的处理稍作改动，其实一样，但是没有递归了

/

if(i==1) i+=LengthList(L);

LinkList p;

p=L;

int j=0;

while(j<i-2) {p=p->next;j++;} //p指向第i-1个结点，即被删除结点的前驱结点

q = p->next; //p指向被删除结点，返回信息

p->next=p->next->next; //删除第i个结点

L = p->next; //修改头指针

return(q);

}

/

求循环链表长度

/

int LengthList(LinkList L)

{

int i=1;

LinkList p=L->next;

while(p!=L)

{

i++;

p=p->next;

}

return(i); //返回长度

}

果然还是改链表头指针的问题，我已经在代码里写了详细注释，你看看，也可以看看参考资料的这篇文章。

/

基本要求

基本的约瑟夫的描述：

古代某法官要判决N个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，

从第S个人开始数起，每数到第D个犯人，就拉出来处决，然后再数D个，数到的人再处决，

直到剩下的最后一个可赦免。

发展的约瑟夫的描述：

古代某法官要判决N个犯人的死刑，

但这N个人每人持有一个密码，他有一条荒唐的法律，将犯人站成一个圆圈，

法官先给出一个密码M，从第S个人开始数起，每数到第M个犯人，就拉出来处决，

再根据这个人所持有的密码F，然后再数F个，数到的人再处决，

以此类推直到剩下的最后一个可赦免。

测试数据

数据请自己添加。

/

#include <iostream>

using namespace std;

// 表示一个犯人的结构体

struct Prisoner

{

// 编号

int id;

// 密码

int pass;

// 用于链表的指针

struct Prisoner pre;

struct Prisoner next;

};

class JosephCircle

{

public:

// 基本的约瑟夫构造函数

JosephCircle(int N,int S,int D);

// 发展的约瑟夫构造函数

JosephCircle(int N,int S,int M,int password[]);

// 输出约瑟夫环

void print();

// 开始处决犯人

void start();

private:

// 约瑟夫环的头指针

struct Prisoner head;

// 第一个被处决的犯人的节点指针

struct Prisoner firstPunishedPrision;

};

JosephCircle::JosephCircle(int N,int S,int D)

{

struct Prisoner p , pr;

// 约瑟夫环的头指针初始化为空

this->head = NULL;

// 构造一个由 N 个犯人组成的约瑟夫环

for(int i=1;i<=N;i++)

{

// 当前添加的犯人是第一个犯人，要特殊处理一下

if(this->head == NULL)

{

// 新增一个犯人

p = new struct Prisoner();

// 犯人编号

p -> id = i;

// 犯人密码

p -> pass = D;

// 紧挨着的下一个犯人（因为是环状的，每个人都会有紧挨着的其他犯人）

p -> pre = p;

p -> next = p;

// 约瑟夫环的头指针

this->head = pr = p;

}

else

{

p = new struct Prisoner();

p -> id = i;

p -> pass = D;

p -> pre = pr;

p -> next = pr->next;

pr -> next -> pre = p;

pr -> next = p;

pr = p;

}

}

// 寻找约瑟夫环里面第一个被处决的犯人的节点指针

firstPunishedPrision = head;

for(int i=2;i<=(S+D-1);i++)

{

this->firstPunishedPrision = this->firstPunishedPrision -> next;

}

}

JosephCircle::JosephCircle(int N,int S,int M,int password[])

{

struct Prisoner p , pr;

// 约瑟夫环的头指针初始化为空

this->head = NULL;

// 构造一个由 N 个犯人组成的约瑟夫环

for(int i=1;i<=N;i++)

{

// 当前添加的犯人是第一个犯人，要特殊处理一下

if(this->head == NULL)

{

// 新增一个犯人

p = new struct Prisoner();

// 犯人编号

p -> id = i;

// 犯人密码

p -> pass = password[i-1];

// 紧挨着的下一个犯人（因为是环状的，每个人都会有紧挨着的其他犯人）

p -> pre = p;

p -> next = p;

// 约瑟夫环的头指针

this->head = pr = p;

}

else

{

p = new struct Prisoner();

p -> id = i;

p -> pass = password[i-1];

p -> pre = pr;

p -> next = pr->next;

pr -> next -> pre = p;

pr -> next = p;

pr = p;

}

}

// 寻找约瑟夫环里面第一个被处决的犯人的节点指针

firstPunishedPrision = head;

for(int i=2;i<=(S+M-1);i++)

{

this->firstPunishedPrision = this->firstPunishedPrision -> next;

}

}

// 输出约瑟夫环

void JosephCircle::print()

{

struct Prisoner p = this->head;

if(p != NULL)

{

do

{

cout << "[编号：" << p->id << "，密码：" << p->pass << "]" ;

if(p->next != this->head)

{

cout<<" -> ";

}

p = p->next;

}while(p != this->head);

}

cout << endl << endl;

}

// 开始处决犯人

void JosephCircle::start()

{

struct Prisoner p = this->firstPunishedPrision,pr,q;

int counter = 1;

/

因为约瑟夫环是一个循环链表（也就是一个圈），

当 p->next != p 的时候，说明圈里面还有多余一个的节点（犯人），

继续数数并处决犯人

/

while(p->next != p)

{

// q 向当前被处决的犯人

q = p;

// 从约瑟夫环里面删除被处决掉的犯人

q -> pre -> next = q -> next;

q -> next -> pre = q -> pre;

p = p -> next;

// 输出被处决的犯人的信息

cout << "第 "<< (counter++) << " 个被处决的犯人编号：" << q->id <<endl;

// 寻找下一个将要处决的犯人

for(int i=1;i<=(q->pass-1);i++)

{

p = p->next;

}

// 释放内存（被处决掉的犯人）。

free(q);

}

// 输出被赦免的犯人的信息

cout << "被赦免的犯人的编号：" << p->id << endl << endl;;

}

int main(int argc, char argv[])

{

// 基本的约瑟夫环： JosephCircle(int N,int S,int D);

JosephCircle j1 = JosephCircle(3,1,2);

j1print();

j1start();

// 发展的约瑟夫环： JosephCircle(int N,int S,int M,int password[]);

int pass[]={1,5,3};

JosephCircle j2 = JosephCircle(3,1,2,pass);

j2print();

j2start();

return 0;

}

帮你改了程序

#include <stdafxh>

#include <stdlibh>

struct number

{

int num;

struct number next;

};

void main ()

{

int m, n;

struct number p, head=NULL, tail;

printf("please input M and N:\n");

scanf("%d %d", &m, &n); //输入M、N值。

for (int i=1; i<=n; i++) //建立循环链表。

{

p=(struct number )malloc(sizeof(struct number));

p->num=i;

if(head==NULL){

head=p;

tail=p;//注意开始tail也要赋值

}

else

tail->next=p;

tail=p;

}

tail->next=head;

p = tail; //从head开始，记录开始的前一个指针

while(n--) //剩下的数的个数为n

{ int t = m%n; //防止多数太多圈造成时间浪费

for(int j=1; j<t;j++ ) //数到要删的那个数的前一个

p=p->next;

number q = p->next; //要删的数的指针

printf("%d ", q->num); //输出要删的数

p->next = q->next; //要删的数从链表中去掉

free(q);

}

printf("\n");

}

以上就是关于约瑟夫环问题编一段C++程序,将军士兵共15人并围成圆,数到三将淘汰一个人,请编程序求出将军坐哪里不会出局全部的内容，包括:约瑟夫环问题编一段C++程序,将军士兵共15人并围成圆,数到三将淘汰一个人,请编程序求出将军坐哪里不会出局、求大神 分析C语言约瑟夫环问题（最好能在程序旁边写注释） 悬赏分多多送上！！！、一个简短的约瑟夫环C程序，在VC6.0中编译通过，在gcc下提示&符号非法，怎么改使它能运行呢等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！