约瑟夫问题求m使自己是最后一人

Question

假设正在游玩约瑟夫游戏，从你开始报数，游戏规则与课上讲述一致，现在你想确保你是最后一个出列的玩家，如果由你设置m（即每报几个数出列一人），你应该如何设置m来确保自己的胜利？如何在确保时间复杂度，计算的开销等因素下，尽量进行优化的选取。可以通过所附的代码进行你所设想算法的验证。
要求

#include<iostream>
using namespace std;
enum boolean { FALSE, TRUE };
#define DefaultSize 100

template<class T>
class Vector
{
private:
    T* elements;
    int ArraySize, VectorLength;
    void GetArray(void);
public:
    Vector(int Size = DefaultSize);
    ~Vector(void) { delete[] elements; }
    T Getnode(int i)
    {
        return(i < 0 || i >= VectorLength) ? NULL : elements[i];
    }
    boolean Insert(T& x, int i);
    boolean Remove(int i);
};

template<class T>
void Vector<T>::GetArray(void)
{
    elements = new T[ArraySize];
    if (elements == NULL) { cerr << "Memory Allocation Error" << endl; }
}

template<class T>
Vector<T>::Vector(int sz)
{
    if (sz <= 0)
        cerr << "Invalid Array Size" << endl;
    else
    {
        ArraySize = sz;
        VectorLength = 0;
        GetArray();
    }
}

template<class T>
boolean Vector<T>::Insert(T& x, int i)
{
    if (VectorLength == ArraySize)
    {
        cerr << "overflow" << endl; return FALSE;
    }
    else if (i<0 || i>VectorLength)
    {
        cerr << "position error" << endl; return FALSE;
    }
    else
    {
        for (int j = VectorLength - 1; j >= i; j--)
            elements[j + 1] = elements[j];

        elements[i] = x;
        VectorLength++;
        return TRUE;
    }
}

template<class T>
boolean Vector<T>::Remove(int i)
{
    if (VectorLength == 0)
    {
        cerr << "Vector is empty" << endl; return FALSE;
    }
    else if (i<0 || i>VectorLength - 1)
    {
        cerr << "position error" << endl; return FALSE;
    }
    else
    {
        for (int j = i; j < VectorLength - 1; j++)
            elements[j] = elements[j + 1];
        VectorLength--;
        return TRUE;
    }
}


void Josephus(Vector<int>& P, int n, int s, int m)
{
    int k = 1;
    for (int i = 0; i < n; i++) { P.Insert(k, i); k++; }
    int s1 = s;
    for (int j = n; j >= 1; j--)
    {
        s1 = (s1 + m - 1) % j;
        if (s1 == 0) s1 = j;
        int w = P.Getnode(s1 - 1);
        P.Remove(s1 - 1);
        P.Insert(w, n - 1);
    }
}

int findM(int n, int s)
{
    /////////////////////////////////////////////////
    // Code here
    /////////////////////////////////////////////////
}

int main(void)
{
    int n, s, m;
    cout << "Input total number, start index" << endl;
    cin >> n >> s;
    m = findM(n, s);
    Vector<int> P(n);
    Josephus(P, n, s, m);
    cout << "The index of last member is:" << endl;
    cout << P.Getnode(n - 1) << " ";
    return 0;
}

1）基于附件代码所完成的代码；2）word文档一份，简述你的设计思路，并说明为什么觉得这个设计合理。

Answer 1

约瑟夫问题是经典的数学问题，在游戏中也经常使用。其基本思想是：有n个人围成一圈，从第s个人开始报数，报到第m个人出列，接着从下一个人开始报数，报到第m个人出列，直到所有人都出列为止，问最后剩下的是第几个人？

解决约瑟夫问题的常见方法是通过模拟游戏过程。在附件代码中，Josephus函数通过Vector实现了一个列表，并按照游戏规则依次将人出列，最终输出最后一人的编号。为了确保自己是最后一个出列的人，需要选择合适的报数m。因此，我们需要设计一个算法来计算合适的m。

我的设计思路如下：

首先，我们需要找到一个与m有关的方程式，使得当m取不同的值时，最后一个出列的人的编号会发生变化。根据约瑟夫问题的定义，第一次出列的人是第(s+m-1)%n个人，第二次出列的人是从第(s+m)%n开始，以此类推。因此，当报数为m时，最后一个出列的人的编号应该是：

f(n, m) = (f(n-1, m) + m) % n

其中f(n, m)表示n个人中，以m为报数时最后一个出列的人的编号。

由此可以得出递归的解决方案：

int findM(int n, int s)
{
if (n == 1) { return 1; }
else { return (findM(n - 1, s) + s - 1) % n + 1; }
}

这个算法的时间复杂度为O(n)，空间复杂度为O(1)。

我们也可以采用非递归的方法进行计算，这样可以避免调用栈的使用，降低空间开销。具体实现如下：

int findM(int n, int s)
{
int m = 0;
for (int i = 2; i <= n; i++) { m = (m + s) % i; }
return m + 1;
}

该算法的时间复杂度为O(n)，空间复杂度为O(1)。

综上，我们可以通过递归或非递归的方式计算出合适的m值，从而确保自己是最后一个出列的人。
以下是基于给出的代码补充完整的代码，其中 findM() 函数用于求出最后一个出列的玩家的编号：

#include <iostream>
using namespace std;

enum boolean { FALSE, TRUE };
#define DefaultSize 100

template<class T>
class Vector {
private:
    T* elements;
    int ArraySize, VectorLength;
    void GetArray(void);

public:
    Vector(int Size = DefaultSize);
    ~Vector(void) { delete[] elements; }
    T Getnode(int i) { return (i < 0 || i >= VectorLength) ? NULL : elements[i]; }
    boolean Insert(T& x, int i);
    boolean Remove(int i);
};

template<class T>
void Vector<T>::GetArray(void) {
    elements = new T[ArraySize];
    if (elements == NULL) {
        cerr << "Memory Allocation Error" << endl;
    }
}

template<class T>
Vector<T>::Vector(int sz) {
    if (sz <= 0) {
        cerr << "Invalid Array Size" << endl;
    } else {
        ArraySize = sz;
        VectorLength = 0;
        GetArray();
    }
}

template<class T>
boolean Vector<T>::Insert(T& x, int i) {
    if (VectorLength == ArraySize) {
        cerr << "overflow" << endl;
        return FALSE;
    } else if (i<0 || i>VectorLength) {
        cerr << "position error" << endl;
        return FALSE;
    } else {
        for (int j = VectorLength - 1; j >= i; j--) {
            elements[j + 1] = elements[j];
        }

        elements[i] = x;
        VectorLength++;
        return TRUE;
    }
}

template<class T>
boolean Vector<T>::Remove(int i) {
    if (VectorLength == 0) {
        cerr << "Vector is empty" << endl;
        return FALSE;
    } else if (i<0 || i>VectorLength - 1) {
        cerr << "position error" << endl;
        return FALSE;
    } else {
        for (int j = i; j < VectorLength - 1; j++) {
            elements[j] = elements[j + 1];
        }

        VectorLength--;
        return TRUE;
    }
}

void Josephus(Vector<int>& P, int n, int s, int m) {
    int k = 1;

    for (int i = 0; i < n; i++) {
        P.Insert(k, i);
        k++;
    }

    int s1 = s;

    for (int j = n; j >= 1; j--) {
        s1 = (s1 + m - 1) % j;

        if (s1 == 0) {
            s1 = j;
        }

        int w = P.Getnode(s1 - 1);
        P.Remove(s1 - 1);
        P.Insert(w, n - 1);
    }
}

int findM(int n, int s) {
    int m = 1;
    while (TRUE) {
        Vector<int> P(n);
        Josephus(P, n, s, m);
        if (P.Getnode(n - 1) == 1) {
            break;
        }
        m++;
    }
    return m;
}

int main(void) {
    int n, s, m;
    cout << "Input total number, start index" << endl;
    cin >> n >> s;
    m = findM(n, s);
    Vector<int> P(n);
    Josephus(P, n, s, m);
cout << "The index of last member is:" << endl;
cout << P.Getnode(n - 1) << " ";
return 0;
}

int findM(int n, int s)
{
// 每轮游戏中，剩余的人数不断减少，因此不妨从 n 开始往下枚举 m 的值，直到剩余最后一个人的时候，m 的值就是我们要找的解
for (int m = n; ; m++) {
// 通过 Josephus 函数来计算，返回最后一个人的编号
Vector<int> P(n);
Josephus(P, n, s, m);
int last_index = P.Getnode(n - 1);
// 如果最后一个人的编号为 1，说明当前的 m 值是解
if (last_index == 1) {
return m;
}
}
}

// Josephus 函数不变

如果对您有帮助，请给与采纳，谢谢。