单向环形链表解决约瑟夫问题

约瑟夫问题(有时也称为约瑟夫斯置换,是一个计算机科学数学中的问题。在计算机编程算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”.)

代码实现:

class OneWayAnnularChainTableMain {
    public static void main(String[] args) {
        OneWayAnnularChainTable oneWayAnnularChainTable = new OneWayAnnularChainTable();
        oneWayAnnularChainTable.add(5);
        oneWayAnnularChainTable.show();
        oneWayAnnularChainTable.outstanding(1,2,5);

    }
}

public class OneWayAnnularChainTable {
    private NumberNode first = null;

    public void add(Integer num) {
        if (num < 1) {
            System.out.println("数值不可小于1");
        }
        NumberNode curNode = null;
        for (int i = 1; i <=num; i++) {
            NumberNode numberNode = new NumberNode(i);
            if (i == 1) {
                first = numberNode;
                first.next = first;
                curNode = first;
            } else {
                curNode.next = numberNode;
                numberNode.next = first;
                curNode = numberNode;
            }
        }
    }

    public void show() {
        if (first == null) {
            System.out.println("链表为空");
        }
        NumberNode numberNode = first;
        while (true) {
            System.out.println(numberNode.toString());
            if(numberNode.next==first){
                break;
            }
            numberNode=numberNode.next;
        }
    }

    public void outstanding(Integer startNo, Integer count, Integer size) {
        if (first == null || startNo < 1 || count > size) {
            System.out.println("参数错误");
            return;
        }
        NumberNode helper = first;
        while (true) {
            if (helper.next == first) {
                break;
            }
            helper = helper.next;
        }
        for (int i = 0; i < startNo - 1; i++) {
            first = first.next;
            helper = helper.next;
        }
        while (true) {
            if (helper == first) {
                break;
            }
            for (int i = 0; i < count - 1; i++) {
                first = first.next;
                helper = helper.next;
            }
            System.out.println(first.id);
            first = first.next;
            helper.next = first;
        }
        System.out.println(helper.id);
    }


}

class NumberNode {
    public Integer id;
    public NumberNode next;

    public NumberNode(Integer id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "NumberNode{" +
                "id=" + id +
                '}';
    }
}

单向环形链表解决约瑟夫问题

 

上一篇:算法:验证二叉搜索树


下一篇:异步、定时、邮件任务