选大王

约瑟夫问题

问题来历

据说著名***历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后，39 个***人与Josephus及他的朋友躲到一个洞中，39个***人决定宁愿死也不要被敌人抓到，于是决定了一个***方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须***，然后再由下一个重新报数，直到所有人都***身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人(因为第一个人已经被越过)，并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了人数总和，一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

选大王问题

• 问题描述：
  有n只猴子，按顺时针方向围成一圈选大王(编号从1到n)，从第1号开始报数，一直数到m，数到m的猴子退出圈外，剩下的猴子再接着从 1 开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王。现在告诉你 n 和 m，请帮忙求出哪一只猴子能当大王。
• 输入描述:
  输入包含多组数据。每组数据包含两个正整数 n 和m（1≤ m < n ≤ 10000）。
• 输出描述:
  对应每一组输入，输出猴王的编号 i（1≤i≤n）。

常规解法

构建一个列表，按照报数顺序依次 删除元素，直到只剩下一个元素

    /**
     * 常规算法
     * 序列为 1,2，... ，n
     */
    static int Josephus(int n,int m){

        List<Integer> monkeys=new ArrayList<>();

        for(int i=1;i<=n;i++){
            monkeys.add(i);
        }

        int pos=0;

        while(n>1){
            pos+=m-1;
            pos%=n;
            monkeys.remove(pos);
            n--;
        }

        return monkeys.get(0);
    }

递归解法

假设 对于n,m 已知 k 是当前需要***的人，当前序列为
0，1，... ，k-1, k , k+1, ... , n-1
那么剩下的人分别为
0，1，... ，k-1, k+1, ... , n-1
接下来需要从 k+1 处开始报数，不妨对 k 以前的数 +n, 即：
n, n+1, ... , n+k-1, k+1, ... , n-1
按照报数顺序排列：
k+1, ... , n，n+1, ... , n+k-1
这个序列可看出，仅比正常序列 0，1，... , n-2 多了 k+1

所以有：
假设 josephus(n,m)是序列 0，1，... , n-1循环报数最终剩下的人，
则 josephus(n-1,m)为序列 0，1，... , n-2循环报数最终剩下的人
josephus(n,m)= josephus(n-1,m)+k+1
考虑到运用上述公式时，是对 n,m序列 对k之前的数+n得到的，
因此应当修正为

josephus(n,m)=（ josephus(n-1,m)+k+1）%n

如此即可还原到原始序列。

又因为对于任意 n,m ,初始k值我们是可以求解得到的

k=(m%n)-1

所以

josephus(n,m)=（ josephus(n-1,m)+(m%n)）%n
josephus(n,m)=（ josephus(n-1,m)+m）%n

至此已形成递归
递归截至条件也显而易见

josephus(1,m)=0

注意
此解法针对的是 0, 1, 2, ... , n-1的序列，
但约瑟夫环一般是从1 开始的，即 1, 2， ... , n
所以我们利用 josephus(n,m)求出的结果要 +1才是最终结果。

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);

        while (scanner.hasNext()){
            //递归算法
            System.out.println( JosephusRecursive( scanner.nextInt(), scanner.nextInt() )+1 );
            //常规算法
            // System.out.println( Josephus( scanner.nextInt(), scanner.nextInt() ));
        }
    }

    /**
    * 递归算法
    * 序列为 0,1,2，... ，n-1
    */
    static int JosephusRecursive(int n,int m){

        if(n==1){
            return 0;
        }
        return (JosephusRecursive(n-1,m)+m)%n;
    }

}

递归衍生循环

由 递归法 可知

josephus(n,m)=（ josephus(n-1,m)+m）%n
josephus(1,m)=0

因此有

josephus(n+1,m)=（ josephus(n,m)+m）%（n+1）

将 josephus( ) 简记为 J( )

J ( n+1, m ) = ( J ( n, m ) + m ) % ( n+1 )

由此可以将递归改成循环

      /**
     * 递归衍生循环
     */
    static int JosephusCycle(int n,int m){
        int r=0;
        for(int i=2;i<=n;i++){
            r = (r+m)%i;
        }
        //由于该方法为递归思想推算过来的，上述算法执行完后的结果仍然为 针对序列 0， 1， ... , n-1推算的结果，
        // 因此最终结果需要 +1
        return r+1;
    }

该方法虽然是从递推的结果进一步通过数***算得来的，但是结论反而可以当作一个公式用，只是逻辑上讲没什么道理。

#include<stdio.h>
int main(){//the shorter,the better.
    int n,m,r,i;
    for(;~scanf("%d%d",&n,&m);printf("%d\n",r+1))for(r=0,i=2;i<=n;r=(r+m)%i,i++);
}  

递推公式求解法：

#include <iostream>
using namespace std;

int main() {
    int m, n;
    while (scanf("%d %d", &n, &m) != -1) {
        //对于f(1, m),称王的猴子下标为0
        int index = 0;
        //递推公式f(n, m) = (f(n - 1, m) + m) % n，求出f(2, m),f(3, m)、...、f(n, m)
        for (int i = 2; i <= n; ++i) {
            index = (index + m) % i;
        }
        //我们求出的是下标，需要+1得到序号
        printf("%d\n", index + 1);
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104739822

报数过程模拟实现（超时）

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int m, n, start, count;
    //table[i]记录编号为i + 1的猴子是否还在圈中
    bool table[10001] = {0};
    while (scanf("%d %d", &n, &m) != -1) {
        start = 0;//当前开始报数的人下标
        count = n;//圈中剩余的猴子
        //初始化所有人在圈中
        memset(table, 1, n);
        //模拟报数，直到圈中剩余1个猴子（注意最后退出的时候count == 1，但执行--操作的时候count == 0）
        while (count-- > 1) {
            //模拟一次报数（淘汰一个猴子）
            for (int i = 1; i <= m; ++i) {
                //找到下一个在圈中的猴子
                while (table[start] == false) {
                    start = (start + 1) % n;
                }
                if (i == m) {
                    //报到第m个数的猴子出圈
                    table[start] = false;
                }
                //计数器后移
                start = (start + 1) % n;
            }
        }
        //然后找出唯一剩下的猴子的下标
        while (count < n) {
            if (table[count++]) {
                printf("%d\n", count);
                break;
            }
        }
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104739822

//开向量直接模拟

#include <cstdio>
(802)#include <vector>

using std::vector;

vector<int> A;
int main(int argc, char const *argv[]){
    int n, m;

   while(scanf("%d%d", &n, &m) != EOF){
       if(m == 1){
           printf("%d\n", n);
       }else{
           for (int i = 1; i <= n; ++i) {
               A.push_back(i);
           }
           int pos = m - 1;
           while(A.size() > 1){
               while(pos <= ((int) A.size() - 1)){
                   A.erase(A.begin()+ pos);
                   pos += (m -1);
               }
               int TSize = (int) A.size();
               pos = pos % TSize;
           }
           printf("%d\n",A[0]);
           A.clear();
       }
   }

    return 0;
}

	//有难度，不会...



	while True:



	    try:



	        n, m = list(map(int, input().split()))



	        last = 0



	        for i in range(2, n+1):



	            last = (last+m) % i



	        print(last+1)



	    except:



	        break

while True:
    try:
        n, m = raw_input().split(' ')
        n = int(n)
        m = int(m)
    except:
        break

    last = 0
    for i in range(2, n+1):
        last = (last+m) % i

    print(last+1)

//约瑟夫问题 顺序表最典型的应用

#include
int main(){
    int n, m;
    while(scanf("%d %d",&n,&m) != EOF){
        int  r=0 , i ;
        for(i = 2; i <= n; i++)
            r = (r + m) % i;  //能用数学解决的就不要用算法
        printf("%d\n", r + 1);
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
 
int J(int m, int n)
{
    if(n == 1)
        return 0;
    else
        return ((J(m, n-1) + m) % n);
}
 
int main()
{
    int m, n;
    while(~scanf("%d %d", &n, &m))
    {
        int result = (J(m, n) + 1);
        printf("%d\n", result);
    }
 
    return 0;
}