约瑟夫

 约瑟夫出圈问题 两种方法实现，数据和链表 n个人围成一个圈，一个个首尾相连的圈报数，从第一个开始报数
 报到m的人出圈，剩下的人继续从1开始报数，直到所有人都出圈为止。

import java.util.LinkedList;
import java.util.Scanner;

/**
 * 约瑟夫出圈问题 两种方法实现，数据和链表 n个人围成一个圈，一个个首尾相连的圈报数，从第一个开始报数
 * 报到m的人出圈，剩下的人继续从1开始报数，直到所有人都出圈为止。
 * 
 * @author sesame.yangj
 */
public class Joseph {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Joseph j = new Joseph();
        System.out.println("约瑟夫出圈");
        System.out.println("输入人数:");
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        System.out.println("输入出圈的位置:");
        int m = s.nextInt();
        System.out.println("数组实现");
        j.arrayJoseph(n, m);
        System.out.println("链表实现");
        j.listJoseph(n, m);
    }

    /**
     * 用数组实现
     * 
     * @param n 总的人数
     * @param m 当前报的数
     */
    public void arrayJoseph(int n, int m) {
        //数组存储编号
        int array[] = new int[n];
        int len = n;
        for (int i = 0; i < array.length; i++) {
            array[i] = i + 1;
        }

        int i = 0;
        //当前报的数
        int j = 1;

        while (len > 0) {
            if (array[i % n] > 0) {
                //位置有人
                if (j % m == 0) {
                    //报到出圈的人
                    System.out.println(array[i % n]);
                    //为之置空
                    array[i % n] = -1;
                    //从1开始报数
                    j = 1;
                    i++;
                    len--;
                } else {
                    i++;
                    j++;
                }
            } else {
                //遇到空位
                i++;
            }
        }
    }

    /**
     * 用双向链表实现
     * 
     * @param n
     * @param m
     */
    public void listJoseph(int n, int m) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < n; i++) {
            //添加数据,与编号对应
            list.add(i + 1);
        }
        int moved = 0;
        while (list.size() > 0) {
            moved = (moved + m - 1) % list.size();
            System.out.println(list.get(moved));
            list.remove(moved);
        }
    }
}

 

评论

1 楼 yangjueshe 2009-11-02  

灰常经典java题目啊