Question

C语言：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报 数），凡报到3的人退出圈子，最

C语言：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报 数），凡报到3的人退出圈子，最后留下那个是原来的几号？求思路！思路重要！

Answer 1

推荐两种方法：

1. 循环链表。把链表做成一个环，设置一个当前位置的linknode指针pos，初始时pos的数据域为0，pos->next则为1，pos->next->next数据域为2，以此类推。加个计数，从1到3，每次加一操作都移动一次指针（pos=p->next），当计数为3时，从该循环链表中删除该节点（注意保存pos的前一节点，原有p->next=pos，删除时p->next=pos->next;free(pos);pos=p->next;）同时需要注意一点的是，当pos->next=pos时，表明该链表只有一个节点了，也就是你所需要的的最后留下来的那个号。

2. 数组。先定义好一个足够长的数组，并初始化好数组的数据位（填入1~n），与上述类似，加个计数，当为3时把该数据置为一个特殊值（如0），表示已从该数组中删除。依此下去，直到剩下最后一个不为0的值就是你所需要的值（如果不考虑效率的话，每删除一个数据置0后将后边非0数据都往前移动）。

追问

谢谢

Answer 2

第一轮：3的倍数（共33个）去掉，还剩67个
第二轮：3的倍数加1（共33个）去掉，还剩34个
第三轮：3的倍数加2（共32个）去掉，还剩2个
不好意思，最后必定剩下2个，且最后留下来的是1号和2号（从3开始一直到100不是满足3的倍数就是满足3的倍数加1就是满足3的倍数加2，所以全部被去除）