Posted on 2012-08-17 00:14
hoshelly 閱讀(1064)
評論(0) 編輯 收藏 引用 所屬分類:
Programming 、
DS && Algorithm
假設有N個人決定選出一個領導人，方法如下：所有人排成一個圓圈，按順序數(shù)數(shù)，每隔第M個人出局，此時他兩邊的人靠攏重新形成圓圈。問題是找出哪一個人將會是最后剩下的那個人。我們希望打印出所有人的出局順序和最后選出的領導人是哪一位。
這個問題稱為約瑟夫問題，可以利用鏈表解決。
代碼如下：
//約瑟夫問題
#include<stdio.h>
#include<stdlib.h>
typedef struct node *link;
struct node { int item; link next; }; //定義結(jié)點
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)); //新建結(jié)點t
link x=t;
t->item = 1; t->next=t; //創(chuàng)建一個代表1號的單個節(jié)點的循環(huán)鏈表
for(i=2;i<=N;i++)
{
x=(x->next= (link)malloc(sizeof(node)));//將2~N號按序插到之前創(chuàng)建的單個節(jié)點的循環(huán)鏈表中
x->item=i; x->next=t;
}
while(x!= x->next) //如果不是最后一個節(jié)點，因為是循環(huán)鏈表，所以x!=x->next
{
for(i=1;i<M;i++) //則順著鏈表向前遍歷，數(shù)出M-1個元素
x=x->next;
printf("%d ",x->next->item);
x->next = x->next->next; //刪除第M個元素
N--; //節(jié)點數(shù)減1
}
printf("\n%d\n",x->item); //最后打印出最后一個節(jié)點
return 0;
}