假設(shè)有N個(gè)人決定選出一個(gè)領(lǐng)導(dǎo)人，方法如下：所有人排成一個(gè)圓圈，按順序數(shù)數(shù)，每隔第M個(gè)人出局，此時(shí)他兩邊的人靠攏重新形成圓圈。問(wèn)題是找出哪一個(gè)人將會(huì)是最后剩下的那個(gè)人。我們希望打印出所有人的出局順序和最后選出的領(lǐng)導(dǎo)人是哪一位。
這個(gè)問(wèn)題稱為約瑟夫問(wèn)題，可以利用鏈表解決。
代碼如下：
//約瑟夫問(wèn)題
#include<stdio.h>
#include<stdlib.h>
typedef struct node *link;
struct node { int item; link next; }; //定義結(jié)點(diǎn)
int main()
{
int i,N,M;
printf("Input N and M: "); //N表示共有N個(gè)人，M表示每隔第M個(gè)人要出局
scanf("%d%d",&N,&M);
link t = (link)malloc(sizeof(node)); //新建結(jié)點(diǎn)t
link x=t;
t->item = 1; t->next=t; //創(chuàng)建一個(gè)代表1號(hào)的單個(gè)節(jié)點(diǎn)的循環(huán)鏈表
for(i=2;i<=N;i++)
{
x=(x->next= (link)malloc(sizeof(node)));//將2~N號(hào)按序插到之前創(chuàng)建的單個(gè)節(jié)點(diǎn)的循環(huán)鏈表中
x->item=i; x->next=t;
}
while(x!= x->next) //如果不是最后一個(gè)節(jié)點(diǎn)，因?yàn)槭茄h(huán)鏈表，所以x!=x->next
{
for(i=1;i<M;i++) //則順著鏈表向前遍歷，數(shù)出M-1個(gè)元素
x=x->next;
printf("%d ",x->next->item);
x->next = x->next->next; //刪除第M個(gè)元素
N--; //節(jié)點(diǎn)數(shù)減1
}
printf("\n%d\n",x->item); //最后打印出最后一個(gè)節(jié)點(diǎn)
return 0;
}