Posted on 2012-08-17 00:14
hoshelly 阅读(1040)
评论(0) 编辑 收藏 引用 所属分类:
Programming 、
DS && Algorithm
假设有N个人决定选出一个领导人，方法如下：所有人排成一个圆圈，按顺序数数，每隔第M个人出局，此时他两边的人靠拢重新形成圆圈。问题是找出哪一个人将会是最后剩下的那个人。我们希望打印出所有人的出局顺序和最后选出的领导人是哪一位。
这个问题称为约瑟夫问题，可以利用链表解决。
代码如下：
//约瑟夫问题
#include<stdio.h>
#include<stdlib.h>
typedef struct node *link;
struct node { int item; link next; }; //定义结点
int main()
{
int i,N,M;
printf("Input N and M: "); //N表示共有N个人，M表示每隔第M个人要出局
scanf("%d%d",&N,&M);
link t = (link)malloc(sizeof(node)); //新建结点t
link x=t;
t->item = 1; t->next=t; //创建一个代表1号的单个节点的循环链表
for(i=2;i<=N;i++)
{
x=(x->next= (link)malloc(sizeof(node)));//将2~N号按序插到之前创建的单个节点的循环链表中
x->item=i; x->next=t;
}
while(x!= x->next) //如果不是最后一个节点，因为是循环链表，所以x!=x->next
{
for(i=1;i<M;i++) //则顺着链表向前遍历，数出M-1个元素
x=x->next;
printf("%d ",x->next->item);
x->next = x->next->next; //删除第M个元素
N--; //节点数减1
}
printf("\n%d\n",x->item); //最后打印出最后一个节点
return 0;
}