服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|

服务器之家 - 编程语言 - JAVA教程 - Java采用循环链表结构求解约瑟夫问题

Java采用循环链表结构求解约瑟夫问题

2019-12-06 14:14shichen2014 JAVA教程

这篇文章主要介绍了Java采用循环链表结构求解约瑟夫问题的解决方法,是很多Java面试环节都会遇到的经典考题,这里详细给出了约瑟夫问题的原理及Java解决方法,是非常经典的应用实例,具有一定的参考借鉴价值,需要的朋友可以参考下

本文实例讲述了Java采用循环链表结构求解约瑟夫问题的方法。分享给大家供大家参考。具体分析如下:

这是第一次java考试的试题,对于没看过链表的同学来说就不会做,现在回头看看,还真不难。

约瑟夫问题:
有n个人,其编号分别为1,2,3,…,n。这n个人按顺序排成一个圈。现在给定s和d,从第s个人开始从1依次报数,数到d的人出列,然后又从下一个人开始又从1开始依次报数,数到d的人又出列,如此循环,直到最后所有人出列为止。要求定义一个节点类,采用循环链表结构求解约瑟夫问题。

以下java版的答案:

复制代码代码如下:

import java.util.Scanner;
public class LinkNode {              //单向链表的节点类
    public int data;                 //存放节点值
    public LinkNode next;            //存放节点值的引用
    
    public LinkNode(int k){         //构造方法 ,值为k的节点
        data = k;
        next= null;
    }
}
 class Josephus{
    public static void printJosephus(int n,int s,int d){        
        int i=1;                    //创建长为n的循环列表
        LinkNode q,tail;
         
        LinkNode head = new LinkNode(i);
        head.next = head ;
        tail = head;             //第一个节点,尾巴和头在一起
        
        while(i<n){
            i++;
            q = new LinkNode(i);    //增加一个新节点
            q.next = head ;        //节点的引用指向头
            tail.next = q;            //最后一个元素的引用指向了q
            tail = q;              //那么最后一个元素就是q
        }

 

        int j= 0;               //从s开始报数,依次输出出列人的编号
        LinkNode p = head;      //计数起点
        while(j<s-1){
            j++;
            p = p.next;
        }
        while(p.next != p){
            j = 1;
            while(j<d-1)   //计数的起始点
            {
                j++;
                p = p.next;
            }        
            System.out.print(p.next.data + " ");  // 输出出列的节点号
            p.next = p.next.next;
            p = p.next;                                //不断指向下一个节点            
        }
        System.out.print(p.data);
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int a = input.nextInt();
        int b = input.nextInt();
        Josephus.printJosephus(n, a, b);
    }
}

 

希望本文所述对大家的Java程序设计有所帮助。

延伸 · 阅读

精彩推荐