约瑟夫斯问题的求解方法

约瑟夫斯问题

1. 问题介绍

  这个问题是以弗拉瓦斯 约瑟夫斯的名字命名的。约瑟夫斯是一个著名的犹太历史学家，参加并记录了公元66-70年的犹太人反抗罗马的起义。约瑟夫斯作为一个将军，设法守住了裘达伯特的堡垒达47天之久，但在城市陷落之后，他在和40名顽强的战士在附近的一个洞穴中避难。在那里，一些反抗者表决说“要投降毋宁死”。于是，约瑟夫斯建议每个人应该轮流杀死他旁边的人，而这个顺序是是由抽签决定的。约瑟夫斯有预谋地抓到最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降罗马。

2. 算法简介

  首先我们先让n个人围成一个圈，并将它们从1到n编上号码。从编号为1的那个人开始残忍的计数，我们每次消去第二个人知道只留下一个幸存者。这么我们需要求解的便是这个幸存者的号码J(n)。

由上述例子可得：
当 n = 6 的时候，约瑟夫斯问题求解得出J(6) = 5
当 n = 7 的时候，约瑟夫斯问题求解得出J(7) = 7

1）公式法

  我们首先先把n作为人数，把它分为奇数和偶数的情况。每次经过一轮后，存活的人会重新排列起来，他们依次往前移来补出局人的空缺，因此我们需要记录他们下一次排列的位置，由上述例子可知，标记为3的人在下一轮中位置变为1，标记为5的人，在下一轮中位置变为3，随后依次类推。
奇数情况下
  因此，在奇数情况下，我们令 n = 2k + 1，在把偶数位置的人消灭了之后，我们需要把位置为1的人也要加进来，为了得到与新的位置编号相对应的初始位置编号，我们需要将它的新位置乘以2加1，那么便可以求出这个幸运者：

$J(2*K+1) = 2*J(K) + 1$J(2∗K+1)=2∗J(K)+1
偶数情况下
  因此，在偶数情况下，我们令n = 2K，我们把偶数位置上的人消灭了之后，为了得到一个人的初始位置，我们需要将它的新位置乘以2减1，那么便可以求出这个幸运者：

$J(2*K) = 2*J(K) - 1$J(2∗K)=2∗J(K)−1

2）每经过一轮，数组删减为原来的一半

每次经过一轮后，n为奇数和n为偶数的情况

  每次经过一轮，无论时奇数还是偶数，数组都会变为原来的一半（n / 2，奇数的情况使用向下取整方法）。arr为原先的数组，arrNew为新的数组。
当 n = 偶数的情况下：
$arrNew[i] = arr[i * 2];$arrNew[i]=arr[i∗2];
当 n = 奇数的情况下：
$arrNew[i] = arr[i * 2 + 2];$arrNew[i]=arr[i∗2+2];

3. 代码演示

import java.util.Scanner;

public class JosephusProblem {
    public static int flag = 0;
    //约瑟夫斯问题
    public static void main (String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.print("请输入一个数字：");
        int number = input.nextInt();
        josephus_1(number);
        System.out.println("幸运者为1：" + flag);
        int[] arrNumbers = new int[number];
        for (int i = 0; i < arrNumbers.length; i++) {
            arrNumbers[i] = i + 1;
        }
        josephus_2(arrNumbers);
    }

1）公式

     /**
     * 使用递归的算法来不断的计算存活的人数
     *
     * @param numbers      int类型
     */
    private static void josephus_1(int numbers) {
        //如果只有一个人的情况下，那么这一个人存活J(K) = 1
        //如果有偶数的情况下，那么情况为J(2 * K) = 2 * J(K) - 1
        //如果有奇数的情况下，那么情况为J(2 * K + 1) = 2 * J(K) + 1
        if (numbers == 1) {
            flag = 1;
        } else if (numbers % 2 == 0) {
            josephus_1(numbers / 2);
            flag = flag * 2 - 1;
        } else if (numbers % 2 != 0) {
            josephus_1((numbers - 1) / 2);
            flag = flag * 2 + 1;
        }
    }

2）每经过一轮，数组删减为原来的一半

/**
     * 使用非递归循环的方法来得出最后一个幸运者
     *
     * @param arrNumbers     int类型数组
     */
    private static void josephus_2 (int[] arrNumbers) {
        //计算arrNumbers.length的长度
        int length = arrNumbers.length;
        int[] arrNumberNew = new int[0];
        while (length != 1) {
            //如果为偶数的时候，长度缩小为原来的一半
            //如果为奇数的情况,长度缩小为原来的一半
            if (length % 2 == 0) {
                length = length / 2;
                arrNumberNew = new int[length];
            //从1开始
                for (int i = 0; i < arrNumberNew.length; i++)
                    arrNumberNew[i] = arrNumbers[2 * i];
            } else if (length % 2 != 0) {
                length = length / 2;
                arrNumberNew = new int[length];
                for (int i = 0; i < arrNumberNew.length; i++)
                    arrNumberNew[i] = arrNumbers[2 * i + 2];
            }
            arrNumbers = arrNumberNew;
        }
        System.out.println("幸存者为2：" + arrNumberNew[0]);
    }
}