每日一题：华为初级题库——报数

　　简单版本的约瑟夫问题。

　　<题目要求>

　　　　有N个小朋友顺序拿了1-N的号，站成一列，从第一个人开始报数（从1开始），念到3的人跳出，报数继续；若末尾的小朋友报完数，第一个人继续报数；直到剩下一个小朋友停止报数。请问最后剩下的一个小朋友，拿的号码是多少？要求能连续输入游戏人数N，每输入一个人数后，就能显示一个结果。

　　思路：能够用数组和链表实现。链表的话，用循环链表和一个临时变量即可。数组的话，用数组存储着小朋友最先的号码，并用到了两个变量，一个变量i实现下一个小朋友的定位，一个变量k实现报号的递增。用第一个变量对人数的求余（i%n）来实现循环，用第二个变量对跳出数字的求余（k%3）来实现循环报数。每找到一个人将数组对应小朋友位置的值置0。当找到了n-1个人之后，就停止报数。

　　计算机实现这个过程的原理，其实可以用现实生活中的状态来讨论，如下图，念到3的小朋友走了，但是他的位置还在那里，我们在进行问题的分析的时候，是按照位置的顺序依次进行的，所以循环遍历的时候，就算3号小朋友已经走了，但是我们还是会对指向这个位置，只是在此处的讨论只需下移，无需报号。

　　易错点分析：

（1）变量i下移一位，来实现对下一个小朋友的定位时，有两种情况：报号k为3（能被3整除，k=k%3=3%3=0）且当前小朋友没有退出（a[i]!=0，因为退出，a[i]就会被置0）；小朋友退出了（a[i]=0）。

一开始，我是将这两种情况合并到一块儿的，但是其实这两种情况是由区别的，前者小朋友还在，所以要继续报号，k要继续增加；后者小朋友不在了，所以k不继续增加，这样就要区分讨论了。

（2）用while(cin>>n)实现循环输入；若要结束继续输入的话，ctrl+z即可。

#include <iostream>

using namespace std;

int main()
{
    int n;
    int i;
    int t3=3;
    int k;
    int outnum;//用于记录已经出去几个人了。
    while(cin>>n)
    {
        int *a=new int[n];
        for(int j=0;j<n;j++)
            a[j]=j+1;
        i=0;
        k=1;
        outnum=0;
        while(1)
        {
            i=i%n;
            k=k%3;
            if(a[i]==0)
                {
                    i++;
                }
            else if(a[i]!=0&&k!=0)
            {
                i++;
                k++;
            }
            else if(k==0)
            {
                a[i]=0;
                i++;
                k++;
                outnum++;
            }
            if(outnum==n-1)
                {
                    outnum=0;
                    break;
                }
        }
        for(int j=0;j<n;j++)
        {
            if(a[j]!=0)
                cout<<a[j]<<endl;
        }
    }
    return 0;
}