网站首页 文章专栏 约瑟夫环算法
约瑟夫环算法

约瑟夫环算法


 前言 :面试新华三时,有个题目就是约瑟夫环,因为有点紧张写的不是很好,记录下应当怎么写,网上流传很多种写法,使用数组实现的,使用集合实现的都有。这里介绍两种的实现方式。



约瑟夫环:这个算法什么意思呢,有很多种说法,大体的意思就是,一群人围城一圈,每个人自带一个编号(比如1,2,3,4,5,6...),从第一个开始报数,报数报到m的人死掉,下一个人重新从1开始报数,再次报到m的人死掉,问最后一个存活的人的原始位置。


1,第一种实现方式,使用java自带的LinkedList实现,因为其是用链表实现的,可以直接remove掉,需要注意的是移除后索引会减少。

/**
 * 输入总人数,循环次数,返回原始对应的下标,注意返回的是下标,不是第几个,应当是第下标+1个人
 * @param totalPeople
 * @param loopNum
 * @return
 */
public static Integer test2(Integer totalPeople,Integer loopNum){
    LinkedList<Integer> people = new LinkedList<>();
    for (int i = 0; i < totalPeople;i++){
        people.add(i);        // 每个元素的值就是原始下标
    }

    int index = 0;
    while(people.size() > 1){
        for(int i = 1;i < loopNum;i++){        // 注意这里,循环次数
            if(index == people.size() - 1){
                index = 0;                // 循环到底后,从头再来
            }else {
                index++;
            }
        }
        people.remove(index);
    }

    return people.get(0);        // 移除完后只剩一个元素了,他的值就是原始的下标值
}


2,第二种实现方式是用数组实现,也很直观。

/**
 * 输入总人数,循环次数,返回原始对应的下标
 * @param totalPeople
 * @param loopNum
 * @return
 */
public static Integer test(Integer totalPeople,Integer loopNum){
    Boolean[] people = new Boolean[totalPeople];    // 定义一个布尔数组,长度为总人数
    for(int i = 0; i < totalPeople;i++){
        people[i] = true;                        // 使其每个元素都为true
    }

    int count = 0;            // 定义计数器
    int index = 0;                    // 定义数组索引
    int aliveNum = totalPeople;        // 定义剩余存活人数
    while (aliveNum > 1){            // 如果剩余人数多于1个就继续循环杀人
        if(people[index]){            // 如果这个位置的人是活的再去杀人
            count ++;                //计数器自增
            if(count == loopNum){        // 如果数到循环次数了
                count = 0;                // 计数器置零
                people[index] = false;       // 杀掉该人
                aliveNum --;                    // 存活人数减一
            }
        }
        index ++;                            // 无论杀不杀人,都要自增
        if(index == totalPeople){            // 如果到数组结尾了,就从头开始
            index = 0;
        }
    }

    for(int i = 0;i < totalPeople;i++){
        if(people[i]){
            return i;        // 循环这个数组,里面只有一个为true的,返回他的索引
        }
    }
    return null;
}


暂时就写这两种方式,还有其他方式实现,都是大同小异,如有其他方式实现可以给我留言。






版权声明:本文由星尘阁原创出品,转载请注明出处!

本文链接:http://www.52xingchen.cn/detail/43




赞助本站,网站的发展离不开你们的支持!
来说两句吧
最新评论