题目描述:
n(n<20)个人站成一圈,逆时针编号为 1~n。有两个官员,A从1开始逆时针数,B从n开始顺时针数。在每一轮中,官员A数k个就停下来,官员B数m个就停下来(两个官员有可能能停在同一个人上)。接下来被官员选中的1个或2个人离开队伍。
输入格式 输入n ,k ,m ,可能有多组数据,以 0 0 0结尾。
输出格式 输出每轮里被选中的人的编号(如果有两个人,先输出被A选中的)。输出的每个数应正好占3列。样例中的“ ␣ ”代表一个空格。
输入样例:
10 4 3
0 0 0
输出样例:
␣␣4␣␣8,␣␣9␣␣5,␣␣3␣␣1,␣␣2␣␣6,␣10,␣␣7
思路:一圈n个人可以看成一个循环队列,设置n个标志位来表示某个人有没有被选中并离开队伍,只有标志位为false的元素才是循环队列的有效元素。设置两个游标表示官员A和B当前所指向的元素,每次输出就是将A的游标向后循环移动k位,B的游标向前循环移动m位(移动过程中跳过无效元素)并输出,将输出元素的标志位设置为false,直至循环队列中所有元素标志均为false。
个人代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k, m, A, B;
while(cin >> n >> k >> m && n)
{
//当前所数到的元素下标
A = -1, B = n;
//当前所属到的元素个数
int cntA = 0, cntB = 0;
vector<bool>flagArr(n, false);
vector<bool>flagTrue(n, true);
bool flagSta = true;
while(flagArr != flagTrue)
{
if (!flagSta)
cout << ",";
flagSta = false;
//A数到下k个
while (cntA < k)
{
do
{
A = (A + 1) % n;
}while(flagArr[A]);
++cntA;
}
//B数到下m个
while (cntB < m)
{
do
{
B = (n + B - 1) % n;
}while(flagArr[B]);
++cntB;
}
cntA = cntB = 0;
flagArr[A] = flagArr[B] = true;
if (A == B)
printf("%3d", A + 1);
else
printf("%3d%3d", A + 1, B + 1);
}
printf("\n");
}
return 0;
}
参考代码:
#include<stdio.h>
#define maxn 25
int n, k, m, a[maxn];
// 逆时针走t步,步长是d(-1表示顺时针走),返回新位置
int go(int p, int d, int t) {
while(t--) {
do { p = (p+d+n-1) % n + 1; } while(a[p] == 0); // 走到下一个非0数字
}
return p;
}
int main() {
while(scanf("%d%d%d", &n, &k, &m) == 3 && n) {
for(int i = 1; i <= n; i++) a[i] = i;
int left = n; // 还剩下的人数
int p1 = n, p2 = 1;
while(left) {
p1 = go(p1, 1, k);
p2 = go(p2, -1, m);
printf("%3d", p1); left--;
if(p2 != p1) { printf("%3d", p2); left--; }
a[p1] = a[p2] = 0;
if(left) printf(",");
}
printf("\n");
}
return 0;
}