约瑟夫问题c语言

约瑟夫问题c语言

1、约瑟夫问题：Joseph问题的一种描述是：编号为1、2、……、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。
2、例程：

#include 
#include 
typedef int ElemType;
typedef struct LNode{
ElemType data;int num;
struct LNode *next;
}LNode,*LinkList;
void CreateList_L(LinkList *L,int n)
{ int i=0;
ElemType e;
LinkList p,q;
*L=(LinkList)malloc(sizeof(LNode));
(*L)-> next=NULL;(*L)-> data=n;
q=*L;
while(i { scanf("%d",&e);
p=(LinkList)malloc(sizeof(LNode));
p-> data=e;p-> num=i+1;
p-> next=NULL;
q-> next=p;
q=p;
i++;
}
p-> next=(*L)-> next;
}
void PrintList(LinkList L)
{ int i=0;
LinkList p;
p=L-> next;
while(i  data)
{
printf("%5d",p-> data);
p=p-> next;
i++;
}
printf("
");
}
void Put(LinkList *L)
{ int i,m;LinkList p,q;
printf("input a number:
");
scanf("%d",&m);
q=(*L)-> next;
while((*L)-> data)
{for(i=0;i {p=q;
q=q-> next;
}
printf("%5d",q-> num);
m=q-> data;
p-> next=q-> next;
free(q);
q=p-> next;
(*L)-> data=(*L)-> data-1;
}
}
void main()
{LinkList L;
int a;
printf("请输入人数:");
scanf("%d",&a);
printf("请输入密码:");
CreateList_L(&L,a);
printf("您输入的数字为:
");
PrintList(L);
Put(&L);
}

循环链表。

根据个人思维写的：已经在KEIL C中调试通过。
typedef unsigned char u8;
#define m 15
#define n 4
u8 a[m+1];
void main()
{
u8 i ,j ,k,ii,Rn,s,value;//itemp;
for(i=1;i<=m;i++)//给数组赋初值；
a[i]=i;
Rn=1;//i作为数组标识;
s=m;
while(s>1)
{
i=1;//i作为数组标识；

for(j=Rn;j {
if(j%n==0)
{
a[i]=0;
}
i++;
}
if((s+Rn)<=n)
{
while(j%n!=0)
{
j++;
}
a[j-s]=0;
}
i=1;
for(j=1;j<=s;j++)//j循环；将数组中为0的数清除并重新排列数组；
{
if(a[i]==0)
{
if(i==(s-ii)){ii++;break;}//如果是数组中最后一位数为0已过来的，则；
else
{for(k=i;ka[k]=a[k+1];
ii++;
i--;
j--;}
}
i++;
}
Rn=s%n+Rn;
if(Rn==n )
{
Rn=0;
}
else if(Rn>n)
Rn=Rn%n;

if((Rn==0)&&(s {
Rn=1;
}

s-=ii;
ii=0;
}
value=a[1];
while(1);
}

#include
#define size 100
void main()
{
int person[size];
int i, j;
int arrayLen;
int start, overNum;
int deleNum;
int name, total;
printf( "请输入圆桌上人的总数: " );
scanf( "%d", &arrayLen ); printf( "\n" );
if( ( arrayLen > size ) || ( arrayLen < 0 ) )
{
printf( "超出范围,请重新输入: " );
scanf( "%d", &arrayLen ); printf( "\n" );
};
printf( "请输入各个人的信息(整数): \n" );
for( i = 0; i < arrayLen; i++ )
{
scanf( "%d", &name );
person[i] = name;
}
printf( "你输入的数据的顺序为: \n" );
for( i = 0; i < arrayLen - 1; i++ )
printf( " %d ==>", person[i] );
printf( "%d \n", person[arrayLen - 1] );
printf( "你打算从第几个人开始? 请输入开始号: " );
scanf( "%d", &start );
printf( "\n" );
start = start - 1;
printf( "请输入相邻两出列人之间的间隔: " );
scanf( "%d", &overNum );
printf( "\n" );

total = arrayLen;
printf( "程序运行后,出列人的顺序为:\n\n" );
for( i = 0; i < total; i++ )
{
if ( arrayLen == 1 )
printf( "%d", person[0] );
else
{
deleNum = ( start + overNum - 1 ) % arrayLen;
printf( "%d ==> ", person[deleNum] );
for ( j = deleNum; j < arrayLen; j++ )
person[j] = person[j+1];
start = deleNum;
arrayLen = arrayLen - 1;
}
}
printf( "\n\n" );
}

从一本数据结构书上看到的用向量实现此问题：
void Josephus (Vector &P, int n, int s, int m)
{
//将人员编号存入向量P；
int k = 1;
for(int i = 0; i{P.Insert(k,i); k++;}
int s1 = s;
for(int j = n; j>=1; j--)
{
s1=(s1+m-1)%j;
if(s1== 0) s1 = j;
int w = P.Getnode(s1 - 1);
P.Remvoe(s1 - 1);
P.Insert(w,n-1);
}
}
以前学C语言的时侯写的，希望对你有用。