PTA猴子选大王（约瑟夫环问题）

 

目录

题目

暴力求解 

 约瑟夫环公式的应用

---

题目

---

 

暴力求解 

一开始我每意识到这是一个约瑟夫环问题，于是就想着能不能通过对数组标记的方法暴力求解。

一开始的思路

• 首先我定义一个数组表示这群猴子，数组的初始值都为1（表示一开始所有的猴子都在圈子中，如果数组中某个元素的值为0，则表示这个猴子不再圈子中）
• 接着定义一个计数器（表示当前的所报的号数），每当号数达到3时，就把当前的猴子所对应的数组元素值赋值为0（表示不在圈子中，注意记录退出的猴子的个数），同时号数重新赋值为0（重新开始报数）
• 最后当退出的猴子个数为猴子总个数减一时，就选出来了大王

代码如下：

import java.util.*;
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) 
            a[i] = 1; // 一开始数组元素值都为1，表示当前所有的猴子都在圈子中
        int num = n; // 圈子中剩余猴子的个数
        int count = 0; // 每轮猴子的序号
        int flag = 0; // 猴王的编号
        while (num != 1) {
            for (int i = 0; i < n; ++i) {
                
                if (a[i] == 1) {
                    count++;
                    flag = i;
                }
                if (count == 3) {
                    a[i] = 0; // 不在圈子中，重新开始报数
                    count = 0;
                    --num; // 报到3的那只猴子退出圈子
                }
            }
        }
        System.out.println(flag + 1);
    }
}

但当我提交上去（扎心了）

 

由于我一直找不到那个出错的点，我只能换一种思路——这时我才发现原来这道题这就是约瑟夫环问题 

而对于约瑟夫环问题只要我们在理解基础上记住约瑟夫环的递推公式，这道题目瞬间就变得简单起来了

---

 约瑟夫环公式的应用

 

我们来简单回顾一下约瑟夫环问题

求圈圈里的最后一个数就可以被称为约瑟夫环问题 

 

 意思就是

• f(n，m)的值就表示对0，1，2，... n - 1，这n个数做约瑟夫操作后最后剩下的那个数（即剩下的那个大王）
• f(n - 1, m)的值就表示对0，1，2，... n - 2，这n - 1个数做约瑟夫操作后剩下的那个数

有以下递推公式

 

这不就是递归吗？ 

如果对约瑟夫环不理解可以看一下这篇文章——约瑟夫环深度解析 

代码如下

import java.util.*;
public class Main {
    public static int func(int n, int m) { 
        if (n == 1) return 0;
        int flag = (func(n - 1, m) + m) % n; // flag表示经过约瑟夫环操作后，最后剩余的那个数字
        return flag;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int flag = func(n, 3); // flag表示约瑟夫环操作后最后一只猴子的序号
        System.out.println(flag + 1); // 因为序号是从1开始的，所有要加一
    }
}

 

 但是递归效率因为有个来回的规程，效率相比直接迭代差一些，也可从前往后迭代：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int flag = 0;//倒推，已知最后一轮猴大王编号为0，推得倒数第二轮，倒数三轮。。。一直到初始位置。
        //flag表示最后一只猴子（猴大王）在每轮（先倒数第1轮，再求倒数第二轮，...）中自己的序号   
        //i表示倒数第i轮

        for (int i = 2; i <= n; ++i) { // 这里的i就相当于递归中的n,3就是m
            flag = (flag + 3) % i;    // flag表示约瑟夫环操作后最后一只猴子的序号
            // 当前圈子的猴子数量是动态变化的，递归是当n等于1时退出，我们从n==2开始从前向后遍历的过程就相当于做了递归操作
        }                          
        System.out.println(flag + 1); // 因为序号是从1开始的，所有要加一
    }
}