C语言出圈问题程序 C++版本

#include<iostream>

using namespace std

int main()

{

    int N, M, K, cot = 0

    cin>>N>>M

    K = N

    int *m = new int[512]

    m[0] = m[1] = 0

    for(int i = 0  i = (i + 1) % N)

    {

        if(m[i] == 0)

        {

            cot++

            if(cot == M)

            {

                m[i] = 1

                K--

                if(K == 0)

                    break

                cout<<i + 1<<" "

                cot = 0

            }

        }

    }

    return 0

}

首先理解题意

设有n个人围坐一圈并按顺时针方向从1到n编号。

从第s个人开始进行1到m的报数, 报数到第m个人, 此人出圈, 再从他的下一个人重新开始1到m的报数,如此进行下去直到所有的人都出圈为止。

现要求按出圈次序,给出这n个人的顺序表p。

木易版答案：

void Josegh(void)

{ int i,j,s1,w

s1=s

for(i=1i<=ni++)

p[i-1]=i

for(i=ni>=2i--)

{ s1=(s1+m-1)%i

if(s1==0) s1=i

w=p[s1-1]

for(j=s1j<ij++)

p[j-1]=p[j]

p[i-1]=w

}

}

这里提出几个广泛流传的错误：

本人在学习此题过程中发现，不管是网上还是书店的一些参考书中，对此题的讲解都有一些错误！本人在这里提出几个广泛流传的错误，希望大家指正！

① 南开上机题或无忧上机题的题干错误！

原题干：

若第i个人报数后出圈，则将p[i]置于数组的倒数第i个位置上，而原来第i+1个至倒数第i个元素依次向前移动一个位置。

举个例子：

套用原题干：

若第10个人报数后出圈，则将p[10]置于数组的倒数第10个位置上，而原来第11个至倒数第10个元素依次向前移动一个位置。

上面这句话显然不对！

而实际上是：

原列队第10个人报数后出圈（即编号为10的人报数出圈），则将p[9]置于数组的倒数第1个位置上，而原来第11个至倒数第1个元素依次向前移动一个位置。

或这么表述：

第1个报数后出圈的人（因为编号为10的人是第1个报数出圈的），将p[9]置于数组的倒数第1个位置上，而原来第11个至倒数第1个元素依次向前移动一个位置。

错误分析：

编题的人没有搞清其实“出圈次序”“出圈人编号”“出圈人所对应的数组下标”是三个不同的概念！

如：第一个出圈的人，出圈次序是1，下标是p[9]，编号是10。

而编题人简单地都用i表示了！显然不对！

这里我认为本句话应该改为：

第i个人报数出圈的人，将“此人的编号”置于数组的倒数第i个位置上。

②市面上卖的谭浩强主编的《三级C语言上机指导》一书中（清华大学出版社2005年7月第1版封皮是红色的价格是22.00元）对此题的解释也有错误：

讲解中说：s1=(s1+m-1)%i的作用是找出报数后出圈人的下标。

本人认为编者也犯了类似的错误：

应该改为：

s1=(s1+m-1)%i的作用是找出报数后出圈人的“编号”。

因为变量s1表示的不是出圈人的所对应的数组下标，而是其“编号”。

清楚变量：

变量i：表示没有出圈的人数。

变量s1：表示出圈人所对应的编号。编号s1=p[s1-1]。

变量w：暂存变量，用于暂时存放刚刚出圈人的编号。

数组p[]：存放出圈人编号的数组。程序结束后，该数组按出圈次序倒序存放出圈人的编号。

思路步骤：

①建立数组，应注意：p[下标]=编号 ；下标=编号-1；编号s1=p[s1-1]。

对应代码是：for(i=1i<=ni++) p[i-1]=i

②倒序循环for(i=ni>=2i--)，找出出圈人的“编号”s1。

对应的算法是通过求余得到的！s1=(s1+m-1)%i

③将刚出圈人的编号先寄存在暂存变量中。

④将刚出圈的人之后至原队列最后一个未出圈的人依次在数组中前移一位。对应的代码是：for(j=s1j<ij++) p[j-1]=p[j]

⑤将刚出圈人的编号放置在最后一个未出圈的人的后面，即p[i-1]的位置上。

注意事项：

①此题有两种变形，差别在于出圈人编号的存放顺序。考生应注意考题中是哪种变形！

形式一：

若第i个人报数后出圈，则将此人编号置于数组的倒数第i个位置上，而原来第i+1个至倒数第i个元素依次向前移动一个位置；即第1个出圈的编号存放在p[n-1]中，第2个出圈的编号存放在p[n-2]中,直至第n个出圈的编号存放在p[0]中。

对应的void WriteDat(void) 函数中的循环语句是for(i=N-1i>=0i--)

形式二：

第1个出圈的编号存放在p[0]中,第2个出圈的编号存放在p[1]中,直至第n个出圈的编号存放在p[n-1]中。

对应的void WriteDat(void) 函数中的循环语句是for(i = 0 i <= N - 1 i++)

上面答案是形式一的答案。

若遇到形式二，考生须在原有答案的基础上再增加两个循环以使循序颠倒过来！

for(i=0,j=n-1i<n,j>=0i++,j--) /*也可改为for(i=0,j=n-1i<ni++,j--) */

q[j]=p[i]

for(i=0i<ni++)

p[i]=q[i]

②由于求余的作用，当报数人正好到最后一个人时s1为0，故要有if(s1==0) s1=i

③根据题意，开始时莫忘设置s1=s

---