[已解决]关于约瑟夫环的问题，不知道哪里出错了求助啊

798487012 · 发表于 2018-10-27 18:32:02

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

感谢大佬指教

题目如下，设有n个人围成一圈，从编号为m的人开始由1开始报数，每次报到数k的人退出游戏，后面的人从1开始报数，求最后剩下的人的编号。

我的想法是每次数到k的人标记为0，下次报数的人为0是直接跳过去，最后输出数组，数值不为0的元素，就是剩下那个人的编号，但是我的程序运行的结果每次都是我初始的m值，求大佬帮忙看看

#include<stdio.h>

#define N 100

int main()
{
        int a[N],n,m,k,i,index;
        int step =1;//计步器
        int count = 0;//退出的人数
        printf("输入一个数令它为总人数n\n");                        //队列中的人数
        scanf("%d",&n);

        printf("输入一个数令它为初始编号m\n");                        //从编号为m的人开始数
        scanf("%d",&m);

        printf("输入一个数令它为数到k时退出\n");                //数到k的人退出
        scanf("%d",&k);
        index=(m-1);                                                                        //a[index]为编号m的值

        for(i=0;i<n;i++)
        {
                a[i]=i+1;
        }

        while(count<(n-1))                                                                //循环条件，退出的人数为count
        {
                step++;
                index=(++index)%n;
                
                if(step=k)
                {
                        a[index]=0;
                        step=0;
                        count++;
                }
                while(a[index]=0)
                {
                        index++;
                }
                
        }
        
        for(i=0;i<n;i++)
        {
                a[i];
        printf("%2d",a[i]);                                                                //打印此时数组里所有的数值，剩下不为0的编号为最后一个剩下的
        }
        
        printf("\n共退出%d人\n",count);
        
        return 0;
}

最佳答案

月排行榜 / 总排行榜

Mongen

2018-10-27 20:39:28

#include<stdio.h>

#define N 100

int main()
{
int a[N],n,m,k,i,index;
int step =1;//计步器
int count = 0;//退出的人数
printf("输入一个数令它为总人数n\n");                      //队列中的人数
scanf("%d",&n);

printf("输入一个数令它为初始编号m\n");                      //从编号为m的人开始数
scanf("%d",&m);

printf("输入一个数令它为数到k时退出\n");             //数到k的人退出
scanf("%d",&k);
index=(m-1);                                                                      //a[index]为编号m的值

for(i=0;i<n;i++)
{
      a[i]=i+1;
}

while(count<(n-1))                                                             //循环条件，退出的人数为count
{
      step++;
      index=(++index)%n;

      if(step==k)
      {
         a[index]=0;
         step=0;
         count++;
      }
      while(a[index+1]==0 && a[index]==0)//要考虑当数组中连续为0时，要跳过值为零的那一个元素
      {
         index++;
         index=index%n;
      }

}

for(i=0;i<n;i++)
{
      a[i];
      printf("%2d",a[i]);                                                             //打印此时数组里所有的数值，剩下不为0的编号为最后一个剩下的
}

printf("\n共退出%d人\n",count);

return 0;
}

跳转到最佳答案楼层

798487012 · 发表于 2018-10-27 18:38:07

我估计是判断a【index】的值为0的时候出问题了

claws0n · 发表于 2018-10-27 19:58:19

#include<stdio.h>

#define N 100

int main()
{
    int a[N], n, m, k, i, index;
    int step = 1; 
    int count = 0; 
    printf("输入一个数令它为总人数n\n");  
    scanf("%d",&n);

    printf("输入一个数令它为初始编号m\n"); 
    scanf("%d",&m);

    printf("输入一个数令它为数到k时退出\n"); 
    scanf("%d",&k);
    index = m-1;

    for(i = 0; i < n; i++)
    {
        a[i] = i+1;
    }

    while( count < n-k+1 )
    {
        while(a[index] == 0)
        {
            index = (++index) % n;
        }

        if(step == k)
        {
            a[index] = 0;
            count++;
            step = 0;
        }
        
        index = (++index) % n;
        step++;
    }
    
    for(i = 0; i < n; i++)
    {
                printf("%2d ",a[i]);
    }
    
    printf("\n共退出%d人\n", count);
    
    return 0;
}

Mongen · 发表于 2018-10-27 20:39:28

这个最佳答案由 Mongen 给出，感谢 Mongen 的回答。

单击隐藏图章

#include<stdio.h>

#define N 100

int main()
{
int a[N],n,m,k,i,index;
int step =1;//计步器
int count = 0;//退出的人数
printf("输入一个数令它为总人数n\n");                      //队列中的人数
scanf("%d",&n);

printf("输入一个数令它为初始编号m\n");                      //从编号为m的人开始数
scanf("%d",&m);

printf("输入一个数令它为数到k时退出\n");             //数到k的人退出
scanf("%d",&k);
index=(m-1);                                                                      //a[index]为编号m的值

for(i=0;i<n;i++)
{
      a[i]=i+1;
}

while(count<(n-1))                                                             //循环条件，退出的人数为count
{
      step++;
      index=(++index)%n;

      if(step==k)
      {
         a[index]=0;
         step=0;
         count++;
      }
      while(a[index+1]==0 && a[index]==0)//要考虑当数组中连续为0时，要跳过值为零的那一个元素
      {
         index++;
         index=index%n;
      }

}

for(i=0;i<n;i++)
{
      a[i];
      printf("%2d",a[i]);                                                             //打印此时数组里所有的数值，剩下不为0的编号为最后一个剩下的
}

printf("\n共退出%d人\n",count);

return 0;
}

Mongen · 发表于 2018-10-27 20:42:14

//你的需要注意==别写成=，这是错误的一个点。
while(a[index+1]==0 && a[index]==0)//要考虑当数组中连续为0时，要跳过值为零的那一个元素
      {
         index++;
         index=index%n;
      }
这段代码要考虑到当数组元素连续为0时，需要跳过为零的代码。我运行没问题，你再试试。

798487012 · 发表于 2018-10-27 21:01:23

Mongen 发表于 2018-10-27 20:42
//你的需要注意==别写成=，这是错误的一个点。
while(a==0 && a==0)//要考虑当数组中连续为0时，要跳 ...

感谢大佬！！怪不得运行结果出错呢，学到了哈哈

798487012 · 发表于 2018-10-27 21:01:54

claws0n 发表于 2018-10-27 19:58

再次感激大佬哦

claws0n · 发表于 2018-10-27 21:04:00

798487012 发表于 2018-10-27 21:01
再次感激大佬哦

他的结果错误

798487012 · 发表于 2018-10-27 21:48:00

claws0n 发表于 2018-10-27 21:04
他的结果错误

我自己重新修改下了，和我验算的结果一样，主要是他告诉我哪里出错了的问题哦

798487012 · 发表于 2018-10-27 21:51:30

claws0n 发表于 2018-10-27 21:04
他的结果错误

$@B5S_4$PW~C10~{MG([4JOD.png$

大佬你的结果好像不一样

798487012 · 发表于 2018-10-27 21:56:04

claws0n 发表于 2018-10-27 21:04
他的结果错误

这是我修改后的，结果和我验算的一样

#include<stdio.h>

#define N 100

int main()
{
        int a[N],n,m,k,i,index;
        int step =1;//计步器
        int count = 0;//退出的人数
        printf("输入一个数令它为总人数n\n");                        //队列中的人数
        scanf("%d",&n);

        printf("输入一个数令它为初始编号m\n");                        //从编号为m的人开始数
        scanf("%d",&m);

        printf("输入一个数令它为数到k时退出\n");                //数到k的人退出
        scanf("%d",&k);
        index=(m-1);                                                                        //a[index]为编号m的值

        for(i=0;i<n;i++)
        {
                a[i]=i+1;
        } 

        while(count<(n-1))                                                                //循环条件，退出的人数为count
        {
                step++;
                index=(++index)%n;                                                        //在不大于n里循环
                
                while(a[index]==0)
                {
                        index=(++index)%n;
                }
                if(step==k)
                {
                        a[index]=0;
                        step=0;
                        count++;
                }
                
                
        }
        
        for(i=0;i<n;i++)
        {
                a[i];
        printf("%2d",a[i]);                                                                //打印此时数组里所有的数值，剩下不为0的编号为最后一个剩下的
        }
        
        printf("\n共退出%d人\n",count);
        
        return 0;
}

claws0n · 发表于 2018-10-27 22:11:57

本帖最后由 claws0n 于 2018-10-27 22:34 编辑

798487012 发表于 2018-10-27 21:56
这是我修改后的，结果和我验算的一样

哦，用经典案例测试的，输出多一个而已，改一改就好。
有问题你又不说，不明白又不问。
架构不是很好

#include<stdio.h>

#define N 100

int main()
{
    int a[N], n, m, k, i, index;
    int step = 1; 
    int count = 0; 
    printf("输入一个数令它为总人数n\n");  
    scanf("%d",&n);

    printf("输入一个数令它为初始编号m\n"); 
    scanf("%d",&m);

    printf("输入一个数令它为数到k时退出\n"); 
    scanf("%d",&k);
    index = m-1;

    for(i = 0; i < n; i++)
    {
        a[i] = i+1;
    }

    while( count < n-1 )
    {
        while(a[index] == 0)
        {
            index = (++index) % n;
        }

        if(step == k)
        {
            a[index] = 0;
            count++;
            step = 0;
        }
        
        index = (++index) % n;
        step++;
    }
    
    for(i = 0; i < n; i++)
    {
                printf("%2d ",a[i]);
    }
    
    printf("\n共退出%d人\n", count);
    
    return 0;
}

798487012 · 发表于 2018-10-27 22:30:28

claws0n 发表于 2018-10-27 22:11
哦，用经典案例测试的，输出多一个而已，改一改就好。
有问题你又不说，不明白又不问。
架构不是很好 ...

798487012 · 发表于 2018-10-27 22:32:31

claws0n 发表于 2018-10-27 22:11
哦，用经典案例测试的，输出多一个而已，改一改就好。
有问题你又不说，不明白又不问。
架构不是很好 ...

没有大佬懂得那么多

膜拜

claws0n · 发表于 2018-10-27 22:40:38

798487012 发表于 2018-10-27 22:32
没有大佬懂得那么多膜拜

啊，打错了，上面 while( count < n-1 )，改了
我们的顺序上不一样
我说架构不是很好，因为他需要 while(a[index+1]==0 && a[index]==0) 比较奇怪的判断
数据一大的话，他的会比较耗时。
由于你一开始是 step = 1，所以应该先判断 step == k，才来 step++。 while 是后来需要调整 index 的，所以后来才加到前面

798487012 · 发表于 2018-10-28 14:00:03

claws0n 发表于 2018-10-27 22:40
啊，打错了，上面 while( count < n-1 )，改了
我们的顺序上不一样
我说架构不是很好，因为他需要 whi ...

太感谢了，为我一个问题费那么多精力而且写得那么详细

账号		自动登录	找回密码
密码			立即注册