囧瑟夫问题

无聊水河畔，看了看今年大华为上机题，比较高大上(shui)，无监考，能讨论，还特么能百度谷歌。。。这才是写代码应该有的模式呀。。。最近正好在看J2EE，就随手写了个约瑟夫问题，顺便试试语法高亮插件>_<

```c++ /* * 约瑟夫问题:设编号为1，2，。。。n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列， * 他的下一位又从1开始报数，数到m的人又出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列。求最 * 后剩下人的编号。 * * 很容易想到循环链表，我这里用的双向循环链表解法。 / package com.yosephu; public class Yosephu { public static void main(String[] args) { //测试用例 Link link = new Link(); link.setLen(10); link.setK(1); link.setM(10); link.init(); link.show(); link.play(); }

} //节点类 class Node { int num; Node pre; Node next;

public Node(int num)
{
    this.num = num;
}

} //链表类 class Link { Node h = null; Node temp = null; //链表大小 int len = 0; public void setLen(int len) { this.len = len; } int k = 0; int m = 0; public void setK(int k) { this.k = k; } public void setM(int m) { this.m = m; } //初始化链表 public void init() { for(int i=1;i<=len;i++) { Node node = new Node(i); if(i == 1) { h = node; temp = node; } else { if(i == len) { node.pre = temp; temp.next = node; node.next = h; h.pre = node; } else { node.pre = temp; temp.next = node; temp = node; } } } } public void play() { Node temp = this.h; //1。先找到开始数数的第k个人 for(int i=1;i<k;i++) { temp = temp.next; } while(this.len !=1) { //2。数m下 for(int j=1;j<m;j++) { temp = temp.next; }

        //打出出列人的编号
        System.out.println("出列人的编号:"+temp.num);

        //3。将数到m的人，踢出链表
        temp.pre.next = temp.next;
        temp.next.pre = temp.pre;
        temp = temp.next;
        this.len--;
    }
    System.out.println("最后一个是:"+temp.num);
}

public void show()
{
    Node t = this.h;
    do
    {
        System.out.println(t.num);
        t = t.next;
    }
    while(t != this.h);
}

} ```