Question

C++程序疑问

选举猴王问题：N 只猴子围成一圈，顺序编号1至N。从编号为1的猴子开始依次报数，报数m 的猴子就退出圈子，接着再报，报数m 的猴子再退出圈子，依次继续下去，圈子最后所剩的一只猴子为猴王，它原先的编号是几？
我的思路是：
1) 使用一维数组存放猴子从1到n的编号，定义参加选举猴王的最多猴子数为40。
2) i为每次循环时计数变量，k为按1,2,3,…m报数时的计数变量，t表示退出的猴子数。依次将退出的猴子对应的数组元素置0，直到只剩下一只猴子。
3) 找出数组中不为0的a[i]，输出该数。
写出的程序：
#include<iostream>
using namespace std;
void main()
{
int a[41],i=0,k=0,n=0,m=0,t=0;
cout<<"请输入参选的猴子数n和所报数m：";
cin>>n>>m;
for(i=1;i<=n;i++)
a[i]=i;
i=m;
for(t=0;t<n;)
{
for(k=i,t=0;k<=n;k=k+m)
a[k]=0,t++;
i=k/n;
}
for(i=1;i<=n;i++)
if(a[i]!=0)
k=i;
cout<<"猴王为："<<k<<"号"<<endl;
}
我知道第三个for中的k=k+m错了，但不知道怎么改。求大神指点。

Answer 1

思路没问题，但考虑不周，编码时细节出错。最主要是不能用k=k+m的算法，经过多轮循环之后，已经有很多猴子退出了，那么k和k+m之间剩下的不可能还是m只猴子了，事实上需要一只一只猴子查是还在圈子中还是退出了。

另外i=k/n，LZ自己能说清楚这是什么吗？

然后，C语言的计数系统（包括下标）都是从0开始的，自然语言和其他一些像VB语言是从1开始的，计数和循环的初值是0是1，最后判断表达式是用小于还是小于等于，LZ需要揣摩一下，如果要认真掌握C，最好适应一下从0开始的方式。

以下给的是第二个for大循环的代码

k=1;    // 猴子下标，根据 LZ 从 1 开始的
for(t=0; t<n-1; )    // 要退出的是 n-1 只猴子，不是 n 只
{
    for(i=0; i<m; )    // i 报数，报到 m 退出内循环，表示找到一只该退出的猴子
    {
        if(k>n)        // k 猴子下标，这个使 k 超过 n 之后从 1 继续
            k = 1;
        if(a[k]==0)    // 猴子 a[k] 早已退出，跳过
            k++;
        else
            i++;        // 报数 + 1
    }
    a[k] = 0;   // 让猴子 a[k] 退出。
    t++;    // 退出猴子数 + 1
}

追问

如果a【k】！=0，则i++，开始报下一个数，可是这时候判断的还是上一个猴子

追答

哦，Sorry！你是对的，报数完了，每次k都要进到下一个的

k=1;    // 猴子下标，根据 LZ 从 1 开始的
for(t=0; t<n-1; )    // 要退出的是 n-1 只猴子，不是 n 只
{
    for(i=0; i<m; )    // i 报数，报到 m 退出内循环，表示找到一只该退出的猴子
    {
        if(k>n)        // k 猴子下标，这个使 k 超过 n 之后从 1 继续
            k = 1;
        //if(a[k]==0)    // 猴子 a[k] 早已退出，跳过
        //    k++;
        if(a[k]!=0)
            i++;        // 报数 + 1
        k++;
    }
    a[k-1] = 0;   // 让猴子 a[k-1] 退出，注意前面的 k++ 使退出的下标变成 k-1 了。
    t++;    // 退出猴子数 + 1
}

Answer 2

你的m都没有变··改什么··