当前位置:首页 > 开发 > 编程语言 > Java > 正文

单循环链表与约瑟夫问题模拟(java)

发表于: 2012-07-31   作者:128kj   来源:转载   浏览:
摘要: 北大《百练》上的题目 http://poj.grids.cn/practice/2746/,用单循环链表模拟了一下。 时间限制: 1000ms 内存限制: 65536kB 描述 约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输
北大《百练》上的题目 http://poj.grids.cn/practice/2746/,用单循环链表模拟了一下。

时间限制: 1000ms 内存限制: 65536kB
描述
约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。

输入
每行是用空格分开的两个整数,第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是:

0 0

输出
对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号

样例输入
6 2
12 4
8 3
0 0

样例输出
5
1
7

下面是AC代码:
import java.util.Scanner;

public class Main< T> {
    private int size = 0;
    private Node< T> head, tail,current;
  
    public Main() {
        head = tail =null;
        current=tail;
       
    }
    public void add(T data) {
        if (size == 0) {
            head = new Node< T>(data, null);
            head.next=head;
            tail=head;
            current=tail;
           
        } else {
            tail.next = new Node< T>(data, head);
            tail = tail.next;
            current=tail;
        }
        size++;
    }

   
    public T moveANDremove(boolean flag){
         T data=current.next.getData();
          if(flag) {
              if(current.next==head){
                   head=current.next.next;
               }else if(current.next==tail){
                  tail=current;
               }
              current.next=current.next.next;
            
              size--;
             return data;
            }else{
              current=current.next;
              return data;
           }
     
         
       }
        
      
    public int size(){
        return size;
    }

   public String toString(){
        if (size < 1) {
            return "没有元素";
        } else {
            Node< T> tmp = head;
            StringBuffer sb=new StringBuffer();
            do{
               sb.append(tmp.getData()+"  ");
                tmp = tmp.next;
            }while (tmp!=head);
           return sb.toString();
        }
     }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
       
        while(true){
            int k=1;
            int n=in.nextInt();
            int m=in.nextInt();
            if(n==0&m==0) break;
             Main< Integer> l = new Main< Integer>();
             for(int i=1;i<=n;i++)
               l.add(i);
        
        
        while(true){
                   
           if(k%m!=0) {
             l.moveANDremove(false);
             k++;
           }
           else{
             l.moveANDremove(true);
             k=1;
           }
                  
          if(l.size()==1) {
            System.out.println(l.current.getData());
           // System.out.println(l);
            break;
          }
         }
        }
       }
        
}

class Node< T> {
    T data;
    Node< T> next;
    public Node(T data, Node< T> next) {
        this.data = data;
        this.next = next;
    }
   public T getData(){
       return data;
    }
    public void setData(T data){
        this.data=data;
    }
 }


源码下载

单循环链表与约瑟夫问题模拟(java)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

推荐文章
编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号