著名的Josephus問題
據說著名猶太歷史學家 Josephus有過以下的故事：在羅馬人占領喬塔帕特後，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧願死也不要被人抓到，於是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然後再由下一個重新報數，直到所有人都自殺身亡為止。
然而Josephus 和他的朋友並不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，於是逃過了這場死亡遊戲。
Josephus問題的C程式
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE 1
typedef int DataType; /* 定義元素類型為整型，也可定義為其他類型 */
struct Node; /* 單鍊表結點類型 */
typedef struct Node *PNode; /* 結點指針類型 */
struct Node /* 單鍊表結點結構 */
{
DataType info;
PNode link;
};
struct LinkList /* 單鍊表類型定義 */
{
PNode head; /* 指向單鍊表中的第一個結點 */
};
typedef struct LinkList *PLinkList; /* 單鍊表類型的指針類型 */
int insert_clink( PLinkList pclist, DataType x, PNode p )
/* 在pclist所指的循環單鍊表中最後一個結點p的後面插入元素x */
{
PNode q;
q = (PNode)malloc( sizeof( struct Node ) );
if( q == NULL )
{
printf( "Out of space!!! \n" );
return ( FALSE );
}
else
{
q->info = x;
q->link = pclist->head->link;
p->link = q;
return ( TRUE );
}
}
PLinkList createNullList_clink( void )
/* 創建帶頭結點的空循環鍊表*/
{
PLinkList pclist;
PNode p;
pclist = (PLinkList)malloc( sizeof( struct LinkList ) );
if( pclist != NULL )
{
p = (PNode)malloc(sizeof(struct Node)); /* 申請頭結點 */
if (p!=NULL)
{
pclist->head = p;
p->link = NULL;
}
else
pclist->head = NULL;
}
else
printf( "Out of space!!\n" );
return pclist;
}
PNode next_clink( PNode p )
{
return p->link;
}
PNode find_clink( PLinkList pclist, int i )
/* 在帶有頭結點的循環單鍊表clist中求第i(i>0)個結點的位置 */
/* 當表為空循環單鍊表時，返回值為NULL */
{
PNode p;
int j;
p = pclist->head->link;
if (i<1)
{
printf("The value of i=%d is not reasonable.\n",i);
return NULL;
}
if ( p == NULL )
return NULL;
for ( j=1;j<i;j++ )
p = p->link;
return p;
}
void josephus_clink( PLinkList pclist, int s,int m )
{
PNode p,pre,tp;
int i;
p = find_clink(pclist,s); /* 找第s個結點 */
if (p==NULL) /* 無第s個結點 */
{
printf(" s = %d not exit.\n ",s);
exit(1);
}
while (pclist->head->link!=NULL)
{
for (i=1;i<m;i++) /* 找第m個結點 */
{
pre = p;
p = p->link;
}
printf(" out element: %i \n",p->info); /* 輸出該結點 */
if (pre!=p) /* 當表中元素個數大於1時，刪除該結點 */
{
pre->link = p->link;
tp = p;
p = p->link;
free(tp);
}
else /* 當表中元素個數等於1時，將頭結點指針置空 */
{
free(pre);
pclist->head->link = NULL;
}
}
free(pclist->head);
free(pclist);
}
main( )
{
PLinkList jos_clist;
PNode p;
int i,n,s,m,k;
printf("\n please input the values of n = ");
scanf("%d",&n);
printf(" please input the values of s = ");
scanf("%d",&s);
printf(" please input the values of m = ");
scanf("%d",&m);
jos_clist = createNullList_clink( ); /* 創建空循環鍊表 */
if (jos_clist==NULL || jos_clist->head==NULL) return ( FALSE);
p = jos_clist->head ;
for( i = 1; i <= n; i++ ) /* 創建循環鍊表 */
{
k = insert_clink( jos_clist,i, p );
if (k==FALSE) return(FALSE);
p = next_clink( p );
}
josephus_clink(jos_clist,s,m);
return (TRUE);
}
