高效实现Josephus算法
当前位置：以往代写 > C/C++ 教程 >高效实现Josephus算法

高效实现Josephus算法

2019-06-13

高效实现Josephus算法

高效实现Josephus算法

副标题#e#

Josephus界说：假设N小我私家编号1－N，围成圈。从1号开始报数，报到M时，此人退出，然 后继承从1开始报数，直到所有人退出为止。简朴的实现是利用轮回单链表，配置一个计数器 count，当count　== M ，删除当前节点，并将count重置。

假设M = 9,N = 5;

这里有两处处所可以优化：

1.当M>N时，取M`= M mod N，即M` = 9 % 5 = 4；报数到9与报数到4结果一致，但少遍历一次链表；

2.当M` > N / 2时，可逆 向走N – M’ + 1步，此时反向走比正向走间隔更近，但需要将数据布局配置为轮回双链 表。

对付M = 9,N = 5，实现优化后流程如下：

—

链表:1 2 3 4 5

N = 5
M` = 9 mod 5 = 4
M` = 4 > N / 2 = 2

反走(5 – 4 + 1) = 2 步，删除节点4，此时起点在节点3;

—

链表:1 2 3 5

N = 4
M` = 9 mod 4 = 1
M' = 1 < N / 2 = 2

正走1步，删除节点5，此时起点在节点3;

—

链 表:1 2 3

N = 3
M` = 9 mod 3 = 0
M` = 0 < N / 2 = 1

正走0步，删除节点3，此时起点在节点2;

—

链表:1 2

N = 2
M` = 9 mod 2 = 1
M` = 1 = N / 2 = 1


#p#副标题#e#

正 走1步，删除节点1，此时起点在节点2;

—

链表:2

N = 1
M` = 9 mod 1 = 0
M` = 0 = N / 2 = 0

正走0步，删除节点2，此时 链表空;

算法C实现：

#include <stdio.h>
#include "dlinkedlist.h"
#define SIZE 5
#define N SIZE
#define M 9
static List init();
void print(List l);
void process(List l);
int main()
{
　　　　List josephus = init();
　　　　print (josephus);
　　　　process(josephus);
　　　　return 0;
}
/* 初始化链表 */
static List init()
{
　　　　int i;
　　　　 List josephus = CreateList(1);
　　　　Position p = josephus;
　　　　 for (i = 2; i <= SIZE; i++)
　　　　{
　　　　　　　　Insert(i, josephus, p);
　　　　　　　　p = NextPosition(p);
　　　　}
　　 　　return josephus;
}
/* 打印链表 */
void print(List l)
{
　　　　if (l == NULL)
　　　　　　　　return;
　　　　printf ("%d ",Retrieve(l));
　　　　Position p = NextPosition(l);
　 　　　while (p != l)
　　　　{
　　　　　　　　printf("%d ",Retrieve(p));
　　　　　　　　p = NextPosition(p);
　　　　}
　　　　printf("\n");
}
/* Josephus处理惩罚 */
void process(List l)
{
　　　　int n = N;
　　　　int m = M % n;
　　　　int i;
　　　　Position p = l;
　　　　while (n > 1)
　 　　　{
　　　　　　　　if (m > n / 2)
　　　　　　　　{
　　　 　　　　　　　　　for (i = 0; i < n - m + 1; i++)
　　　　　　　　　　　 　　　　　p = PreviousPosition(p);
　　　　　　　　}
　　　　　　　　 else
　　　　　　　　{
　　　　　　　　　　　　for (i = 0; i < m; i++)
　　　　　　　　　　　　　　 p = NextPosition(p);
　　　　　　　　 }
　　　　　　　　p = PreviousPosition(p);
　　　　　　　　printf ("%d out\n",Retrieve(NextPosition(p)));
　　　　　　　　Remove (NextPosition(p), &l);
　　　　　　　　n--;
　　　　　　　　m = M % n;
　　　　　　　　printf("current: ");
　　　　　　　　 print(l);
　　　　}
}

#p#副标题#e#

测试功效：

1 2 3 4 5
4 out
current: 1 2 3 5
5 out
current: 1 2 3
3 out
current: 1 2
1 out
current: 2

这里给出轮回双链表数据布局 ADT和实现

假定链表不带哨兵节点。

dlinkedlist.h
typedef int ElementType;
#ifndef DLINKEDLIST_H_INCLUDED
#define DLINKEDLIST_H_INCLUDED
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
List CreateList (ElementType X);
void DisposeList(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
void Remove(Position P, List * L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position NextPosition(Position P);
Position PreviousPosition (Position P);
ElementType Retrieve(Position P);
#endif // DLINKEDLIST_H_INCLUDED
　　
fatal.h
#ifndef FATAL_H_INCLUDED
#define FATAL_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#define Error(Str)　　　　　　　　FatalError(Str)
#define FatalError(Str)　　 fprintf(stderr, "%s\n", Str), exit(1)
#endif // FATAL_H_INCLUDED
　　
dlist.c
#include "dlinkedlist.h"
#include "fatal.h"
struct Node
{
　　　　ElementType Element;
　　　　Position Next;
　　　　 Position Prev;
};
List CreateList(ElementType X)
{
　　　　 List L;
　　　　L = malloc(sizeof(struct Node));
　　　　if(L == NULL)
　　　　　　　　FatalError("Out of space!!!");
　　　　L- >Next = L->Prev = L;
　　　　L->Element = X;
　　　　return L;
}
void DisposeList(List L)
{
　　　　if(L->Next != L)
　　　　　　　　DeleteList(L);
　　　　free(L);
}
/* Return true if L is empty */
int IsEmpty(List L)
{
　　　　return L == NULL;
}
/* Return true if P is the last position in list L */
/* Parameter L is unused in this implementation */
int IsLast(Position P, List L)
{
　　　　return P == L;
}
/* Return Position of X in L; NULL if not found */
Position Find(ElementType X, List L)
{
　　　 　if (L->Element == X)
　　　　　　　　return L;
　　　　Position P;
　　　　P = L->Next;
　　　　while(P != L && P- >Element != X)
　　　　　　　　P = P->Next;
　　　　if (P == L) //not found
　　　　　　　　P = NULL;
　　　　return P;
}
/* Delete from a list */
/* Cell pointed to by P->Next is wiped out */
/* Assume that the position is legal */
void Delete(ElementType X, List L)
{
　　　　Position P;
　　　　P = Find(X, L);
　　　　if (P != NULL)
　　　　　　　　Remove(P, &L);
}
void Remove (Position P, List * L)
{
　　　　if(P == *L)
　　　　{
　　　 　　　　　if ((*L)->Next == *L)
　　　　　　　　{
　　　　　　　　　 　　　free(*L);
　　　　　　　　　　　　*L = NULL;
　　　　　　　　　　 　　return;
　　　　　　　　}
　　　　　　　　*L = (*L)->Next;
　　　　}
　　　　P->Prev->Next = P->Next;
　　　　P->Next ->Prev = P->Prev;
　　　　free(P);
}
/* Insert (after legal position P) */
/* Tailer implementation assumed */
/* Parameter L is unused in this implementation */
void Insert(ElementType X, List L, Position P)
{
　　　　Position TmpCell;
　　　　TmpCell = malloc(sizeof (struct Node));
　　　　if(TmpCell == NULL)
　　　　　　　　FatalError ("Out of space!!!");
　　　　TmpCell->Element = X;
　　　 　TmpCell->Next = P->Next;
　　　　P->Next->Prev = TmpCell;
　　　　TmpCell->Prev = P;
　　　　P->Next = TmpCell;
}
void DeleteList(List L)
{
　　　　Position P, Tmp;
　　　　P = L->Next;　　/* Tailer assumed */
　　　　L->Next = L;
　　　　L- >Prev = L;
　　　　while(P != L)
　　　　{
　　　　　　　　Tmp = P->Next;
　　　　　　　　free( P );
　　　　　　　　P = Tmp;
　　　　}
}
Position NextPosition(Position P)
{
　　　　 return P->Next;
}
Position PreviousPosition(Position P)
{
　　　　return P->Prev;
}
ElementType Retrieve(Position P)
{
　　　　return P->Element;
}

#p#副标题#e#

这里要留意的是函数Remove()

#p#分页标题#e#

void Remove(Position P, List * L)
{
　　　　if(P == *L)
　　　　{
　　　　　　　　if ((*L)->Next == *L)
　　　　　　　　 {
　　　　　　　　　　　　free(*L);
　　　　　　　　　　　　*L = NULL;
　　　　　　　　　　　　return;
　　　　　　　　}
　　　　　 　　　*L = (*L)->Next;
　　　　}
　　　　P->Prev->Next = P- >Next;
　　　　P->Next->Prev = P->Prev;
　　　　free(P);
}

List自己是一个指针，而这里选择List的指针，即指针的指针作为行参， 目标是当删除的节点是首元节点时，需要修改指针的值，即地点，所以通报指针的指针。就 好好比果需要修改int的值，则行参通报int *；同样假如需要修改int *的值，则行参通报 int **。

    关键字：

在线提交作业