注册 登录
查看: 336|回复: 1

约瑟夫环的问题

[复制链接]
发表于 2014-5-4 09:41:30 | 显示全部楼层 |阅读模式
关于约瑟夫环的数学的问题,今天通过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()。
回复

使用道具 举报

发表于 2014-5-4 09:51:40 来自手机 | 显示全部楼层
这类面试题,一般是计算机类软件面试,主要考的是算法思想。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

快速回复 返回列表 返回顶部