约瑟夫问题

思路:

实际上是一个非常巧妙的数学问题。

从结果上来看, 如果只剩最后一个人(最后的幸存者),那么被杀掉一定是它。那么它的当前号码为1,问其原坐标?思考一下新旧人列的下标关系:

Old(k+1) : 
1 2 3 4 5 6 7 --- k + 1 
New(k)
4 5 6    m -1 (s) 1 2 3 

可能的一种形式,其中s是old被杀掉的人的下标。 且s = (m - 1 )% (k + 1) + 1

但不难发现有: old = (new + s - 1) % (k + 1) + 1

综上有逆推式: old =(new + m - 1) % (k + 1) + 1

代码


#include<iostream>
#include<string>
using namespace std;
int Youseuf(int n, int m) {
    if(n == 1) return 1;
    return (Youseuf(n - 1, m) + m - 1 ) % n + 1; 
    // old "- - - - - - - "
    // new "- X - - - - - "
    // old = (new + s - 1) % + 1 (called from 1)
    // where s is the index of old killed people.
}

int main() {
    int n, m;
    cin >> n >> m;
    cout << Youseuf(n, m) << endl;
    return 0;
    
}

Comments