자바에서 조셉 문제를 해결하는 방법

1. 요셉의 문제 소개

1. 요셉의 문제 원래 제목:

n 아이들이 원을 그리며 손을 잡고 있고, k(1

2. 문제 분석:

문제 설명에 따르면 단방향 순환 연결 목록을 사용하여 시뮬레이션하는 것을 생각하면 쉽습니다. 먼저 n개의 노드로 단방향 순환 연결 리스트를 구성한 후 노드 K를 1부터 계산합니다. m이 계산되면 해당 노드가 연결 리스트에서 삭제되고 다음 삭제된 노드부터 1부터 계산이 시작됩니다. 노드가 삭제됩니다.

단방향 순환 연결 목록

1번 사람부터 시작하여 번호가 보고될 때마다 2번 사람이 대기열에서 나온다고 가정합니다. $n=5$명이면 $n=5$입니다. k=1,m=2$ . 그러면 최종 결과는 2, 4, 1, 5, 3이 되어야 합니다.

2. 단방향 순환 연결 리스트 구축

1. 구축 아이디어:

• 먼저 첫 번째 노드를 생성하고 첫 번째 포인터로 노드를 가리키고 다음 노드는 자신을 가리킵니다. 아래와 같습니다:

첫 번째 노드

• 그런 다음 두 번째 노드를 만들고, 첫 번째 노드의 다음 포인터를 두 번째 노드로 가리키고, 두 번째 노드의 다음 포인터를 첫 번째 노드로 가리킵니다. , 아래 그림과 같이

두 번째 노드

등으로 단방향 순환 연결 목록을 구축할 수 있습니다. 순회할 때 다음 노드가 첫 번째와 같을 때 순회가 완료되었음을 의미합니다.

2. 코드 구현:

위의 분석을 바탕으로 다음 코드를 작성할 수 있습니다. ​

3. 자식 대기열 제거 구현

1. 아이디어:

먼저 계산을 시작하는 노드를 찾고, 이를 기록하기 위해 cur를 사용합니다. 예를 들어, k번째 노드에서 시작하면 cur는 k번째 노드를 가리켜야 합니다. 그런 다음 cur의 이전 노드를 찾아 pre로 기록합니다. 이 두 노드를 찾은 후 cur에서 (m-1)번, 즉 cur와 pre move(m-1)번을 동시에 계산하기 시작합니다. 이번에는 cur가 삭제하려는 노드를 가리킵니다. 삭제할 노드를 인쇄한 후 삭제된 노드 다음 노드인

로 이동합니다. cur = cur.next，pre的next指向新的cur，即pre.next = cur

2. 코드 구현:

<code>package com.zhu.study.linkedList;<br><br>/**<br> * 约瑟夫问题，即单向循环链表问题<br> * @author: zhu<br> * @date: 2020/8/30 17:57<br> */<br>public class Josepfu {<br>    public static void main(String[] args){<br>        CircleSingleLinkedlist linkedlist = new CircleSingleLinkedlist();<br>        linkedlist.add(5);<br>        linkedlist.showNodes();<br>    }<br>}<br><br>/**<br> * 单向循环链表<br> */<br>class CircleSingleLinkedlist{<br>    private Node first = null;<br>    /**<br>     * 添加节点<br>     * @param num 需要添加的节点个数<br>     */<br>    public void add(int num){<br>        if (num             throw new RuntimeException("非法参数");<br>        }<br>        Node cur = null; // 当前node<br>        for (int i = 1; i             Node node = new Node(i);<br>            if (i == 1) {<br>                first = node;<br>                first.setNext(first); // next指向自己，构成环<br>                cur = first;<br>            } else {<br>                cur.setNext(node);<br>                node.setNext(first);<br>                cur = node;<br>            }<br>        }<br>    }<br><br>    /**<br>     * 遍历<br>     */<br>    public void showNodes(){<br>        if (first == null){ // 链表为空<br>            return;<br>        }<br>        Node cur = first;<br>        while (true){<br>            System.out.printf("小孩编号%d \n", cur.getNo());<br>            if (cur.getNext() == first){ // 遍历完毕<br>                break;<br>            } else {<br>                cur = cur.getNext();<br>            }<br>        }<br>    }   <br>}<br><br>/**<br> * 节点内部类<br> */<br>class Node{<br>    private int no; // 编号<br>    private Node next; // 下一个节点<br><br>    public Node(int no){<br>        this.no = no;<br>    }<br><br>    public int getNo() {<br>        return no;<br>    }<br><br>    public void setNo(int no) {<br>        this.no = no;<br>    }<br><br>    public Node getNext() {<br>        return next;<br>    }<br><br>    public void setNext(Node next) {<br>        this.next = next;<br>    }<br>}<br></code>

입력 매개변수가 k=1, m=2, n=5일 때 이 메서드를 실행한 결과는 위의 분석과 동일하며 출력 시퀀스는 2, 4,1,5,3.

위 내용은 자바에서 조셉 문제를 해결하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!