约瑟夫斯问题的一个优化解法

发表于   |   分类于 技术向文章 , 算法   |   暂无评论

Josephus Problem，俗称“出圈问题”，通常描述为： n 个人围成一个圈，从第一个人开始依次报数，将报 k 的人移出这个圈，然后下一个人开始重新报数，直到这个圈子仅剩一人，试问这个人在最初的圈子中是第几个人。（其中，n>1, k>1。）
这个问题通常是练习程序设计的一个重要题目，解答这个题目的程序也可以使用以下几种不同的数据结构与算法。由于本文着重讨论算法过程本身，因此默认所有传入参数均合法。

使用循环链表（结构）和遍历链表结点移除（算法）

首先定义基本的链表结构和算法。

/* 链表结构 */
typedef struct st_p {
  int num;
  struct st_p *next;
} p;

/* 新建一个结点，分配空间，初始化结点的值 */
p *add_node( int num, p *ptr ) {

  p *ptr_new = NULL;
  ptr_new = ( p * ) malloc( sizeof ( p ) );

  ptr_new->num  = num;
  ptr_new->next = ptr;   // IMPORTANT

  return ptr_new;
}

/* 初始化整个链表
 * 从 num 值最大的一项开始，从后向前生成整个链表 */
p *init( int all_num ) {

  p *ptr = NULL;

  ptr = add_node( all_num--, ptr );
  p *tail = ptr;    // 将尾结点的特殊标记

  while ( all_num > 0 ) {
    ptr = add_node( all_num--, ptr );
  }

  tail->next = ptr;    // 将尾结点的 next 指向首结点
  return ptr;
}

/* 移除 ptr 之后的第 each_num 个结点 */
p *remove_one( p *ptr, int each_num ) {

  for ( ; each_num > 2; each_num-- )  // 默认 each_num > 2
    ptr = ptr->next;

  p *ptr_out;

  ptr_out = ptr->next;
  ptr->next = ptr_out->next;

  free( ptr_out );
  return ptr->next;
}

有了基本算法后，整个“出圈”过程将高度简化。

int josephus_chain( int all_num, int each_num ) {

  p *ptr = NULL;
  ptr = init( all_num );

  /* 仅剩一个人等价于 ptr->next == ptr */
  while ( ptr->next != ptr ) {
    ptr = remove_one( ptr, each_num );
  }

  int ret = ptr->num;
  free( ptr );
  return ret;
}

使用线性表（数据结构）和线性表的遍历（算法）

使用线性表时的基本思路与使用链表相同，都是先构造一个“圆圈”，然后一个一个将结点移除。

int *init_list( int all_num )
{
  /* 初始化列表，并动态分配空间 */
  int *list;
  list = ( int * ) malloc( all_num * sizeof ( int ) );

  int i = 0;
  for ( ; i < all_num; i++ ) {
    list[ i ] = i + 1;          // 逐个设定列表数值
  }

  return list;
}

void remove_entry( int *list, int index, int list_cur_len ) {

  int i = index;
  for ( ; i < list_cur_len - 1; i++ ) {
    list[ i ] = list[ i + 1 ];   // 将第 index 个结点移除，把后边的结点向前移动
  }

  list[ i ] = 0x0;
}

使用列表总体来说比链表实现进来要方便很多。

int josephus_list( int all_num, int each_num )
{
  int *list;
  list = init_list( all_num );

  int i = 0;
  int list_cur_len = all_num;
  /* 初始化列表完毕 */

  while ( list_cur_len > 1 ) {  // 每次移除一个结点，直到只剩一个结点为止

    i = ( i + each_num - 1 ) % list_cur_len;   // 确定要移除的结点的 index
    remove_entry( list, i, list_cur_len );
    list_cur_len -= 1;

    if ( i > list_cur_len ) i = 0;  // 因为 list_cur_len 已经减一，所以此处使用 > 号
  }

  int ret = list[ 0 ];
  free( list );
  return list[ 0 ];
}

使用两个变量（数据结构）以及递归算法（算法）

目前我个人已知最快算法。该算法使用递归思想，把“一圈人”看作一个数列，每删除一个结点后重新排列数列，可以得出递归公式为 f( n ) = [ f( n - 1 ) + k ] % n。通过这一公式逆向计算出最终留下的人最初的编号。

int josephus_algo( int all_num, int each_num ) {
  int ori_num = each_num % 2;
  int iter = 3;

  for ( ; iter <= all_num; iter++ ) {
    ori_num = ( ori_num + each_num ) % iter;    // 递归公式
  }

  return ori_num + 1;
}

以上四种算法的复杂度比较

就数学算法本身来说，内存的动态分配与回收的时间与空间成本不应计入复杂度中。但对于算法的可用性来说，内存管理是算法使用中必不可少的，同时内存管理甚至有时会成为算法实现中最耗时的部分。因此在比较以上四种算法的性能时，执行内存管理的过程也计入程序运行时间中去了。
注：测试程序本身比较简单，而且与算法没有直接关系，在此不列出。可以移步GitHub参考。
all_num分别取100，10000，100000；each_num分别取比all_num大的最小素数及最接近(1/4)all_num的素数（若有两个，取小者）以及比3all_num小的最大素数。

最终程序运行结果为：

all_num: 100
each_num: 31
algo: 91, time: 0. 0 s
list: 91, time: 0. 0 s
chain: 91, time: 0. 0 s

all_num: 100
each_num: 101
algo: 31, time: 0. 0 s
list: 31, time: 0. 0 s
chain: 31, time: 0. 0 s

all_num: 100
each_num: 293
algo: 33, time: 0. 0 s
list: 33, time: 0. 0 s
chain: 33, time: 0. 0 s

all_num: 10000
each_num: 3331
algo: 5024, time: 0. 1 s
list: 5024, time: 0. 65 s
chain: 5024, time: 0.159 s

all_num: 10000
each_num: 10007
algo: 7332, time: 0. 0 s
list: 7332, time: 0. 65 s
chain: 7332, time: 0.498 s

all_num: 10000
each_num: 29989
algo: 4408, time: 0. 1 s
list: 4408, time: 0. 64 s
chain: 4408, time: 1.432 s

all_num: 100000
each_num: 33331
algo: 47407, time: 0. 1 s
list: 47407, time: 6.321 s
chain: 47407, time: 20.473 s

all_num: 100000
each_num: 100003
algo: 41174, time: 0. 2 s
list: 41174, time: 6.338 s
chain: 41174, time: 62.940 s

all_num: 100000
each_num: 299993
algo: 6511, time: 0. 1 s
list: 6511, time: 6.351 s
chain: 6511, time: 189.214 s

all_num: 100
each_num: 100003
algo: 34, time: 0. 0 s
list: 34, time: 0. 0 s
chain: 34, time: 0. 41 s

all_num: 100000
each_num: 31
algo: 42868, time: 0. 1 s
list: 42868, time: 6.427 s
chain: 42868, time: 0. 28 s

可以看出，对于基于列表的算法，受all_num影响很大，而受each_num影响较小；基于链表的算法，则同时受到all_num和each_num的影响；递归算法，则耗时极少，在此另作一次测试：

all_num: 2102586737
each_num: 2101482763
algo: 8383763, time: 21.409 s

all_num: 210258673
each_num: 2101482763
algo: 3764271, time: 2.178 s

all_num: 21025867
each_num: 2101482763
algo: 18766660, time: 0.217 s

all_num: 2102586737
each_num: 210148276
algo: 656715148, time: 20.858 s

all_num: 2102586737
each_num: 21014827
algo: 177403765, time: 20.380 s

all_num: 2102586737
each_num: 2101482
algo: 1062073320, time: 20.277 s

由此可见，all_num对该算法的影响要比each_num大得多。
添加新评论