稍微总结一下几个流传的方法，这几天快被这环套死了

  • 循环链表
  • 标记法（暂且这样命名= =）
  • 数学魔法（雾
  • 递归

自己的尝试

其实这里是C语言程序设计那本书上的题， 要求用指针实现，后来百度一下才知道这个问题的背景...

有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子问最后留下的是原来的第几号。

开始我连题意都摸了半个小时才摸清楚（纠结那围成圈儿，最后两人咋整的问题），原来就是个循环

我最终还是选用了 标记法，所有人都乖乖站好，踢出去的人印个章。因为这样虽然比不上循环链表那样形象，但采用模拟，也让人容易接受。然而就这么简单的道理，编出来却Bug不断，到后面还不得已用拙劣的办法去修补，也是令自己汗颜，但不管怎么说，代码都还是要贴的：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int *p,*p2,b[100]= {0};
    p=&b[0];

    int i=0,a,c=0,flag=0;
    scanf ("%d",&a);
    while (c<a-1) //当还剩一人未被踢出时
    {
        p2=p; //恢复指向队头
        while ((p2-p)<a) //每次都遍历一遍人员标签来检查
        {
            if(*p2==0)
            {
                if (flag==1)
                {
                    c++; //回生
                    break;
                }
                //只剩下一个了，跳出循环，此时P2指向的正是余下的人
                if (c==a-1) 
                    break;
                i++;
            }
            if (i==3)
            {
                *p2=1;
                c++;
                i=0;
                //愚蠢的Flag，就是为了防止出现当最后一项为踢出的人，然而不足以引发下一次循环的
                //的再遍历，从而无法指向余下的人，可以用用10来体验这过程
                if (c==a-1 && (p2-p)==a-1)
                {
                    c--; //逆转大法，还能gou
                    flag=1;
                }
            }
            p2++; //指针下移
        }

    }
    printf("余下人为：%d",p2-p+1); //指针相减+1即为序号
    return 0;
}

别人家的算法

数学魔法

#include<stdio.h>
int main()
{
    int n,i,sum=0;
    scanf("%d",&n);
    for(i=2;i<=n;i++) sum=(sum+3)%i;
    printf("%d",sum+1);
    return 0;
}

递归

#include<stdio.h>
int sk(int n)
{
    if(1 == n) return 0 ;   
    return (sk(n-1)+3)%n;
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d",sk(n)+1);
    return 0;
}