(C++)报数问题

一、实验目的、内容

有n人围坐成一圈（假设他们的编号沿顺时针方向依次为1到n）。编程序，使用数组来存放各数据（人员编号），而后从1号人员开始数起（沿顺时针方向），当数到k时（其中k>1由用户通过cin输入指定），则该号人员被“淘汰出局”；接着仍沿顺时针方向从被淘汰出局者的下一人员又重新从1开始数起，数到k后，淘汰第2个人；如此继续，直到最后剩下一个人时停止。输出先后被“淘汰”的人的编号。

二、实验程序设计及结构

1.需求分析

变量

无符号数n(size_t)表示人数，k(size_t)淘汰的报数，i(size_t)记录报到的数；指针a(unsigned char*)指向数组的首位，q(unsigned char*)指向数组的末位，p(unsigned char*)循环变量。

函数

主函数int main()。

2.设计结构或流程图

1. 输入人数及报数k。
2. 初始化数组及指针。
3. 每次循环用i记录报数，p指向当前报数的人，当i等于零时输出并进入下一次循环。
4. 淘汰了n-1个人后输出最后剩下的人。

三、设计过程

#include <iostream>
using namespace std;
int main()
{
    size_t n, k, i;
    cout << "请输入人数:\n";
    cin >> n;
    cout << "请输入报数k:\n";
F:
    cin >> k;
    if (k < 2)
    {
        cout << "报数k不正确!\n请重新输入:\n";
        goto F;
    }
    signed char *a = new signed char[n], *p = a + n, *q = p;
    do
        *--p = 1;
    while (p > a); // a数组记录第i-1个人是否被淘汰，淘汰为0，未淘汰为1
    --p;
    cout << "淘汰先后顺序:";
    while (--n) // 一共要淘汰n-1个人
    {
        i = k;
        do
            if (++p == q)
                p = a;
        while (i -= *p); // 如果p指向了最后一个人，将p赋值为第一个人
        *p = 0;
        cout << '\t' << p - a + 1;
    }
    cout << "\n最后剩下的人为:";
    do
        if (*--q)
        {
            cout << ++q - a;
            break;
        }
    while (true);
    cout << "号\n";
    system("pause");
    return 0;
}

四、测试分析

第一组

第二组

五、设计的特点和结果

特点：采用指针算法，效率比利用取余运算更高。

结果：输出了淘汰顺序和胜出者。