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이 되어야 합니다.
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>위 내용은 자바에서 조셉 문제를 해결하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
