约瑟夫环问题-白红宇

约瑟夫环问题

阅读量：6271 次

发布时间：2019-06-22

本文共 14153 字，大约阅读时间需要 47 分钟。

Josephus问题的定义如下：假设n个人排成环形，且有以正整数m<=n。从某个制定的人开始，沿环报数，每遇到第m个人就让其出列，且报数进行下去。这个过程一直进行到所有人都出列为止。每个人出列的次序定义了整数1，2，...，n的(n, m)-Josephus排列。例如，(7,3)-Josephus排列为<3,6,2,7,5,1,4>。

a)假设m为整数。请描述一个O(n)时间的算法，使之对给定的整数n，输出(n, m)-Josephus排列。

b)假设m不是个常数。请描述一个O(nlgn)时间的算法，使给定的整数n和m，输出(n, m)-Josephus排列。

递归求解约瑟夫环

约瑟夫序列从0,1,2.....,N-1中报数为M-1的出列，从M开始又重新从1开始报数，这可以用典型的递归来求解，递归的具体过程如下图所示：

图片描述

不妨用$f(i)$表示问题规模$size=i$的时候，数的下标的排列，值得注意的是，从$size=i$问题规模递减为$size=i-1$的时候，同一个数的下标发生变化，其实是对应函数的映射，不妨用$f(i)$表示这种映射。

如上图所示，在Josephus排列中，满足

$f(i)=(f(i-1)+k) mod i$

根据这种算法，可以使用递归求解：

#include 
    
     using namespace std;int main(){  int N;  int M;  cin>>N;  cin>>M;  int result=0;  for(int i=2; i<=N;i++)    result=(result+M)%i;   //值得注意的是，这里的i表示规模，递推关系   //表示从i递推到i-1，问题规模数组大小   //最小就为1，所以i的初值为2  std::cout << "最后输出的元素是" <
     
      <

递归算法的局限性：用这样的递归算法，无法获得一个Josephus的(n,m)排列，我们只知道最后一个出队的人，在初始时候的下标，并不知道所有的人，分别什么时候出队。

使用循环链表输出

不删除结点的时候，我们需要给每一个节点加上status属性，判断这个结点是否已经处理过？

或者就采用最普通的删除结点的方式来处理。每当完成报数的时候，删除节点让报数的人退出Josephus环。

以下函数给出的是两种方式实现，一种在链表中不删除节点，一种要删除节点。

#include 
    
     using namespace std;#define n 30#define m 3#define LEN sizeof(struct circular_list)#define LEN_status sizeof(struct circular_list_status)struct circular_list{  int key;  //存储数据  circular_list *next;};struct circular_list_status{  int key;  bool status;  //用来存储该节点的状态，出队没有？  circular_list_status *next;  circular_list(int k,circular_list *init):key(k),status(TRUE),next(init){}};struct circular_list *tail=NULL;struct circular_list_status *tail_status=NULL;circular_list *insert(circular_list *head, int k){  circular_list *z=new circular_list[LEN];  z->key=k;  if(head==NULL)  {    head=tail=z;    head->next=tail;  //自循环  }  else  {    //插入表尾    tail->next=z;    z->next=head;    tail=z;  }  return head;}circular_list_status *insert_stus(circular_list_status *head,int k){  circular_list_status *z=new circular_list_status[LEN_status];  z->key=k;  z->status=TRUE;  if(head==NULL)  {    head=tail=z;    head->next=tail;  //自循环  }  else  {    //插入表尾    tail->next=z;    z->next=head;    tail=z;  }  return head;}circular_list *delete(circular_list *head, circular_list *z){  circular_list *p=head;  //先是要寻找到z这个结点的位置  while(p->next!=z)  //要删除的是p->next这个节点    p=p->next;  if(head==tail)    p->next=NULL;  else  {    if(p->next==head)      head=p->next->next;    else if(p->next==tail)      tail=p;    p->next=p->next->next;  }  return p->next;}circular_list_status *delete_stus(circular_list_status *head, circular_list_status *z){  circular_list_status *p=head;  while(p->next!=z)  //要删除的是p->next这个节点    p=p->next;  if(head==tail)    p->next=NULL;  else  {    if(p->next==head)      head=p->next->next;    else if(p->next==tail)      tail=p;    p->next=p->next->next;  }  return p->next;   //返回的值，是更新后的p->next}void Josephus_n_m(circular_list_status *head, int n,int m){  struct circular_list_status *p=head;  //p作为遍历指针  int count=0;  while(p && count<=n)  {    int i=0;    while(i!=m-1)    {      if(p->status==TRUE)      {        p=p->next;        i++;      }      else p=p->next;    }    //循环到最后，i报数报M-1    p->status=false;    count++;    p=p->next;  }}void Josephus_link_imple(circular_list *head,int m){  circular_list *p=head;  while(p)  {    int i=0;    while(i!=m-1)    {      p=p->next;      i++;    }    circular_list *z=p;    cout<
     
      key<<" ";    p=delete(head,z);  }}int main(){  int a[n]={0}  for(int i=0;i
      
       key;    p=p->next;    /* code */  } while(p!=head);  cout<

算法分析：时间复杂度是$O(mn)=O(n)$

是两个循环的嵌套，在m值不大的情况下可以使用该算法实现。

使用顺序统计树实现

假设m不是一个常数，用$O(nlgn)$的算法实现

这里采用顺序统计树来存储Josephus环中的点，通过映射关系查找每次需要删除的节点的坐标并执行删除。

映射关系如下图所示：

图片描述

主要的实现函数

void Josephus_imple(os_tree *T, int m, int n){  os_node *x=T->root;  int k=0, i=n;  int t=1;  while(T->root!=NULL && i>0)  {    k=(t+m-1)%i;    //k就是我们需要删除的点，注意到我们对一个点执行删除之后    //这个点原来的下标是k，删除了之后k+1就自动补到k的位置上    //这样新的k重新编号的话就是1，相当于原来的t=1    if(k==0)      k=i;    os_node *del=os_select(T,k);    //这里del表示要删除的结点    cout<
    
     key<<" ";    //输出节点    RB_delete(del);    t=k;    i--;  }}

这里采用的数据结构是一种顺序统计量，能够计算出rank值。但值得注意的是，在顺序统计量中，计算一个节点的rank值的函数的写法：

int Interative_os_rank(os_tree *T,os_node *x)//确定x这个节点的顺序统计树的rank{  int r=x->left->size+1;  os_node *y=x;     //沿左脊柱上升，r=x->left->size+1  while(y!=T->root)   //如果是沿着右脊柱上升？y->size=y->left->size+1+sum{y->parent->size}  {                  //沿左脊柱上升，r保持不变；一旦拐弯到了右脊柱，要关注y->parent->left->size+1    if(y==y->parent->right)      r=r+y->parent->left->size+1;    y=y->parent;    //不管是左脊柱还是右脊柱，都要沿树上升  }  return r;}

特别说明，当函数沿左脊柱上升的时候，r的值是r=x->left->size+1,但是，沿右脊柱，情形就变成了r=r+y->parent->left->size+1，具体的说明请看下图：

图片描述

$O(lgn)$算法的实现

os_tree.h

#define RED 0#define BLACK 1#define NIL -1#define LEN sizeof(struct os_node)#define LENTREE sizeof(struct os_tree)struct os_node{  os_node *left;  os_node *right;  os_node *parent;  int key;  int color;  int size;  //用于顺序统计量  os_node(os_node *init,int num)  :left(init),right(init),parent(init),key(num),color(RED),size(0){}};struct os_tree{  os_node *root;  os_node *nil;  os_tree()  {    nil=new os_node(NULL,NIL);    root=nil;  }};

rotate.h

#include "os_tree.h"void left_rotate(os_tree *T,os_node *x){  os_node *y=x->right;  //左孩子结点  x->right=y->left;  //这一部处理的是加在x，y之间的“内结点”，y->left原先  //夹在x->left和y->right之间，旋转之后子树的相对顺序不变，最外边的结点是  //x->left和y->right，注意是围绕x和y进行的旋转，所以子树的相对位置保持不变  if(y!=T->nil && y->left!=T->nil)    y->left->parent=x;  //旋转之后需要重新更新parent结点信息  y->parent=x->parent;  //这个时候y作为子树的根了，y要连到祖先中！  if(x->parent==T->nil)    T->root=y;  else if(x->parent->left==x)     x->parent->left=y;  else      x->parent->right=y;   //保证x与祖先结点相连接   //最后处理x和y的关系   y->left=x;   x->parent=y;   //顺序统计树新增部分   y->size=x->size;   //旋转之后，y代替原来x的位置，而x的位置在树的高处   //直接将原来x的size值赋值给y就可以了   x->size=x->left->size+x->right->size+1;}//右旋，对称的代码void right_rotate(os_tree *T,os_node *x){  //只需要把上述代码的相对位置，right和left互换就可以了   os_node *y=x->left;   x->left=y->right;   if(y!=T->nil && y->right!=T->nil)     y->right->parent=x;   //旋转之后需要重新更新parent结点信息   y->parent=x->parent;   if(x->parent==T->nil)     T->root=y;   else if(x->parent->left==x)      x->parent->left=y;   else       x->parent->right=y;    //保证x与祖先结点相连接    //最后处理x和y的关系    y->right=x;    x->parent=y;    y->size=x->size;    x->size=x>left->size+x->right->size;}

delete.h

#include "os_tree.h"#include "rotate.h"#include "succ_and_other.h"//删除调整，这个时候x有两重黑色void RB_delete_fixup(os_tree *T, os_node *x){  os_node *w=T->nil;  while (x!=T->root && x->color==BLACK)  {    if(x==x->parent->left)    {      w=x->parent->right;   //w为x的兄弟结点      if(w->color==RED)      {        w->color=BLACK;    //将这种情况划归为下面一种情况        w->parent->color=RED;        left_rotate(T,x->parent);        w=x->parent->right;      }      if(w->left->color==BLACK && w->right->color==BLACK)      {        w->color=RED;        x=x->parent;      //x和w的黑色沿树上升，注意到x有双重黑色，所以x的颜色不变      }                  //变得是w，x->parent的颜色      else      {        if(w->right->color==BLACK)        {          w->left->color=BLACK;          w->color=RED;         //同样，内节点变为外节点          right_rotate(T,w);          w=x->parent->right;        }        w->color=x->parent->color;   //这里x->parent的颜色不确定，但是w的颜色是黑色        //x有双重黑色，通过改变颜色加上旋转，可以将双重黑色表现在图中，这样完成了红黑树的局部平衡        x->parent->color=BLACK;        w->right->color=BLACK;        left_rotate(T,x->parent);        //红黑树局部平衡了        x=T->root;      }    }    else    {      w=x->parent->left;      if(w->color==RED)      {        w->color=BLACK;        x->parent->color=RED;        right_rotate(T,x->parent);        w=x->parent->left;      }    }    if(w->left->color==BLACK && w->right->color==BLACK)    {      w->color=RED;      x=x->parent;    }    else    {      if(w->left->color==BLACK)      {        w->right->color=BLACK;        w->color=RED;        left_rotate(T,w);        w=x->parent->left;      }      w->color=x->parent->color;      x->parent->color=BLACK;      w->left->color=BLACK;      right_rotate(T,x->parent);      x=T->root;    }  }  x->color=BLACK;}void transplant(os_tree *T, os_node *u, os_node *v){  if(u->parent==T->nil)    T->root=v;  else if(u==u->parent->left)    u->parent->left=v;  else u->parent->right=v;  if(v!=T->nil)    v->parent=u->parent;}void RB_delete(os_tree *T, os_node *z){  os_node *y=z, *x;  int y_original_color=y->color;  os_node *par=z->parent;  //par作为被删除节点的双亲  if(z->left==T->nil)  {    //删除一个节点的时候，size会发生变化    while(par!=T->nil)    {      //删除节点后，z的双亲的size值会减小      par->size--;      par=par->parent;  //自底向上遍历，所有的节点的size都减小    }    x=z->right;    transplant(T,z,z->right);  }  else if(z->right==T->nil)  {    while(par!=T->nil)    {      //删除节点后，z的双亲的size值会减小      par->size--;      par=par->parent;  //自底向上遍历，所有的节点的size都减小    }    x=z->left;    transplant(T,z,z->left);  }  else  {    y=tree_minimum(T,z->right);   //这里是查找z的后继，为y，用y来代替z的位置    y_original_color=y->color;    os_node *par=y->parent;    //这里用y嫁接到z处，原先y位置往上所有的节点相当于    //少了一个y结点，所以par往上遍历的过程中所有的size都为size--    //特别地，当用y来代替z的时候，并不是y->size=z->size    //因为子树中少了一个y，所以size-1    //特别注意，实际上，从y结点到z节点之间的节点，少了一个y    //从z节点往上，少了一个z，由于size结点是不包括当前节点的    //所以y->size=z->size-1    /*y->size=z->size-1;    while(par!=T->nil)    {      //删除节点后，z的双亲的size值会减小      par->size--;      par=par->parent;  //自底向上遍历，所有的节点的size都减小    }*/    //还有一种方法：完成transplant之后自底向上调整！    x=y->right;    if(y->parent==z)    {      x->parent=y;    }    else    {      transplant(T,y,y->right);      y->right=z->right;      y->right->parent=y;    }    transplant(T,z,y);    y->left=z->left;    y->left->parent=y;    y->color=z->color;    //这里进行size属性的维护    while(par!=T->nil)    {      //删除节点后，z的双亲的size值会减小      par->size--;      par=par->parent;  //自底向上遍历，所有的节点的size都减小    }  }  if(y_original_color==BLACK)     RB_delete_fixup(T,x);   //x为y的孩子结点，y的删除会影响x的相关性质}

insert.h

#include "os_tree.h"#include "rotate.h"void RB_insert_fixup(os_tree *T, os_node *z);void RB_insert(os_tree *T, os_node *z){  os_node *y=T->nil;  //y作为遍历指针的双亲  RB_node *x=T->root;  while(x!=T->nil)  {    y=x;    if(z->key
    
     key)      x->x->left;    else x=x->right;  }  z->parent=y;  //y作为遍历指针x的母结点，x遍历寻找合适的插入位置  if(y==T->nil)    T->root=z;  else if(z->key
     
      key)    y->left=z;  else y->right=z;  z->left=T->nil;  z->right=T->nil;  z->parent=RED;  //新插入节点的信息  z->size=1;  z->left->size=0;  z->right->size=0;  RB_insert_fixup(T,z);   //最后插入的结点是红色的，与此同时进行红黑树性质的调整}void RB_insert_fixup(os_tree *T,os_node *z){  while(z->parent->color==RED)  {    if(z->parent==z->parent->parent->left)    {      os_node *y=z->parent->parent->right;  //设置叔结点      if(y->color==RED)      {        z->parent->color=BLACK;   //父节点的黑色可以下放给两个结点        y->color=BLACK;        z->parent->parent->color=RED;        z=z->parent->parent;   //z沿树上升      }      else      {        if(z==z->parent->right)   //内结点先旋转成外节点        {          z=z->parent;          left_rotate(T,z);        }        z->parent->color=BLACK;    //改变颜色之后，z的兄弟结点和z颜色相同        z->parent->parent->color=RED;  //红黑树局部恢复平衡        right_rotate(T,z->parent->parent);  //这个技巧是：改变颜色之后，然后旋转，这样不破坏红黑树性质      }                                     //与此同时，结点沿树上升    }    else    {      os_node *y=z->parent->parent->left;      if(y->color==RED)      {        z->parent->color=BLACK;        y->color=BLACK;        z->parent->parent->color=RED;        z=z->parent->parent;      }      else      {        if(z==z->parent->left)        {          z=z->parent;          right_rotate(T,z);        }        z->parent->color=BLACK;        z->parent->parent->color=RED;        left_rotate(T,z->parent->parent);      }    }  }  T->root->color=BLACK;}

succ_and_other.h

#include "os_tree.h"os_node *tree_maxinum(os_tree *T, os_node *x){  while(x!=T->nil && x->right!=T->nil)    x=x->right;  return x;}os_node *tree_minimum(os_tree *T,os_node *x){  while (x->left!=T->nil) {    x=x->left;  }  return x;}os_node *tree_successor(os_tree *T, os_node *x){  if(x->right!=T->nil)  {    return tree_minimum(x->right);  }  os_node *y=x->parent;  //后继在根节点处  while(y!=T->nil && x==y->right)  {    x=y;    y=y->parent;  }  return y;}os_node *tree_predecessor(os_tree *T, os_node *x){  if(x->left!=T->nil)  {    return tree_maxinum(x->left);  }  os_node *y=x->parent;  while(y!=T->nil && x==y->left)  {    x=y;    y=y->parent;  }  return y;}os_node *Iterative_tree_search(os_tree *T,os_node *x, int k){  while(x!=T->nil && k!=x->key)  {    if(k
    
     key)      x=x->left;    else x=x->right;  }  return x;}void in_order_traverse(os_tree *T, os_node *p){  if(p!=T->nil)  {    in_order_traverse(p->left);    cout<
     
      key<<" "<
      
       color<<" "<
       
        size<
        
         right);  }}os_node *os_select_rank(os_tree *T, os_node *x, int i){  int r=x->left->size+1;  if(i==r)    return x;  else if(i
         
          left,i); else return os_select_rank(T,x->right,i-r);}int Interative_os_rank(os_tree *T,os_node *x)//确定x这个节点的顺序统计树的rank{ int r=x->left->size+1; os_node *y=x; //沿左脊柱上升，r=x->left->size+1 while(y!=T->root) //如果是沿着右脊柱上升？y->size=y->left->size+1+sum{y->parent->size} { //沿左脊柱上升，r保持不变；一旦拐弯到了右脊柱，要关注y->parent->left->size+1 if(y==y->parent->right) r=r+y->parent->left->size+1; y=y->parent; //不管是左脊柱还是右脊柱，都要沿树上升 } return r;}

Josephus_circle.h

#include "delete.h"#include "succ_and_other.h"void Josephus_imple(os_tree *T, int m, int n){  os_node *x=T->root;  int k=0, i=n;  int t=1;  while(T->root!=NULL && i>0)  {    k=(t+m-1)%i;    //k就是我们需要删除的点，注意到我们对一个点执行删除之后    //这个点原来的下标是k，删除了之后k+1就自动补到k的位置上    //这样新的k重新编号的话就是1，相当于原来的t=1    if(k==0)      k=i;    os_node *del=os_select(T,k);    //这里del表示要删除的结点    cout<
    
     key<<" ";    //输出节点    RB_delete(del);    t=k;    i--;  }}

主函数

#include "Josephus_circle.h"#include 
    
     #include "time.h"#include "os_tree.h"#include "delete.h"#include "insert.h"using namespace std;int main(){  srand((unsigned)time(NULL));  int m=0,n=0;  cout<<"输入Josephus排列的m和n值"<
     
      key=-1;  nilnode->color=BLACK;  T->nil=nilnode;  int i=0;  newroot->key=array_jose[i++];  RB_insert(T,newroot);  T->root=newroot;  while(i!=n)  {    os_node *z=new os_node[LEN];    z->key=array_jose[i];    RB_insert(T,z);    i++;  }  in_order_traverse(T,T->root);  cout<<"Josephus排列"<<" ";  Josephus_imple(T,m,n);}

转载地址：http://arlpa.baihongyu.com/

你可能感兴趣的文章