聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

用单循环链表来玩一下约瑟夫环游戏

2012-06-01 21:00 浏览: 1819415 次 我要评论(0 条) 字号:


一群小孩围成一圈,每个小孩都会带有一个随机的密码。然后设定一个数m,从第一个小孩数起,数到第m个的时候,该小孩离开。小孩离开时,其携带的密码将更新这个m值,顺序往下数的第m个小孩会继续出列。依次这样数下去,最后一个小孩是胜利者,问:胜利者是第几个小孩?

这就是大家所熟知的约瑟夫环

循环链表天然地很适合解决这个问题,下面用C语言实现了一下:


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define OK 1;
#define ERROR 0;
#define OVERFLOW -2;

typedef int ElemType;
typedef struct Node
{
ElemType num;
ElemType password;
struct Node *next;
}Node;
typedef struct Node CLinkList; /* 定义LinkList */

void main(){
int num=10;
int m=10;
CLinkList *L;
/* 输入约瑟夫环的总结点数*/
printf("有多少个小孩参与游戏(设定小于100):");
scanf("%d",&num);
if(num<=0||num>=100){
/* 如果输入的数字超出范围,就默认总结点数为10 */
printf("你的输入不符合,下面采用默认数字10n");
num=10;
}
/* 输入第一个需要出列的数字 */
printf("第一个报到哪个数必须出列 (设定小于100):");
scanf("%d",&m);
if(m<=0||m>=100){
printf("你的输入不符合,下面采用默认数字10n");
m=10;
}
InitList(L);
Creat_Joseph(L,num);
ListTraverse(L,num);
Joseph_Run(L,m);
}

/* 释放删除的结点 */
void FreeNode(CLinkList *p){
CLinkList *temp=p;
while(temp->next!=p)
temp=temp->next;
temp->next=p->next;
printf("编号%3d的小孩离队了,他携带的密码是%3dn",p->num, p->password);
free(p);
}

/* 初始化结点 */
int InitList(CLinkList *l){
l=(CLinkList *) malloc (sizeof(CLinkList));
if(!l)
return OVERFLOW;
return OK;
}
/* 创建每个结点携带的密码 */
void Creat_Joseph(CLinkList *l,int length){
int i;
CLinkList *p=l;
l->next=l;
l->num=1;
srand( (unsigned)time(NULL));
l->password=rand()%(length+3)+1;
printf("以下小孩(约瑟夫环结点)携带的密码随机生成的:n");
/* 打印约瑟夫环的第一个结点 */
printf("小孩编号: %3d 带的密码: %3dn",l->num,l->password);
for(i=1;i<length;i++){
CLinkList* temp=(CLinkList*)malloc (sizeof(CLinkList));
p->next=temp;
temp->next=l;
temp->num=i+1;
temp->password=rand()%(2*length)+1;
/* 打印除第一个结点外的其它结点 */
printf("小孩编号: %3d 带的密码: %3dn",temp->num,temp->password);
p=p->next;
}
}

void ListTraverse(CLinkList *L,int length)
{
int i;
CLinkList *p=L->next;
for(i = 0; i < length; i++)
{
printf("%d:%d ",p->num, p->password);
p=p->next;
}
printf("n");
return OK;
}

/* 根据结点携带的密码释放下一个结点 */
void Joseph_Run(CLinkList *l, int m){
int i,k;
CLinkList *temp,*p;
if(l->next==l)
/* 打印最后一个结点 */
printf("最后编号 %d 的小孩获胜!",l->num);
else{
temp = l;
for(i=1; i<m; i++)
{
printf("编号%3d的小孩安全n",temp->num);
temp=temp->next;
}
p=temp->next;
k=temp->password;
/* 释放中招的结点 */
FreeNode(temp);
/* 递归 */
Joseph_Run(p,k);
}
}

程序运行结果:


有多少个小孩参与游戏(设定小于100):6
第一个报到哪个数必须出列 (设定小于100):8
以下小孩(约瑟夫环结点)携带的密码随机生成的:
小孩编号: 1 带的密码: 5
小孩编号: 2 带的密码: 9
小孩编号: 3 带的密码: 12
小孩编号: 4 带的密码: 2
小孩编号: 5 带的密码: 5
小孩编号: 6 带的密码: 2
2:9 3:12 4:2 5:5 6:2 1:5
编号 1的小孩安全
编号 2的小孩安全
编号 3的小孩安全
编号 4的小孩安全
编号 5的小孩安全
编号 6的小孩安全
编号 1的小孩安全
编号 2的小孩离队了,他携带的密码是 9
编号 3的小孩安全
编号 4的小孩安全
编号 5的小孩安全
编号 6的小孩安全
编号 1的小孩安全
编号 3的小孩安全
编号 4的小孩安全
编号 5的小孩安全
编号 6的小孩离队了,他携带的密码是 2
编号 1的小孩安全
编号 3的小孩离队了,他携带的密码是 12
编号 4的小孩安全
编号 5的小孩安全
编号 1的小孩安全
编号 4的小孩安全
编号 5的小孩安全
编号 1的小孩安全
编号 4的小孩安全
编号 5的小孩安全
编号 1的小孩安全
编号 4的小孩安全
编号 5的小孩安全
编号 1的小孩离队了,他携带的密码是 5
编号 4的小孩安全
编号 5的小孩安全
编号 4的小孩安全
编号 5的小孩安全
编号 4的小孩离队了,他携带的密码是 2
最后编号 5 的小孩获胜!
Process returned 23 (0x17) execution time : 8.506 s
Press any key to continue.


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复