约瑟夫环问题
- 问题描述
- 数据结构设置
- 过程代码
【数据结构|约瑟夫环问题C++】n个小朋友做成一圈，编号分别是分别为1-n，2号小朋友坐在1号小朋友顺时针方向，3号小朋友坐在2号小朋友顺时针方向……1号小朋友坐在n号小朋友顺时针方向；对于给定输入n、k，从第一位小朋友开始报数，第一位小朋友报数为1，下面的小朋友每次报数增加1，当某一位小朋友报数报到k的整数倍或者报的数的个位数为k时，该小朋友被淘汰出局。最终剩下一位小朋友，该小朋友为获胜者。利用数据结构来简化问题
输入：n、k
输出：获胜的小朋友的编号
分析问题，需要存储的是小朋友的编号、小朋友的状态（是否淘汰出局）、小朋友的报数,环状结构则通过进行mod n实现。结构体设置
因此选择结构体数组来进行数据的存储。
struct Item{
int id;
int num;
bool state;
Item(int _id,int _num,bool _state=true){
id = _id;
num = _num;
state = _state;
}
};
过程代码
经过数据结构的恰当选择，过程已经变得极为简单，只需要找出前一个报数者和后一个报数者的数组下标即可。当两个下标相等时，游戏结束。下面是完整代码：
#include
#include
using namespace std;
struct Item{
int id;
int num;
bool state;
Item(int _id,int _num,bool _state=true){
id = _id;
num = _num;
state = _state;
}
};
int main(){
int n,k;
cin >> n >> k;
vector- loop;
for(int i=0;
i
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔