约瑟夫问题
题目描述
个人围成一圈,从第一个人开始报数,数到 的人出列,再由下一个人重新从 开始报数,数到 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。
注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 名小朋友,而该题是全部出圈。
输入格式
输入两个整数 。
输出格式
输出一行 个整数,按顺序输出每个出圈人的编号。
样例 #1
样例输入 #1
10 3
样例输出 #1
3 6 9 2 7 1 8 5 10 4
提示
思路
定义一个长度为 n 的一维数组 arr,用来表示队列。
首先,将 1~n 的数依次加入数组中。使用 count 记录当前报数的次数,使用 out 记录已经出队的人数,使用 f 记录是否是第一个出队的人,方便输出空格。
使用一个 while 循环,直到队列为空为止。在循环中,使用 for 循环遍历数组,对于已经出队的人,跳过。对于未出队的人,当报数次数 count 等于 m-1 时,输出其对应的数字,将其在数组中标记为已出队,并将 count 重置为 -1,out 加 1,f 设置为 1。重复此过程直到队列为空。
AC代码
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
int main()
{
int n, m;
int count = 0, out = 0, f = 0;
cin >> n >> m;
int arr[n];
for (int i = 0; i < n; i++)
{
arr[i] = i + 1; // 初始化
// cout << arr[i];
}
while (out < n)
{
for (int j = 0; j < n; j++)
{
if (arr[j] == 0)
{
continue; // 跳过
}
if (count == m - 1)
{
if (f == 1)
{
cout << " ";
}
cout << arr[j];
arr[j] = 0; // 出队
count = -1;
out++;
f = 1;
}
count++;
}
}
return 0;
}
标签:count,输出,出圈,int,题解,出队,P1996,洛谷,报数
From: https://blog.51cto.com/HEX9CF/11960189