C++编程：约瑟夫环问题。

/

基本要求

基本的约瑟夫的描述：

古代某法官要判决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<stdioh>

int

main()

{

int

i,k,m,n,num[50],p;

int

n;

printf("输入两个数字n和m:\n");

scanf("%d",&n);

while(scanf("%d",&n)!=eof)

{

if(n==0)

return

0;

else

{

p=num;

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

(p+i)=i+1;

i=0;

k=0;

m=0;

}

while(m<n-1)

{

if((p+i)!=0)

k++;

if(k==n)

{

(p+i)=0;

k=0;

m++;

}

i++;

if(i==n)i=0;

}

while(p==0)

p++;

printf("%d\n",p);

}

}

望采纳哦~~

while((r)next!=r)

{

//查找报数为n-1和n的结点，便于 *** 作

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

{

p=r;

r=(r)next;

}

}

每次free释放后，链表的节点数应该减小

楼主你好~~！

帮你解决了问题，代码见下：

#include<stdioh>

main()

{int m,n,i,count,d;

int a[100];

scanf("%d,%d",&m,&n);

for(i=0;i<m;i++)

a[i]=i+1;

count=d=0;

while(d<m)

{ for(i=0;i<m;i++)

if(a[i]!=0)

{count++;

if(count==n)

{printf("%d",a[i]);

a[i]=0;

count=0;

d=d+1;}

}

}

试过可行，自己看下，体会一下吧~~！

#include #define MaxSize 50 #define ElemType int using namespace std; typedef struct //定义顺序表结构体类型 { ElemType data[MaxSize]; //存放每个人的编号 int length; }SqList; void CreateList(SqList&L,int n) //创建顺序表 { int i

帮你改了程序

#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");

}

#include <stdioh>

#include <conioh>

#define N 300

int main(){

 int hou[N],n,m,i,j,k;

 while(1){

  scanf("%d%d",&n,&m);

  if(n<1)break;

  for(i=0;i<n;++i){

   hou[i]=i+1;

  }

  printf("Out: ");

  k=-1;//从第k位置开始报数

  for(i=0;i<n-1;++i){//循环一次出局一只猴子，共出局n-1只猴子

   for(j=0;j<m;++j){

    do{

     k=(k+1)%n;

    }while(hou[k]==0);//找到第一个非零元素（即还没出局的猴子）报数

   }

   printf("%d ",hou[k]);

   hou[k]=0;//报数到m的猴子出局

  }

  do{

   k=(k+1)%n;

  }while(hou[k]==0);//找到第一个非零元素（即还没出局的猴子）报数

  printf("\nLeave:%d\n",hou[k]);

 }

 printf("\nFinished!\n");

 getch();

 return 0;

}

以上就是关于C++编程：约瑟夫环问题。全部的内容，包括:C++编程：约瑟夫环问题。、急！求解C语言关于约瑟夫环的程序、C语言编程约瑟夫问题，程序出错等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！