Josephus （数学问题）

著名的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;

if(

{

printf( "Out of space!!! \n" );

return ( FALSE );

}

else

{

return ( TRUE );

}

}

PLinkList createNullList_clink( void )

/* 创建带头结点的空循环链表*/

{

PLinkList pclist;

PNode p;

if(

{

if (

{

}

else

}

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(

/* 当表为空循环单链表时，返回值为NULL */

{

PNode p;

int j;

if (

{

printf("The value ofis not reasonable.\n",i);

return NULL;

}

if (

return NULL;

for (

return p;

}

void josephus_clink( PLinkList pclist, int s,int m )

{

PNode p,pre,tp;

int i;

p = find_clink(pclist,s); /* 找第s个结点 */

if (

{

printf("

exit(1);

}

while (pclist->head->link!=NULL)

{

for (

{

}

printf(" out element:

if (

{

free(tp);

}

else /* 当表中元素个数等于1时，将头结点指针置空 */

{

free(pre);

}

}

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 = ");

printf(" please input the values of s = ");

printf(" please input the values of m = ");

if (

for(

{

if

}

josephus_clink(jos_clist,s,m);

return (TRUE);

}