回 帖 发 新 帖 刷新版面

主题:转圈相除

大家好!我在做作业是时碰见这样一个题:有人围成一圈(编号为1到17),从第1号开始进行1,2,3报数,凡报3者退出,写一个人又从1开始报数……直到最后只剩下一个人为止。请问此人原来的位置是多少号?把我编死了!我现在没辙了!请高手帮帮忙!感激不尽!

回复列表 (共11个回复)

沙发

你试试这样..
定义一个整数数组.
0表示还在圈里.
1表示已退出

令设循环,内循环内定义一变量用来计算圈里的人数.当这人数是3的倍数,设该数组元素为1.
外循环,当圈里的人数等于1,结束.

板凳

约瑟夫环问题,可以找数据结构的书来参考,一般是链表的经典入门例题

3 楼


那个数据结构我们下学期才学呢!

4 楼


哦!好的!我试试看!谢了哦![em8]

5 楼

[code=c]
#include <iostream>
int ChuQuan(int Num)//Num为总人数
{
    int *arrayTemp=new int[Num+1];//定义一个标志位数组 1表示已出圈
    for(int i=0; i<Num+1; ++i) arrayTemp[i]=0;//标志位清0 只用arrayTemp[1]~arrayTemp[Num]
    int count=0;//计数,计出圈的个数
    int indexNum=0;//记录最后出圈的下标
    for(int j=1,k=0;;)
    {
        if(Num-count==2) break;//只剩下2个人无法再出圈
        if(1==arrayTemp[j]){j++;continue;}//此人已出圈,继续
        if(j>Num) j-=Num;
        if(arrayTemp[j]==0) k++;
        if(k==3) {arrayTemp[j]=1;indexNum=j;count++;k=0;std::cout<<"出圈:"<<j<<std::endl;}
        j++;
    }

    std::cout<<"出圈结束"<<std::endl;

    delete[]arrayTemp;
    return indexNum;
}

int main()
{
    int num=17;
    std::cout<<ChuQuan(num);
}[/code]

随便写了个程序 仅供参考

6 楼


哦!很好!多谢啊!可是您能不能写个C语言版的吗?这个我看的不是很明白!感激不尽……
哦!我也写了一个!但是不能打印出来东西!我有检查不出来那出了问题?请您指教!谢谢……
#include <stdio.h>
#define  N   18

main()
{
    int i, t, n=N, m;
    int a[N]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};

L:
    m=(n-1)-(n-1)/3;
    for (i=1; i<n; i++)
    {
        if (i%3!=0)
            for (t=1; t<=m; t++)
                a[t]=a[i];
    }


    if ((n-1)%3==2)
    {
        a[1]=a[t-1];
        a[2]=a[t];
        for (i=3; i<=m; i++)
        {
            t=i;
            a[i]=a[t-2];
        }
    }
    else if ((n-1)%3==1)
    {
        a[1]=a[t];
        for (i=2; i<=m; i++)
        {
            t=i;
            a[i]=a[t-1];
        }
    }
    else if ((n-1)%3==0)
    {
        for (i=1; i<=m; i++)
        {
            t=i;
            a[i]=a[t];
        }
    }

        n=m+1;
        if (n!=1)
            goto L;
        printf("此人原来的位置为:%d",a[t]);
}[em8]

7 楼

写点注释吧,看着都晕了。
而且为什么要goto呢?这明明是while循环嘛

8 楼

[code=c]
#include<stdio.h>
#include<malloc.h>
int ChuQuan(int Num)//Num为总人数
{
    //int *arrayTemp=new int[Num+1];//定义一个标志位数组 1表示已出圈
    int *arrayTemp=(int *)malloc((Num+1)*sizeof(int));
    
    for(int i=0; i<Num+1; ++i) arrayTemp[i]=0;//标志位清0 只用arrayTemp[1]~arrayTemp[Num]
    int count=0;//计数,计出圈的个数
    int indexNum=0;//记录最后出圈的下标
    for(int j=1,k=0;;)
    {
        if(Num-count==2) break;//只剩下2个人无法再出圈
        if(1==arrayTemp[j]){j++;continue;}//此人已出圈,继续
        if(j>Num) j-=Num;
        if(arrayTemp[j]==0) k++;
        if(k==3) {arrayTemp[j]=1;indexNum=j;count++;k=0; printf("出圈:%d\n",j); }//std::cout<<"出圈:"<<j<<std::endl;
        j++;
    }

    //std::cout<<"出圈结束"<<std::endl;
    printf("出圈结束");

    //delete[]arrayTemp;
    free (arrayTemp);
    return indexNum;
}

int main()
{
    int num=17;
    //std::cout<<ChuQuan(num);
    printf("%d",ChuQuan(num));
}[/code]

9 楼


我帮你改写成C语言版的了

10 楼

我发的第一个帖子就是约瑟夫环的问题

但是那个是C++的

C的百度下,很多。一般书上也有

我来回复

您尚未登录,请登录后再回复。点此登录或注册