文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > josephus环公式法
侵权投诉

josephus环公式法

Josephus(约瑟夫)问题的数学方法(转)2010-06-25 3:08Josephus问题

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的情形

该问题一般都是计算最

第1页

你可能喜欢

热门文档

相关文档

  • Josephus环算法的设计

    实验报告一 Josephus环算法的设计 实验报告一 Josephus环算法的设计 报告一、... josephus环公式法 3页 免费 一种生成随机数的新算法... 暂无评价 2页 ...

  • 课程设计Josephus环问题

    Josephus环-2 暂无评价 1页 2财富值 约瑟夫环问题(Josephus)源... 2页 2财富值 josephus环公式法 3页 免费 数据结构:Josephus环问题 暂无评价 3页 5...

  • 约瑟夫环问题(Josephus)

    约瑟夫环问题(Josephus)_计算机软件及应用_IT/计算机_专业资料。已知n(<2^15)个人(以编号1,2,…,n分别表示)围坐在一圆桌上,从编号为k(1≤ k≤ n)的人...

  • Time Improvement on Josephus Problem

    josephus环公式法 3页 免费 数据结构经典题(一)Jose... 3页 免费 ★约瑟夫问题(Josephus ... 3页 免费 Josephus problem 14页 免费Time ...

  • 循环单链表法实现Josephus问题

    向量法求解 Josephus 问题 智能一班 林潇 2220101468 一. 实验题目描述 Josephus 问题可描述如下: 设有 n 个人围成一个环, 现从第 s 个人开始报数, 数到第 ...

  • 约瑟夫环问题(Josephus)源代码

    写出C程序。(约瑟夫环问题 Josephus) 提示: 由于当某个人退出圆圈后,报数的工作要从下一个人开始继续,剩下的人仍然是围成一个圆圈的,可以使用循环表,由于退出圆圈...

  • (已验证)约瑟夫环问题(Josephus)

    7页 20财富值 Josephus环问题 2页 2财富值 课程设计Josephus环问题 13页 5财富值 josephus环 暂无评价 5页 8财富值 Josephus环 暂无评价 1页 2财富值...

  • Josephus问题

    Josephus问题:假设n个竞赛者排成一个环形,依次顺序...剩下的n-1个人组成了一个新的约瑟夫环(以编号为k...变回去的公式很简单:x'=(x+k)%n 如何知道(n-...

  • 求解Josephus问题实验报告(C语言向量法实现)

    求解Josephus问题实验报告(C语言向量法实现)_IT/计算机_专业资料。求解Josephus... ★约瑟夫问题(Josephus ... 3页 免费 josephus环公式法 3页 免费...

  • 编程求Josephus问题

    1. 编程求 Josephus 问题:m 个小孩围成一圈,从第一个小孩开始顺时针方向每数...8. 建立一个 VI,只用一个公式节点计算下面的方程。 y1=x*x*x+x*x-3*x...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email