用c++实现减治法解决约瑟夫问题

约瑟夫问题是一个经典的数学问题，可以用C++的减治法（也称为迭代减半法）算法来求解。以下是使用C++实现的基本步骤：

#include <iostream>
using namespace std;

int josephus(int n, int k) {
    // 检查输入合法性
    if (n <= 0 || k <= 0 || k > n) {
        throw invalid_argument("Invalid input: n and k should be positive integers with k <= n");
    }

    // 减治法核心逻辑
    int steps = 0;
    while (n > 1) {
        steps++;  // 步数加一
        n -= k;   // 每次跳过k个人
        n %= k;   // 更新剩余人数，相当于跳过了已经淘汰的人
    }

    // 返回最终位置
    return steps % n + 1;
}

int main() {
    int n, k;
    cout << "Enter the number of participants (n) and the skip count (k): ";
    cin >> n >> k;

    try {
        int result = josephus(n, k);
        cout << "The last survivor is position " << result << "." << endl;
    } catch (const invalid_argument& e) {
        cerr << "Error: " << e.what() << endl;
    }
    return 0;
}

在这个代码中，首先检查输入的有效性。接着，在`while`循环中，每次增加`steps`表示经过的淘汰轮数，然后将总人数`n`减去`k`并取模，以适应跳过已淘汰的人。当`n`变为1时，跳出循环，返回`steps % n + 1`作为结果，即最后一个幸存者的位置。