首页 > 其他 > 详细

约瑟夫斯问题

时间:2020-09-18 18:56:15      阅读:109      评论:0      收藏:0      [点我收藏+]

约瑟夫问题
维基百科,自由的百科全书
跳到导航跳到搜索
约瑟夫问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,处刑下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。

问题即,给定人数、起点、方向和要跳过的数字,选择初始圆圈中的位置以避免被处决。

历史
这个问题是以弗拉维奥·约瑟夫命名的,他是1世纪的一名犹太历史学家。他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意,他不知道是哪一个。[1]

解法
比较简单的做法是用循环单链表模拟整个过程,时间复杂度是O(n*m)。如果只是想求得最后剩下的人,则可以用数学推导的方式得出公式。且先看看模拟过程的解法。

Python版本

-- coding: utf-8 --

class Node(object):
def init(self, value):
self.value = value
self.next = None

def create_linkList(n):
head = Node(1)
pre = head
for i in range(2, n+1):
newNode = Node(i)
pre.next= newNode
pre = newNode
pre.next = head
return head

n = 5 #总的个数
m = 2 #数的数目
if m == 1: #如果是1的话,特殊处理,直接输出
print (n)
else:
head = create_linkList(n)
pre = None
cur = head
while cur.next != cur: #终止条件是节点的下一个节点指向本身
for i in range(m-1):
pre = cur
cur = cur.next
print (cur.value)
pre.next = cur.next
cur.next = None
cur = pre.next
print (cur.value)

using namespace std;

typedef struct _LinkNode {
int value;
struct _LinkNode* next;
} LinkNode, *LinkNodePtr;

LinkNodePtr createCycle(int total) {
int index = 1;
LinkNodePtr head = NULL, curr = NULL, prev = NULL;
head = (LinkNodePtr) malloc(sizeof(LinkNode));
head->value = index;
prev = head;

while (--total > 0) {
	curr = (LinkNodePtr) malloc(sizeof(LinkNode));
	curr->value = ++index;
	prev->next = curr;
	prev = curr;
}
curr->next = head;
return head;

}

void run(int total, int tag) {
LinkNodePtr node = createCycle(total);
LinkNodePtr prev = NULL;
int start = 1;
int index = start;
while (node && node->next) {
if (index == tag) {
printf("%d\n", node->value);
if (tag == start) {
prev = node->next;
node->next = NULL;
node = prev;
} else {
prev->next = node->next;
node->next = NULL;
node = prev->next;
}
index = start;
} else {
prev = node;
node = node->next;
index++;
}
}
}

int main() {
if (argc < 3) return -1;
run(atoi(argv[1]), atoi(argv[2]));
return 0;
}
数学推导解法
我们将明确解出{\displaystyle k=2}k=2时的问题。对于{\displaystyle k\neq 2}k\neq 2的情况,我们在下面给出一个一般的解法。

设{\displaystyle f(n)}f(n)为一开始有{\displaystyle n}n个人时,生还者的位置(注意:最终的生还者只有一个)。走了一圈以后,所有偶数号码的人被杀。再走第二圈,则新的第二、第四、……个人被杀,等等;就像没有第一圈一样。如果一开始有偶数个人,则第二圈时位置为{\displaystyle x}x的人一开始在第{\displaystyle 2x-1}2x-1个位置。因此位置为{\displaystyle f(2n)}f(2n)的人开始时的位置为{\displaystyle 2f(n)-1}2f(n)-1。这便给出了以下的递推公式:

{\displaystyle f(2n)=2f(n)-1.,}f(2n)=2f(n)-1.,
如果一开始有奇数个人,则走了一圈以后,最终是号码为1的人被杀。于是同样地,再走第二圈时,新的第二、第四、……个人被杀,等等。在这种情况下,位置为{\displaystyle x}x的人原先位置为{\displaystyle 2x+1}2x+1。这便给出了以下的递推公式:

{\displaystyle f(2n+1)=2f(n)+1.,}f(2n+1)=2f(n)+1.,
如果我们把{\displaystyle n}n和{\displaystyle f(n)}f(n)的值列成表,我们可以看出一个规律:

{\displaystyle n}n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
{\displaystyle f(n)}f(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1
从中可以看出,{\displaystyle f(n)}f(n)是一个递增的奇数数列,每当n是2的幂时,便重新从{\displaystyle f(n)=1}f(n)=1开始。因此,如果我们选择m和l,使得{\displaystyle n=2^{m}+l}n=2^{m}+l且{\displaystyle 0\leq l<2^{m}}0\leq l<2^{m},那么{\displaystyle f(n)=2\cdot l+1}f(n)=2\cdot l+1。注意:2^m是不超过n的最大幂,l是留下的量。显然,表格中的值满足这个方程。我们用数学归纳法给出一个证明。

定理:如果{\displaystyle n=2^{m}+l}n=2^{m}+l且{\displaystyle 0\leq l<2^{m}}0\leq l<2^{m},则{\displaystyle f(n)=2l+1}f(n)=2l+1。

证明:对{\displaystyle n}n应用数学归纳法。{\displaystyle n=1}n=1的情况显然成立。我们分别考虑{\displaystyle n}n是偶数和{\displaystyle n}n是奇数的情况。

如果{\displaystyle n}n是偶数,则我们选择{\displaystyle l_{1}}l_{1}和{\displaystyle m_{1}}m_{1},使得{\displaystyle n/2=2^{m_{1}}+l_{1}}n/2=2^{{m_{1}}}+l_{1},且{\displaystyle 0\leq l_{1}<2^{m_{1}}}0\leq l_{1}<2^{{m_{1}}}。注意{\displaystyle l_{1}=l/2}l_{1}=l/2。我们有{\displaystyle f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1}f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1,其中第二个等式从归纳假设推出。

如果{\displaystyle n}n是奇数,则我们选择{\displaystyle l_{1}}l_{1}和{\displaystyle m_{1}}m_{1},使得{\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}(n-1)/2=2^{{m_{1}}}+l_{1},且{\displaystyle 0\leq l_{1}<2^{m_{1}}}0\leq l_{1}<2^{{m_{1}}}。注意{\displaystyle l_{1}=(l-1)/2}l_{1}=(l-1)/2。我们有{\displaystyle f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1}f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1,其中第二个等式从归纳假设推出。证毕。

答案的最漂亮的形式,与{\displaystyle n}n的二进制表示有关:把{\displaystyle n}n的第一位移动到最后,便得到{\displaystyle f(n)}f(n)。如果{\displaystyle n}n的二进制表示为{\displaystyle n=b_{0}b_{1}b_{2}b_{3}\dots b_{m}}n=b_{0}b_{1}b_{2}b_{3}\dots b_{m},则{\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}b_{0}}f(n)=b_{1}b_{2}b_{3}\dots b_{m}b_{0}。这可以通过把{\displaystyle n}n表示为{\displaystyle 2^{m}+l}2^{m}+l来证明。

一般情况下,考虑生还者的号码从{\displaystyle n-1}n-1到{\displaystyle n}n的变化, 我们可以得到以下的递推公式(编号从0开始):

{\displaystyle f(n,k)=(f(n-1,k)+k){\bmod {n}}}f(n,k)=(f(n-1,k)+k){\bmod n},{\displaystyle f(1,k)=0}f(1,k)=0

这种方法的运行时间是{\displaystyle O(n)}O(n)。

程序实现(C++)

include

using namespace std;
//編號從0開始,也就是說如果編號從1開始結果要加1
int josephus(int n, int k) { //非遞回版本
int s = 0;
for (int i = 2; i <= n; i++)
s = (s + k) % i;
return s;
}
int josephus_recursion(int n, int k) { //遞回版本
return n > 1 ? (josephus_recursion(n - 1, k) + k) % n : 0;
}
int main() {
for (int i = 1; i <= 100; i++)
cout << i << ‘ ‘ << josephus(i, 5) << ‘ ‘ << josephus_recursion(i, 5) << endl;
return 0;
}
对于{\displaystyle k<n}k<n,可以将上述方法推广,将杀掉第k、2k、……、{\displaystyle \lfloor n/k\rfloor }\lfloor n/k\rfloor 个人视为一个步骤,然后把号码改变,可得如下递推公式, 运行时间为{\displaystyle O(k\log n)}O(k\log n)。

{\displaystyle f(n,k)={\begin{cases}0&{\text{if }}n=1\(f(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k\\left\lfloor {\frac {k((f(n‘,k)-n{\bmod {k}}){\bmod {n}}‘)}{k-1}}\right\rfloor {\text{where }}n‘=n-\left\lfloor {\frac {n}{k}}\right\rfloor &{\text{if }}k\leq n\\end{cases}}}{\displaystyle f(n,k)={\begin{cases}0&{\text{if }}n=1\(f(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k\\left\lfloor {\frac {k((f(n‘,k)-n{\bmod {k}}){\bmod {n}}‘)}{k-1}}\right\rfloor {\text{where }}n‘=n-\left\lfloor {\frac {n}{k}}\right\rfloor &{\text{if }}k\leq n\\end{cases}}}
程序实现(C++)

include

using namespace std;
//編號從1開始,結果要加1
int josephus(int n, int k) {
if (k==1) return n-1;
int ans=0;
for (int i=2;i<=n;)
{
if (ans+k>=i)
{
ans=(ans+k)%i;
i++;
continue;
}
int Step=(i-1-ans-1)/(k-1);//向下取整
if (i+Step>n)
{
ans+=(n-(i-1))k;break;
}
i+=Step;ans+=Step
k;
}
return ans;
}

int main() {
while (~scanf("%d%d",&n,&k)
printf("%d\n",josephus(n,k)%n+1);
return 0;
}
https://zh.wikipedia.org/zh-cn/约瑟夫斯问题

约瑟夫斯问题

原文:https://www.cnblogs.com/pony-mamba/p/13598284.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!