【算法练习三】约瑟夫环

一、问题描述

N个人围城一桌(首位相连),约定从1报数,报到数为k的人出局,然后下一位又从1开始报,以此类推。最后留下的人获胜。(有很多类似问题,如猴子选代王等等,解法都一样)

二、思路分析

(1)可将人的顺序简单编号,从1到N;

(2)构造一个循环链表,可以解决首位相连的问题,同时如果将人的编号改为人名或者其他比较方便

(3)将人的编号插入到结构体的Data域;

(4)遍历人的编号,输出参与的人的编号;

(5)开始报数,从头报数,报到k的人出局(删除次结点),(输出出局的人更人性化)避免浪费,可释放次结点。直到人数只有一个人时,退出循环。输出获胜的人。

(6)注意:在写删除删除结点的函数时都是针对K>=2的情况处理,所以要考虑k=1的情况,要是出局的密码为1时则最后一个获胜。

三、算法实现

(1)构造结构体

                  typedef struct Node{

int Num;//Data域

struct Node *next;

}JoseNode, *PNode, *HNode;//PNode为指针变量,HNode为头结点

(2)得到头结点

                HNode h = ((HNode)malloc(sizeof(JoseNode)));

(3)初始化循环单链表

             int JoseInit(HNode *h)

{

if (!h)

{

printf(“初始化链表错误!\n”);

return 0;

}

(*h)->next = (*h);//循环单链表

return 1;

 

}

(4)插入算法

            int JoseInsert(JoseNode *h, int pos, int x)

{

PNode p=h,q;

int i=1;

if (pos == 1)/*尾插法*/

{

p->Num = x;

p->next = p;

return 1;

}

while(i<pos-1)

{

p=p->next;

i++;

}

q=(PNode)malloc(sizeof(JoseNode));

q->Num=x;

q->next=p->next;

p->next=q;

return 1;

}

 

 

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

{

JoseInsert(h, i, i);

}

(4)遍历算法

void TraverseList(HNode h, int M)

{

int i = 0;

PNode p = h;

printf(“参与的人的编号为:\n”);

while (i<M)

{

printf(“%d\t”, p->Num);

p = p->next;

i++;

}

printf(“\n”);

}

 

(5)找到出局的人,并删除(删除算法)

  if(k > 1)//考虑出局密码为1时的情况

JoseDelete(h, N, k);

else

{

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

printf(“出局的人为:%d号\n”,i);

printf(“***************获胜者为:%d号***************”,N);

}

 

 

int JoseDelete(HNode h, int M, int k)

{       int i;

PNode p=h,q;

while(M>1)//循环终止条件,只剩一个人时

{

for(i=1;i<k-1;i++)//此处为i<k-1,因为要找到的是出局的人的前一个结点①

{

p=p->next;

}

 

q=p->next;

p->next=q->next;

printf(“出局的人为:%d号\n”,q->Num);

free(q);//释放次结点

 

p=p->next;//与①处的相对应,①处找到的只是出局的人的前一个结点

M–;

}

printf(“***************获胜者为:%d号***************”,p->Num);

return 1;

}

四、完整代码

#include <stdio.h>
#include <malloc.h>

/*构建结构体*/
typedef struct Node{
int Num;
struct Node *next;
}JoseNode, *PNode, *HNode;

/**********初始化循环单链表*********/
int JoseInit(HNode *h)
{
if (!h)
{
printf(“初始化链表错误!\n”);
return 0;
}
(*h)->next = (*h);//循环单链表
return 1;

}

/*************单链表插入操作**********/
int JoseInsert(JoseNode *h, int pos, int x)
{
PNode p=h,q;
int i=1;
if (pos == 1)/*尾插法*/
{
p->Num = x;
p->next = p;
return 1;
}
while(i<pos-1)
{
p=p->next;
i++;
}
q=(PNode)malloc(sizeof(JoseNode));
q->Num=x;
q->next=p->next;
p->next=q;
return 1;
}

/*遍历*/
void TraverseList(HNode h, int M)
{
int i = 0;
PNode p = h;
printf(“参与的人的编号为:\n”);
while (i<M)
{
printf(“%d\t”, p->Num);
p = p->next;
i++;
}
printf(“\n”);
}
/**************出局函数****************/

int JoseDelete(HNode h, int M, int k)
{ int i;
PNode p=h,q;
while(M>1)
{
for(i=1;i<k-1;i++)
{
p=p->next;
}

q=p->next;
p->next=q->next;
printf(“出局的人为:%d号\n”,q->Num);
free(q);

p=p->next;
M–;
}
printf(“***************获胜者为:%d号***************”,p->Num);
return 1;
}

/***************************************/
int main()
{
int i;//计数器
int N;//参与的人数
int k;//报数密码
printf(“请输入参与人数:”);
scanf(“%d”,&N);
printf(“请输入出局密码:”);
scanf(“%d”,&k);

/**************得到头结点****************/
HNode h = ((HNode)malloc(sizeof(JoseNode)));

/***************初始化单链表************/
JoseInit(&h);

/******将编号插入到循环单链表中******/
for (i = 1; i <=N; i++)
{
JoseInsert(h, i, i);
}
/**************遍历单链表***************/
TraverseList(h,N);

/***************出局函数************/
if(k > 1)
JoseDelete(h, N, k);
else
{
for(i = 1; i < N; i++)
printf(“出局的人为:%d号\n”,i);
printf(“***************获胜者为:%d号***************”,N);
}

printf(“\n”);
printf(“\n”);
return 0;
}

五、实验验证

发表评论

电子邮件地址不会被公开。 必填项已用*标注