「C++代码实现」栈结构实现约瑟夫环游戏 |21xrx.com

2023-07-08 13:04:29 深夜i -- --

C++ 代码栈结构约瑟夫环游戏

约瑟夫环游戏是一个古老的数学问题，其以古罗马历史学家约瑟夫斯的名字命名，问题的描述如下：

首先，编号为1到N的N个人围成一圈，约定从编号为k的人开始报数，数到m的那个人出列，他的下一个人重新从1开始报数，直到所有人都出列为止。由于出列的顺序与报数起始点k、出列的间隔m都有关，因此约瑟夫环游戏问题的一般形式是：

已知N个人（N>0），从编号为k的人开始报数，数到m的那个人出列，他的下一个人重新从1开始报数，数到m的那个人再出列，直到所有人都出列为止。请写出一段C++代码，实现约瑟夫环游戏。

思路分析：

本题需要用到栈这种数据结构，我们可以使用一个栈来模拟此游戏。首先，在栈中将所有人按照编号从1到N依次插入，然后从栈顶开始报数，当数到第m个人时，将其从栈中弹出，并输出其编号。接下来顺次报数，直到所有人都被弹出栈为止。

代码实现：

下面是一段实现约瑟夫环游戏的C++代码：

#include

using namespace std;

void josephus(int n, int m, int k) {

stack st;

for (int i = n; i >= 1; --i) {

st.push(i);

}

int count = 0, popCount = 0;

while (!st.empty()) {

int cur = st.top();

st.pop();

++count;

if (count == m) {

++popCount;

cout << cur << " ";

count = 0;

} else {

st.push(cur);

}

if (popCount % n == 0)

break;

}

int main() {

int n, m, k;

cout << "请输入总人数N、出列间隔M和报数起点K: " << endl;

cin >> n >> m >> k;

josephus(n, m, k);

return 0;

}

通过上面的代码实现，我们可以输入总人数N、出列间隔M和报数起点K，就可以得到具体的出列顺序。在程序中使用了stack数据结构，模拟约瑟夫环游戏整个过程，并在最后输出了出列的顺序。

上一篇: idea打包java可执行jar包

下一篇: C++黑马程序员教你写代码

()

相似文章