约瑟夫生死游戏
前面，我们学习了线性表的存储结构，基于数组的顺序存储和基于链表的链式存储，今天呢，我们对所学的知识做一个练习-约瑟夫生死游戏，这个游戏是做什么的呢？
设有n个人围坐在圆桌周围，现从某个位置 i 上的人开始报数，数到 m 的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus 问题。
例如：当n=8,m=4,i=1时，得到的新序列为：
4，8，5，2，1，3，7，6
编写程序选择顺序存储方式模拟整个过程，并依次输出出列的各人的编号。
游戏的大意就是这样的，现在我们来看一下代码实现，首先是基于数组的顺序存储
#include <stdio.h>
#include <stdlib.h>int main(int argc, char *argv[])
{int n;//总人数int m;//当数到m时出列int i;//位置i上的人开始报数scanf("%d%d%d",&n,&m,&i);int *peoples = (int*)malloc(sizeof(int)*n);//创建长度为n的数组peoples int k;for(k=0;k<n;k++)//1表示未出列 0表示出列 peoples[k]=1; int curnum=n;//用于记录当前未出队的人数 int startnum=i-1;//从第startnum开始进行报数 int j=1;//用于记录当前的报数号 while(curnum>0){while(peoples[startnum]==0){startnum++;startnum%=n;}if(j==m){printf("%d ",startnum+1);peoples[startnum]=0;curnum--;j=1;startnum++;startnum%=n;continue;}j++;startnum++; startnum%=n; } return 0;
}下面是基于链表的链式存储，大家可以做下对比
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{int data;struct Node* next;
}Node;
Node *Find(Node*head,int i);
void Delete(Node *head,Node *p);
int main(int argc, char *argv[])
{int n;//人数int m;//每到m出一个人int i;//从第i个人开始scanf("%d%d%d",&n,&m,&i);//输入Node *head=(Node*)malloc(sizeof(Node));//头节点 Node *p=head;p->data=1;p->next=NULL;int j;Node *q;for(j=2;j<=n;j++){q=(Node*)malloc(sizeof(Node));q->data=j;q->next=p->next;p->next=q;p=q;}p->next=head;int k=1;//用于计数p=Find(head,i);while(p!=q){if(k==m){printf("%d ",p->data);k=1;q->next=p->next;free(p);p=q->next;}else{k++;q=p;p=p->next;}}printf("%d",p->data);return 0;
}Node *Find(Node*head,int i)
{int j;Node*p=head;for(j=1;j<i;j++){p=p->next;}return p;
}
约瑟夫生死游戏
前面，我们学习了线性表的存储结构，基于数组的顺序存储和基于链表的链式存储，今天呢，我们对所学的知识做一个练习-约瑟夫生死游戏，这个游戏是做什么的呢？
设有n个人围坐在圆桌周围，现从某个位置 i 上的人开始报数，数到 m 的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus 问题。
例如：当n=8,m=4,i=1时，得到的新序列为：
4，8，5，2，1，3，7，6
编写程序选择顺序存储方式模拟整个过程，并依次输出出列的各人的编号。
游戏的大意就是这样的，现在我们来看一下代码实现，首先是基于数组的顺序存储
#include <stdio.h>
#include <stdlib.h>int main(int argc, char *argv[])
{int n;//总人数int m;//当数到m时出列int i;//位置i上的人开始报数scanf("%d%d%d",&n,&m,&i);int *peoples = (int*)malloc(sizeof(int)*n);//创建长度为n的数组peoples int k;for(k=0;k<n;k++)//1表示未出列 0表示出列 peoples[k]=1; int curnum=n;//用于记录当前未出队的人数 int startnum=i-1;//从第startnum开始进行报数 int j=1;//用于记录当前的报数号 while(curnum>0){while(peoples[startnum]==0){startnum++;startnum%=n;}if(j==m){printf("%d ",startnum+1);peoples[startnum]=0;curnum--;j=1;startnum++;startnum%=n;continue;}j++;startnum++; startnum%=n; } return 0;
}下面是基于链表的链式存储，大家可以做下对比
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{int data;struct Node* next;
}Node;
Node *Find(Node*head,int i);
void Delete(Node *head,Node *p);
int main(int argc, char *argv[])
{int n;//人数int m;//每到m出一个人int i;//从第i个人开始scanf("%d%d%d",&n,&m,&i);//输入Node *head=(Node*)malloc(sizeof(Node));//头节点 Node *p=head;p->data=1;p->next=NULL;int j;Node *q;for(j=2;j<=n;j++){q=(Node*)malloc(sizeof(Node));q->data=j;q->next=p->next;p->next=q;p=q;}p->next=head;int k=1;//用于计数p=Find(head,i);while(p!=q){if(k==m){printf("%d ",p->data);k=1;q->next=p->next;free(p);p=q->next;}else{k++;q=p;p=p->next;}}printf("%d",p->data);return 0;
}Node *Find(Node*head,int i)
{int j;Node*p=head;for(j=1;j<i;j++){p=p->next;}return p;
}
发布评论