習題8-4 報數(shù) (20 分)
1. 題目摘自
https://pintia.cn/problem-sets/12/problems/337
2. 題目內(nèi)容
報數(shù)游戲是這樣的：有n個人圍成一圈黄伊，按順序從1到n編好號。從第一個人開始報數(shù)锦募，報到m（<n）的人退出圈子儿普；下一個人從1開始報數(shù)，報到m的人退出圈子晃虫。如此下去灭忠，直到留下最后一個人。
本題要求編寫函數(shù)连躏，給出每個人的退出順序編號。
函數(shù)接口定義：
void CountOff( int n, int m, int out[] );
其中n是初始人數(shù)贞滨；m是游戲規(guī)定的退出位次（保證為小于n的正整數(shù)）。函數(shù)CountOff將每個人的退出順序編號存在數(shù)組out[]中拍棕。因為C語言數(shù)組下標是從0開始的晓铆，所以第i個位置上的人是第out[i-1]個退出的。
輸入樣例：
11 3
輸出樣例：
4 10 1 7 5 2 11 9 3 6 8
3. 源碼參考
#include<iostream>
using namespace std;
#define MAXN 20
void CountOff(int n, int m, int out[]);
int main()
{
int out[MAXN], n, m;
int i;
cin >> n >> m;
CountOff(n, m, out);
for (i = 0; i < n; i++)
{
cout << out[i] << " ";
}
cout << endl;
return 0;
}
void CountOff(int n, int m, int out[])
{
int a[MAXN];
int index; // 退出順序編號
int i; // 位置
int cnt; // 累計報數(shù)
i = 0;
while (i < n)
{
a[i++] = 1;
}
index = i = cnt = 0;
while (index < n)
{
if (a[i] == 1)
{
cnt++;
}
if (cnt == m)
{
a[i] = 0;
out[i] = ++index;
cnt = 0;
}
i++;
if (i == n)
{
i = 0;
}
}
return;
}
