• 打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮
  • 打赏支付宝扫一扫

首页

 > 

设计架构 > 

数据结构

转贴:Josephus问题

winter-cnwinter-cn • 10年前
原文地址及原作者不详

1. 问题的由来
Josephus问题是以10世纪的著名历史学家Flavius Josephus命名的. 据说, Josephus如果没有数学才能, 他就不会在活着的时候出名! 在犹太人和古罗马人战争期间, 他是陷如罗马人陷阱的41个犹太反抗者之一. 反抗者宁死不做俘虏, 他们决定围成一个圆圈,且围绕圆圈来进行, 杀死所有第3个剩下的人直到没有一个人留下. 但是, Josephus和一个不告发的同谋者感到自杀是愚蠢的行为, 所以以他快速计算出在此恶性循环中他和他的朋友应该站的地方. 因此, 他们活了下来...
2.  平凡的解法 
 
我们用一个循环连表来模拟他们的行为。为了省事,我直接找了一个一个java代码: 
 
class  Josephus   
{   
           static  class  Node   
           { 
                       int  val;  Node  next;   
                       Node(int  v)  {  val  =  v;  }   
           }   
           public  static  void  main(String[]  args)   
           { 
                       int  N  =  Integer.parseInt(args[0]);   
                       int  M  =  Integer.parseInt(args[1]);   
 
                       Node  t  =  new  Node(1);   
                       Node  x  =  t;   
 
                       for  (int  i  =  2;  i    <=  N;  x  =  (x.next=new  Node(i++)));   
                       x.next  =  t;   
 
                       while  (x  !=  x.next)   
                       {   
                                   for  (int  i  =  1;  i    <  M;  i++)  x  =  x.next;   
                                   x.next  =  x.next.next;   
                       }   
                       Out.println(  "Survivor  is    "  +  x.val);   
           }   
}
 
3.  递归公式 
 
喜欢这个问题的朋友肯定不满足上面的方法,很想知道更简单的算法。 
其实Josephus问题中的序列确实存在递归的公式。但是递归公式的推导 
比较麻烦,我就直接给出结果。如果想了解详细过程可以查阅相关资料。 
 
假设有n个人,每次杀第m个人,则k为第k个被杀死的人... 
 
j1:  x    <-  k*m 
j2:  if(x    <=  n)  输入结果x 
j3:  x    <-  floor((m*(x-n)-1)  /  (m-1)),  goto  j1 
 
以C语言实现如下: 
 
unsigned  josephus(unsigned  m,  unsigned  n,  unsigned  k) 

           unsigned  x  =  km; 
           while(x    <=  n)  x  =  (m*(x-n)-1)/(m-1); 
           return  x; 
4. m为2的情况 
 
现在考虑一种m为2的特殊情形。 
这时候有更简单的递归公式: 
 
x  =  2*n  +  1  -  (2*n+1-2*k)*2^log2((2*n)/(2*n+1-2*k)) 
 
其中,log2((2*n)/(2*n+1-2*k))为计算(2*n)/(2*n+1-2*k)以2为底的对数, 
结果向下取整数。 
 
联系2^log2((2*n)/(2*n+1-2*k))整体,可以理解为将(2*n)/(2*n+1-2*k)向下 
舍取到2的幂。有些地方把这中运算称为地板函数,我们定义为flp2,下面是 
C语言的实现: 
 
unsigned  flp2(unsigned  x) 

           unsigned  y; 
           do  {  y  =  x;  x  &=  x-1;  }while(x);   
           return  y;   

其中x  &=  x-1;语句是每次把x二进制最右边的1修改为0,直到最左边的1为止. 
这种方法也可以用来计算x二进制中1的数目,当x二进制中1的数目比较小的 
时候算法的效率很高。
m为2的代码实现:
unsigned josephus2k(unsigned n, unsigned k)
{
unsiged t = (n<<1) - (k<<1) + 1;
return (n<<1)+1 - t*flp2((n<<1)/t);
5. m为2的情况, k为n的情形
该问题一般都是计算最后一个被杀的人的位置。
现在考虑更为特殊的,m为2的情况, k为n的情形。
令k=n可以化简前边m=2的公式:
x = 2*n + 1 - (2*n+1-2*n)*2^log2((2*n)/(2*n+1-2*n))
即,x = 2*n + 1 - 2^log2(2*n)
从二进制的角度可以理解为:
将n左移1位(即乘以2),然后将最右端设置为1(既加1),
最后将左端的1置为0(既减去2*n的向下取的2的幂)。
更简单的描述是将n的二进制表示循环右移动一位!
例如: n为1011001 -> 0110011 -> 110011
用代码实现为:
unsigned josephus2n(unsigned n)
{
return ((n-flp2(n))<<1)|1;
}
===================
class Josephus
{
static class Node
{
int val; Node next;
Node(int v) { val = v; }
}
public static void main(String[] args)
{
int N = Integer.parseInt(args[0]);
int M = Integer.parseInt(args[1]);
Node t = new Node(1);
Node x = t;
for (int i = 2; i <= N; x = (x.next=new Node(i++)));
x.next = t;
while (x != x.next)
{
for (int i = 1; i < M; i++) x = x.next;
x.next = x.next.next;
}
Out.println("Survivor is " + x.val);
}
}
unsigned josephus(unsigned m, unsigned n, unsigned k)
{
unsigned x = km;
while(x <= n) x = (m*(x-n)-1)/(m-1);
return x;
}
unsigned flp2(unsigned x)
{
unsigned y;
do { y = x; x &= x-1; }while(x);
return y;
}
unsigned josephus2n(unsigned n)
{
return ((n-flp2(n))<<1)|1;
}
unsigned josephus2k(unsigned n, unsigned k)
{
unsiged t = (n<<1) - (k<<1) + 1;
return (n<<1)+1 - t*flp2((n<<1)/t);
}

参考knuth相关著作
 
 
 
 
#include<iostream>
using namespace std;
typedef struct Josephus
{
int value;
Josephus *next;
}JS,*pJS;
int main()
{
pJS l,p,q;
l=new JS;
l->value =1;
l->next =l;
q=l;
for (int i=2;i<=2000;i++)
{
p=new JS;
p->value =i;
        p->next =l;
q->next =p;
q=q->next;
}
while(q->next!=q)
{
p=q->next;
q->next=q->next->next;
q=q->next;
delete p;
}
cout<<q->value<<endl;
system("pause");
return 0;
}
结果:1952
 
“看完这篇还不够?如果你也在学习IT,并希望记录自己的成长日志,请戳这里告诉我们!”
新人作者

好好学习,天天向上,有工作有兼职可以找我。微信号:gethost

文章总数
总阅读量
程序猿们,如果你或你的朋友想升职加薪,请狠戳这里我要成长
参与讨论
后参与讨论
winter-cn
新人作者

文章总数
总阅读量
程序猿们,如果你或你的朋友想升职加薪,请狠戳这里我要成长
48h快讯7天最热月榜More
  • 7年前

    Dijkstra算法(单源最短路径)单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。一.最短路径的最优子结构性质该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路
    收起
  • 7年前

    二叉树的非递归遍历二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。一.前序遍历前序遍历按照根结点-左孩子-右孩子的顺序进行访问。1.递归实现voi
    收起
  • 7年前

    淘宝名词解释产品和商品的区别:淘宝标准化产品,由类目+关键属性唯一确定。如:手机类目,关键属性是品牌和型号,NokiaN95就是一个产品,nokia是品牌,N95是型号。产品除了关键属性还包括一般信息、销售属性和非关键属性。参考:如"诺基亚N95"就是一个产品。通过类目的关键属性组合来确定唯一的产品。后台标准类目叶子节点下,一组共同特征商品的组合(例如:化妆品+雅芳+保湿单品+容量),属于同一个产品的商品可以认为对消费者的效用及使用感受是没有差别的。产品这个概念对淘宝这种C2
    收起
  • 5年前

    队列特性:先进先出(FIFO)先进队列的元素先出队列。来源于我们生活中的队列(先排队的先办完事)。队列有下面几个操作:InitQueue()  初始化队列EnQueue()进队列DeQueue()出队列IsQueueEmpty()判断队列是否为空IsQueueFull()判断队列是否已满队列可以由数组和链表两种形式实现队列操作(c语言),下面仅以数组为例:数组实现:队列数据结构typedefstructqueue
    收起
  • 7年前

    前言那个啥前面发了2篇文章讲这个商品表的设计,后面越多需求浮出水面才发现设计依旧有问题,好吧,乐观一点,正如我博客的标题一样,我在进化^_^为什么要这样设计先说几个需求,看看您现在是如何去实现:一个用户来到我们网站,在前台页面,1.他要买洗发水,他进入了洗发水的类别,他想买带去屑止痒功效的500ml的洗发水,能否直接搜索出来所有品牌带这个功效属性是500ml的洗发水2.接着他要买一件T恤,他想买V领,短袖的T恤,能否直接通过2个属性搜索出所有品牌的T恤展示给他3.他
    收起
  • 9年前

    1、反转一个链表。循环算法。1Listreverse(Listl){2if(!l)returnl;3listcur=l.next;4listpre=l;5listtmp;6pre.next=null;7while(cur){8tmp=cur;9cur=cur.ne
    收起
  • 7年前

    图的遍历图的遍历有两种遍历方式:深度优先遍历(depth-firstsearch)和广度优先遍历(breadth-firstsearch)。1.深度优先遍历基本思想:首先从图中某个顶点v0出发,访问此顶点,然后依次从v0相邻的顶点出发深度优先遍历,直至图中所有与v0路径相通的顶点都被访问了;若此时尚有顶点未被访问,则从中选一个顶点作为起始点,重复上述过程,直到所有的顶点都被访问。可以看出深度优先遍历是一个递归的过程。如下图中的一个无向图其深度优先遍历得到的序
    收起
  • 7年前

    1:原理以此比较相邻的两个元素,每次比较完毕最大的一个字跑到本轮的末尾。目的:按从小到大排序。方法:假设存在数组:72,54,59,30,31,78,2,77,82,72第一轮比较相邻两个元素,如果左边元素大于右边元素,则交换。72和54比较的结果就是,54在前,72在后;然后72和59比较的结果,59在前,72在后;以此类推,第一轮比较之后的结果是:54,59,30,31,72,2,77,78,72,82经过第一轮比较,最大的元素跑到了最
    收起
  • 9年前

    CodehighlightingproducedbyActiproCodeHighlighter(freeware)http://www.CodeHighlighter.com/-->/*冒泡排序基本思想将n个记录看作按纵向排列,每趟排序时自下至上对每对相邻记录进行比较,若次序不符合要求(逆序)就交换。每趟排序结束时都能使排序范围内关键字最小的记录象一个气泡一样升到表上端的对应位置,整个排序过程共进行n-1趟,依次将关键字最小、次小、第三小的各个记录冒到表的第一个、第二个、第三个位置
    收起