约瑟夫问题

目录

1 问题描述

夫拉维.约瑟夫(Flavius Josephus)是一世纪著名的历史学家. 在犹太罗马战争期间, 他们 41名犹太反抗者被罗马人困在了洞穴中. 这些反抗者宁愿自杀也不愿被活捉, 他们决定围成一个圆圈, 并沿着圆圈每三个人杀死一个人, 直到没有人剩下. 但是, 约瑟夫和他的一名朋友不希望无谓地自杀, 于是他迅速地计算出他和朋友在这个险恶圆圈中的应该站的位置, 最后生存了下来.

约瑟夫问题的一般描述如下: \(n\)个人围成一圈, 从第1个开始报数, 第\(k\)个人离开, 直到最后剩下\(m\)个人. 指定\(n, k\)时, 求\(m\)个人所在的位置.

2 问题分析

2.1 \(k=2, m=1\)的情况分析

2.1.1 暴力遍历

此问题的暴力遍厉十分简单:

  1. 构造数组\(candidate_array\), 初始化各项数值为\(1,2,...,n\), 初始化剩余人员数量\(left_candidate\)为n;
  2. 遍厉数组\(candidate_array\),

2.1.2 非封闭优化解

假设开始时有\(2n\)个人, 第一轮后剩下的是\(1, 3, 5, ..., 2n-3, 2n-1\). 同时3号是下一个要离开的人. 对比分析\(n\)个人开始时的情况, 是每个人的号码加倍并减1:

\(J.1: J(2n) = 2J(n) - 1, n\ge 1 \)

再分析\(2n+1\)个人的情形, 第一轮后剩下的是\(1, 3, 5, ..., 2n-1, 2n+1\), 标号为1的人是下一轮第一个离开人选. 1号离去后剩余\(n\)个人\(3, 5, ..., 2n-1, 2n+1\), 离去人合计\(n+1\)个:

\(J.2: J(2n+1)=2J(n)+1, n\ge 1\)

对于\(n=1\)的情况, 分析可知\(J(1)=1\). 结核J.1和J.2, 已经可以用递归方式解决此问题.

例如: \(J(5)=2J(2)+1=3\) \(J(20)=2J(10)-1=2*(2*J(5)-1)-1=2*(2*3-1)-1=9\)

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

\(J(2^m+l)=2l+1\)

请参考2.1.1.