分别使用结构体和数组实现约瑟夫环(围圈报数问题之二)

时间:2022-10-05 11:00:17

  前天用单循环链表实现了约瑟夫环问题,这种方法执行效率高。接下来用另外两种简单的方法实现之。

  方法一:使用数组

  

void main()
{
    int a[81],n,i,counter,num;      //counter用来计算,num用来记录退出的人数
    printf("please input total the number of person:");
    scanf("%d",&n);
    for(i=0;i<n;i++)      //为每个人编号,1~n
    {
        a[i]=i+1;
    }
    for(i=0;i<n;i++)      //打印报数前状态
         printf("%d\t",a[i]);
         printf("\n");
    counter=0;i=0;num=0;
    while(num<(n-1)&&i<n)
    {
        if(a[i]!=0)      //当编号不为0时,计数值加1
            counter++;
        if((counter%3)==0&&a[i]!=0)      //当计数值能被3整除且元素编号不为0时,将编号值置0,num加1******这个地方一开始没有判断a[i]不等于0,
                           //结果出现了逻辑错误 { printf(
"number %d is out\n",a[i]); a[i]=0; num++; if(num==n-1) break;      //如果num数为总数减1即还剩一个人时推出循环 } i++;      //循环数组 if(i==n)      //当报数到最后一名时重新开始报数 { i=0; } } printf("\nthe last person is number ");      //打印操作后剩余人员编号 for(i=0;i<n;i++) if(a[i]!=0) printf("%d\t",a[i]); }

  方法二:使用结构体数组

  

struct person{      //每个元素中定义一个成员存放下一个元素的下标nextp,一个成员存放成员编号number
    int number;
    int nextp;
};

void main()
{
    int n,out,num,i;
    printf("please input the total number of the people:");
    scanf("%d",&n);
    struct person link[n];
    for (i=0;i<n;i++)      
    {
        if(i==n-1) link[i].nextp=0;      //最后一个人的下一个元素位置为第一个元素,形成循环队列
        else link[i].nextp=i+1;      //下一个人的序号
        link[i].number=i+1;      //本人编号
    }
    printf("\n");
    out=0;num=n-1;      //定义out记录退出报数的人数,初始化num为最后一个元素方便从第一个元素开始报数
    while(out<n-1)
    {
        i=0;
        while(i!=3)
        {
            num=link[num].nextp;      //从第一个元素开始报数
            if(link[num].number) i++;      //当编号不为0时,报数加1
        }
        printf("number %d is out\n",link[num].number);      //打印出退出人员编号
        link[num].number=0;      //退出人员编号置0
        out++;
    }
    printf("\nthe last person is number ");
    for(i=0;i<n;i++)
        if(link[i].number!=0) printf("%d\t",link[i].number);
}