ジョセフループを実現するアルゴリズム
一)配列実装を採用する(数字が比較的小さい場合に適用する):
二)チェーンテーブルを採用して実現する(一般的に適用する):
#include <stdio.h>
void josephus(const unsigned int nNum, const unsigned int nDistance, const unsigned int nBegin)
{
if(nNum <= 0 || nDistance <= 0 || nBegin <= 0)
return;
int i, j, *nPassword = new int [nNum];
for(i = 0;i < nNum;i ++)
{
nPassword[i] = nDistance;//
}
int k = 0, iStart = nBegin;// ,
for(i = 0;i < nNum;i ++)
{
j = 1;
while(j < iStart)
{
while(nPassword[k] == 0)
{
k = (k + 1) % nNum;
}
j ++;
k = (k + 1) % nNum;
}
while(nPassword[k] == 0)
{
k = (k + 1) % nNum;
}
printf("%3d ",k + 1);
iStart = nPassword[k];
nPassword[k] = 0;
}
}
void main()
{
josephus(100,3,1);
}
二)チェーンテーブルを採用して実現する(一般的に適用する):
// :
#include <stdio.h>
#include <malloc.h>
struct node
{
int nNum,nPassword;
struct node * next;
};
typedef struct node * LNode;
LNode CreateList(const int num,const int nPwd)
{
int i;
LNode head = NULL,p = NULL,q = NULL;
for(i = 1; i <= num; ++ i)
{
p = (LNode)malloc(sizeof(struct node));
p->nNum = i;
p->nPassword = nPwd;
if(NULL == head)
{
head = p;
}
else
{
q->next = p;
}
q = p;
}
q->next = head;
return q;
}
void josephus(const int num,const int nPwd,const int nBegin)
{
LNode q = CreateList(num,nPwd);
LNode p = q->next;
int iNum = num,iCall = nBegin;
while(iNum --)
{
for(int i = 0; i < iCall - 1; ++ i)
{
q = p;
p = p->next;
}
q->next = p->next;
iCall = p->nPassword;
printf("%3d ",p->nNum);
free(p);
p = q->next;
}
}
void main()
{
josephus(100, 3, 1);
}
// :
#include <stdio.h>
#include <malloc.h>
struct node
{
int nNum,nPassword;
struct node * next;
};
typedef struct node * LNode;
LNode CreateList(const int num,const int nPwd)
{
int i;
LNode head = NULL,p = NULL,q = NULL;
p = (LNode)malloc(sizeof(struct node));
p->nNum = 1;
p->nPassword = nPwd;
head = p;
for(i = 2; i <= num; i ++)
{
q = (LNode)malloc(sizeof(struct node));
q->nNum = i;
q->nPassword = nPwd;
p->next = q;
p = q;
}
q->next = head;
return q;
}
void josephus(const int num,const int nPwd,const int nBegin)
{
LNode q = CreateList(num,nPwd);
LNode p = q->next;
int iNum = num,iCall = nBegin;
while(iNum --)
{
for(int i = 0;i < iCall - 1; i ++)
{
q = p;
p = p->next;
}
q->next = p->next;
iCall = p->nPassword;
printf("%3d
",p->nNum);
free(p);
p = q->next;
}
}
void main()
{
josephus(100,3,1);
}