Java使用队列解决约瑟夫问题

约瑟夫问题:

      传说在公园1世纪的犹太战争中,犹太约瑟夫是公元一世纪著名的历史学家。在罗马人占领乔塔帕特后,39 个犹太人与约瑟夫及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人俘虏,于是决定了一个流传千古的自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报到第3人该人就必须自杀,然后再由下一个人重新报数,直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从这个约定,约瑟夫要他的朋友先假装遵从,他将朋友与自己安排在第_个和第_个位置,于是逃过了这场死亡游戏,你知道安排在了第几个嘛?

队列实现:

package org.codewy.algorithm.josephusproblem;

import java.util.LinkedList;
import java.util.Queue;

public class JosephusProblem {
    
    public static void main(String[] args) {
        Queue<Integer> persons = new LinkedList();

        for (int i = 1; i < 42; i++) {
            persons.add(i);
        }

        int count = 0;

        while (persons.size() > 2) {
            count++;
            Integer person = persons.poll();
            if (count % 3 == 0) {
                System.out.println("die: " + person);
            } else {
                persons.add(person);
            }
        }

        System.out.println("alive: " + persons);
    }

}

输出结果:

Java使用队列解决约瑟夫问题

 

上一篇:SQL 测验


下一篇:SQL常用语法与语句