首页 > 试题广场 > Joseph 题目描述: 原始的Joseph问题的描述如下:
[填空题]
Joseph
题目描述:
原始的Joseph问题的描述如下:有n个人围坐在一个圆桌周围,把这n个人依次编号为1,…,n。从编号是1的人开始报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m个人又出列,…,如此反复直到所有的人全部出列为止。比如当n=6,m=5的时候,出列的顺序依次是5,4,6,2,3,1。
现在的问题是:假设有k个好人和k个坏人。好人的编号的1到k,坏人的编号是k+1到2k。我们希望求出m的最小值,使得最先出列的k个人都是坏人。
输入:
仅有的一个数字是k(0 < k <14)。
输出:
使得最先出列的k个人都是坏人的m的最小值。
输入样例:
4
输出样例:
30
程序:
#include <stdio.h>
long k, m, begin;
int check(long remain){
    long result = (  1  ) % remain;
    if (  2  ){
        begin = result; return 1;
    }
    else return 0;
}
int main( ){
    long i, find = 0;
    scanf("%ld", &k);
    for (m = k;   3  ; m++){
        find = 1; begin = 0;
        for (i = 0; i < k; i++)
            if (!check(  4  )){
                find = 0; break;
            }
    }
    printf("%ld\n",   5  );
    return 0;
}

经典约瑟夫问题,首先从main函数开始解释,枚举m直到找到一个m满足前k个人都在坏人之后被杀死,第二层循环枚举死了几个人,然后函数check内部变量即为当前还剩多少人,所以表示为2*k-i,然后从begin开始往后数m个数,对m取模模拟一下得到死了谁,死的那个人不能在前k个人中,因为begin和取模都是从0开始的,所以坐标向前移一位,就是begin+m-1 % remain为最后那个人,当找到第一个m满足k个人都活下来了,然后在循环跳出时因为m又加了1所以答案是m-1
发表于 2019-10-10 19:26:36 回复(0)