Java实现循环列表解决约瑟夫环问题

约瑟夫环:共有n个人围成一圈,从1开始报数,数到m的人出圈,求最后幸运者序号??

下面用Java实现循环列表解决这个问题:

package com.iteye.ljmdbc7a;

import java.util.Scanner;

/**
 * 循环列表的Java实现,解决约瑟夫环问题
 * @author LIU
 *
 */
public class LinkedList
{
 //定义结点,必须是static
 static class Node
 {
  int data;
  Node next;
  Node(int arg1)
  {
   this.data = arg1;
  }
 }
 public static void main(String[] args)
 {
  int n = 0,m = 0;//定义总人数n,和出圈数字m
  //输入n和m
  System.out.println("输入总人数n,出圈数字m");
  Scanner scanner = new Scanner(System.in);
  n = scanner.nextInt();
  m = scanner.nextInt();
 
  //初始化循环列表,头结点first和尾结点p
  Node first = new Node(1);
  first.next = first;
  Node p = first;
  for(int i=2; i<=n; i++)
  {
   Node temp = new Node(i);
   temp.next = p;
   p.next = temp;
   p = p.next;
  }
  p.next = first;//尾接头形成循环链表(p为尾结点)
 
  //执行出圈操作
  System.out.println("出圈顺序为:");
  while(p != p.next)
  {
   //下面for循环后,p是第m个结点的前一个结点
   for(int i=1; i<m; i++)
    p = p.next;
   //删除第m个结点
   System.out.print(p.next.data+" ");
   p.next = p.next.next;
  }
  System.out.print("\n幸运者是:"+p.data);
 }
 
}

注意42行->>>>p.next = first;//尾接头形成循环链表(p为尾结点)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/65ba7e74b0215e4a956a8e3296a94054.html