从算法到程序之Joseph问题

Posted on 2016-03-16

Joseph问题: 对给定的两个正整数 n,m,编号为1~n的n个人围坐成一圈,从1连续报数,报到m就出局,余下的从当前位置继续从1报数,报到m再次出局,一直到剩下最后一人。求出局的顺序,剩下的人原始编号为多少。 例如n=6,m=5时,出局顺序为5,4,6,2,3,1。

现在给定正整数K个人,n=2k个人氛围两组,编号即为1~k,k+1~n,求最小的m,使得按照joseph规则后出局的k个人恰好都出自后一组。

输入:正整数k 输出:最小的正整数m,使得编号为1~n=2k,围坐在一圈的n个人,循环的依次从1报到m.报到m的出局,出局的k个人编号为k+1~n的组。

如何考虑這个问题呢? 为了方便写程序,我们另编号为0到n-1,n到2k。前k个出局者为原始编号是k~n-1的人。

注意到m=ak+b,a为奇数。1<b<k也是显然。m一定是大于k的,所以才会這么表达,若第一轮报到m的人编号为t,应该满足k<t<n,对a,b进行推演,mk+b,从第一轮报数者编号t=0开始计算到t+m-1除以n的余数,也就是说,一个由n人围坐的圈子开始joseph规则时,从t开始以1报数,到m,(t+m-1)mod(n)就是這一轮中最后报数的人 的编号。

#include<stdio.h>
#include<iostream>
using namespace std;
int joseph(int k){
    int m, t, a = 1, b, i, n;
    while (1){
        for (b = 1; b <= k; b++){
            m = a*k + b, t = 0, n = 2 * k;
        for (i = 1; i <= k; i++){//k轮报数
            t = (t + m - 1) % n;//本轮报数到m-1的人的编号
            if (t<k)//此时的m不符合游戏规则
            break;
            n--;
        }
    if (i>k)
        return m; 本m通过了所有k轮报数
}
a += 2;    
    }    
}
int main(){
    int n;
    cout << "输入参加约瑟夫环的人数(偶数)" << endl;
    cin >> n;
    cout << joseph(n/2) << endl;
    system("pause");
    return 0;
}

蚊子再小也是肉~
本站总访问量 本站访客数