约瑟夫环的问题

传说男号

关于约瑟夫环的数学的问题，今天通过C语言来解决这个问题，这个问题也是笔试的时候经常遇到的一个问题。我们不仅仅要把这个问题解决出来，我们要学习下里面解决问题的思路。学到一个新的技巧就是用数据来进行思考。

　　约瑟夫环就是个一群人（6个人）围着一个圈，从1开始报起，假如报的3那个人就出来。那么先是3号位出来，4号位再从1开始报起，6号位就出来。这样一直循环下去，到最后一个人出来。
　　
　　那么我们是不是要先要用一个数组来容纳这一群人。所以我们先搞一个数组，unsigned char arry[6];上面说了是6个人，要是假如是100个人呢，1000个人呢。是不是到时候改是很麻烦的一件事情，那么我们能不能#define一下，所以 #define ALL 6，以后我们就可以直接在这里改数字，不要一改要动全身。那么是不是我们要把这个数组容纳的一群人加上标志位。那么我们要用一个小的函数来初始化下里面成员。劲量一个功能要写成一个函数。
　　
　　那么我们先去一个函数的名字，叫creat_list();为什么要取一个名字是创建链表的意思了，等下再说。实现的代码如下：
　　
int creat_list()
{
        int i=0;
        for (i=0; i< ALL; i++) {   
                arry[i]=i+1; // 1,2,3,4,5,6
        }
        return 0;
}

创建好了之后，我们必然要把里面的成员打印出来，再调试的代码的时候是很有帮助的。实现的代码如下：

int print_note()
{
        int i=0;
        for (i=0; i < ALL; i++) {
                printf("%d ",arry[i]);
        }
        printf("\n\r");
        return 0;
}

我们是不是要想下如果报到3的时候，那个人就出来了，那么这个时候数组的人员是不是要相应的减少，那么我们是不是要用个变量来标志这个圈里面还剩余了多少人，那么我们定义一个变量。int left=0;那么我们是不是刚开始的时候是不是圈子里面有ALL个人，所以left=ALL；那么我们再想下left要在什么时候left要减少，是不是当数组里面的成员报的数字等于3的时候减少。那么这个报的数字是不是每个人报的不一样的，用一个变量来代表，就是int count=0;
那么代码是不是:
if (count == num) {
　　left--;
　　count=0; //又要从头报起
　　arry[i]=0;//那么是不是那个出来的人的那个位置要用个数字来标志，那么就用0来标志
}

那么count的增加，那么当数组是0的时候不增加，那么实现的代码就是
if (arry[i] != 0) {
        count++;
}

而当成员就剩只有一个的时候不再循环下去，那么实习的代码的是：
if (left < 1) {
        break;
}

i的变量是要一直增加，但是到ALL的时候，再从0开始。实习的代码：
i++;
if (i == ALL) {
        i=0;
}


整个代码如下：
#include <stdio.h>

#define ALL 100

unsigned char arry[ALL];
int creat_list()
{
        int i=0;
        for (i=0; i< ALL; i++) {
                arry[i]=i+1;
        }
        return 0;
}

int print_note()
{
        int i=0;
        for (i=0; i < ALL; i++) {
                printf("%d ",arry[i]);
        }
        printf("\n\r");
        return 0;
}

int main(int argc ,char *argv[])
{
        int left=0,count=0,num=3;
        int i=0;

        left=ALL;
        creat_list();
        while (1)
        {
                if (arry[i] != 0) {
                        count++;
                }
               
                if (count == num) {
                        count=0;
                        arry[i]=0;
                        left--;
                        print_note();
                }
                if (left < 1) {
                        break;
                }
                i++;
                if (i == ALL) {
                        i=0;
                }
        }
        print_note();
        return 0;
}


如果这个代码在笔试题中做出这样的答案，那么你说可以吗？其实在这个里面是很费时间的，因为i在这个里面做了很多无用的工。那么怎么来增加效率呢。那么要用链式的思想，也就是为什么刚刚创建的时候要用creat_list（）。

传说男号

本来想创建QQ群的，但是有点问题，等创建好之后告诉大家，现在也可以加我的QQ：360361550.一起讨论问题

山外メ雲ジ

这类面试题，一般是计算机类软件面试，主要考的是算法思想。