约瑟夫双向生死游戏c语言代码,约瑟夫双向生死游戏

说明

约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上，正向计数后反向计数，然后再正向计数。具体描述如下：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，顺时针依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，逆时针数到第5人，将他投入大海，然后从他逆时针的下一个人数起，顺时针数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。程序运行时可以输入任意的旅客，可以自己制定规则，输入顺时针扔第几个、逆时针扔第几个、从第几个开始扔，并按被扔的顺序显示扔下去的位置和最后幸存者的名单。

链表实现

设计思想

用双向循环链表实现。定义一个链表结点的结构体，包含整形的结点序号number、前驱指针pre、后继指针next，设立表头phead与表尾pend。定义一个创建链表的函数，能够手动输入船上的人数，实现链表的插入，创建链表。创建时新建一个结点ps，将ps的前驱指针和后继指针都设为空。然后手动输入船上的人，以0表示结束。然后进入循环，当ps->number不为0时进行循环，如果是空表，则将头指针和尾指针都指向当前结点。如果不是空表，则采用尾插法，使尾指针的下一个为该结点，该结点的前驱为尾指针，然后将尾指针指向该结点。循环结束后连接表头表尾从而构成双循环链表。定义一个扔人的函数，实现链表结点的删除。手动输入顺时针扔几个，逆时针扔几个，总共扔几个。先通过一个循环定位到开始扔的起点，然后设立一个循环，通过循环定位要删除的结点，如果恰好要删除头结点则要更新头结点，如果恰好要删除尾节点则要更新尾节点，然后将该结点的后继的前驱指向该结点的前驱，该结点的前驱的后继指向该结点的后继，死亡人数加一。然后执行另一方向的程序，直到删除的结点数等于输入的扔的人数的总数循环结束。最后打印当前链表中的结点数，表示幸存者。

如果被删除的结点恰好是头结点或尾节点，删除结点后头或尾指针可能会丢失，所以应先判断删除的结点是否是头结点或尾节点，如果是头结点则应将头结点指向该结点的下一个，如果是尾节点则应将尾节点指向该结点的前一个。

因为删除结点是顺时针删一次，逆时针删一次，而我采用while循环，当被扔下去的人数不等于设定的人数时进行循环，而每一次循环都会进行两次操作，即顺时针删一次，逆时针删一次。所以出现了顺时针删一次后，被扔下去的人数已经等于设定的人数了，却还会再进行一次逆时针删除的操作。所以在每一次删除操作后都进行一次判断，如果被扔下去的人数已经等于设定的人数了就终止循环。

因为问题要求的是在顺时针扔完之后，要从这个人的下一个人数起，在逆时针扔完之后，要从这个人的前一个人数起。所以在顺时针删除当前结点后，负责定位的的指针要移向下一个结点，在逆时针删除完当前结点后，负责定位的指针要移向前一个结点。

代码及运行

#include

using namespace std;

int count=0;//链表的个数

typedef struct node

{

int number;

struct node *pre;

struct node *next;

}node;

node *pend; //头

node *phead; //尾

void Create_List()//创建链表；

{

node *ps=new node;

ps->next=NULL;

ps->pre=NULL;

cout<

cin>>ps->number;

while(ps->number!=0)

{

if(!phead)//空表的插入；

{

phead=ps;

pend=ps;

}

else

{

pend->next=ps;

ps->pre=pend;

pend=ps;

}

ps=new node;

ps->next=NULL;

ps->pre=NULL;

cin>>ps->number;

count++;

}

pend->next=phead;//连接表头表尾；

phead->pre=pend;

}

void throw_list(int Cwise,int aCwise,int start,int die_num)

{

int d=0;

node *p=new node;

p=phead;

for(int i=1;i

{

p=phead->next;

}

while(d!=die_num)//扔人

{

for(int i=1;i

{

p=p->next;

}

if(phead->number==p->number)//保证头

phead=phead->next;

else if(pend->number==p->number)

pend=pend->pre;

cout<number<

p->next->pre=p->pre;

p->pre->next=p->next;

p=p->next;

d++;

if(d==die_num)

break;

for(int i=1;i

{

p=p->pre;

}

if(phead->number==p->number)//保证头

phead=phead->next;

else if(pend->number==p->number)

pend=pend->pre;

cout<number<

p->next->pre=p->pre;

p->pre->next=p->next;

p=p->pre;

d++;

if(d==die_num)

break;

}

cout<

p=phead;

for(int i=1;i<=count-d;i++)

{

cout<number<

p=p->next;

}

cout<

}

int main()

{

int p_num,Cwise,aCwise,start,die_num;

Create_List();

cout<

cout<

cin>>Cwise;

cout<

cin>>aCwise;

cout<

cin>>start;

cout<

cin>>die_num;

throw_list(Cwise,aCwise,start,die_num);

}

顺序表实现

设计思想

定义一个顺序表，包含初始化、返回链表长度、返回链表元素、定位、删除、插入、打印七个功能函数和储存元素的数组及表示数组元素个数的变量。初始化直接使count为0.返回长度即返回count的值。取第i个元素的值即返回data[i-1]。定位即通过循环判断，如果data[i]==x，即返回i+1。插入即找到要插入的位置，将后面的元素向后移，然后将该元素插入，count 加一。打印即通过循环打印当前顺序表中的元素。定义一个游戏的函数，通过循环创建链表。然后按照规则对顺序表进行删除，通过tag变量定位要删除的元素，打印死亡名单和幸存者名单

顺序表里从哪一点开始删除不好定位，所以定义一个变量tag，在循环开始前利用tag=start+Cwise-1定位到要删除的位置。

定义的顺序表里没有循环，当顺时针数到结尾时不能接着数第一个结点，当逆时针数到头时不能接着数最后一个结点。所以利用tag=tag-aCwise+1;if(tag<1)tag=tag+L.length()，判断如果tag小于1了，即表示需要逆时针从后接着数起，所以tag加上当前顺序表的长度就定位到了应该删除的位置。利用tag=tag-1+Cwise-1;if(tag>L.length())tag=tag-L.length()，判断如果tag大于当前顺序表长度，即表示需要顺时针从头接着数起，所以tag减去当前顺序表的长度就定位到了应该删除的位置。

代码及运行

#include

using namespace std;

class list

{

public:

void List();

int length()const;

int get_element(const int i);

int locate(const int x)const;

void insert(const int i,const int x);

void delete_element(const int i);

void print();//打印

private:

int data[100];

int count;

};

void list::List()

{

count=0;

}

int list::length()const

{

return count;

}

int list::get_element(const int i)

{

return data[i-1];

}

int list::locate(const int x)const

{

for(int i=0;i

{

if(data[i]==x)

return i+1;

else

return -1;

}

}

void list::insert(const int i,const int x)

{

for(int j=count-1;j>=i-1;j--)

{

data[j+1]=data[j];

}

data[i-1]=x;

count++;

}

void list::delete_element(const int i)

{

for(int j=i+1;j<=length();j++)

{

data[j-2]=data[j-1];

}

count--;

}

void list::print()

{

for(int i=0;i

cout<

}

void play(list L,int number,int Cwise,int aCwise,int start,int die_num)//游戏

{

int d=0;

int tag;//用来确定扔谁

L.List();

for(int i=1;i<=number;i++)//人被安排在船上

L.insert(i,i);

tag=start+Cwise-1;//开始扔人

while(d!=die_num)

{

cout<

L.delete_element(tag);

d++;

if(d==die_num)

break;

tag=tag-aCwise+1;

if(tag<1)

tag=tag+number;

cout<

L.delete_element(tag);

d++;

if(d==die_num)

break;

tag=tag-1+Cwise-1;

if(tag>L.length())

tag=tag-L.length();

}

cout<

L.print();

}

int main()

{

list L;

int number,Cwise,aCwise,start,die_num;

cout<

cout<

cin>>number;

cout<

cin>>Cwise;

cout<

cin>>aCwise;

cout<

cin>>start;

cout<

cin>>die_num;

play(L,number,Cwise,aCwise,start,die_num);

}

标签：pre,ps,结点,生死,int,number,约瑟夫,链表,双向

来源： https://www.cnblogs.com/Qi-Lin/p/12221279.html