1. Introduction
The Joseph problem (sometimes called the Josephs permutation, is a problem that appears in computer science and mathematics. In computer programming algorithms, similar problems are also called the Joseph ring. Also known as the "handkerchief throwing problem".)
example:
len personally formed a circle and played the game of throwing handkerchiefs. Starting from the kth person, counting from 1. When m is counted, the person who counts m will exit the circle, until there is only one person left in the circle.
Problem analysis and algorithm design
The Joseph problem is not difficult, but there are many solutions; there are many variations in the question. Here is a method of implementation.
In the question, len individuals are surrounded by a circle, which inspires us to use a circular chain to represent it. We can use a structural array to form a circular chain. There are two members in the structure, one is the head node pointing to the first child, and the other is the node temp as a judgment (responsible for playing the supporting role).
The specific code is as follows:
package demo11;/** * Joseph's problem, turned into a handkerchief* * @author tianq idea: create a Child class, a loop list class CyclLink */public class demo11 {public static void main(String[] args) {CyclLink cyclink = new CyclLink();cyclink.setLen(15);cyclink.createLink();cyclink.setK(2);cyclink.setM(2);cyclink.show();cyclink.play();}}// Create a child class Child {// The child's identity is int no;Child nextChild;// Point to the next child public Child(int no) {// The constructor gives the child an idthis.no = no;}}class CyclLink {// Define a reference to the first child in the linked list first child // The reference to the first child cannot be moved Child firstChild = null;Child temp = null;int len = 0;// Indicate how many children there are int k = 0;// The beginning child int m = 0;// count to the number of out// Set mpublic void setM(int m) {this.m = m;}// Set the size of the linked list public void setLen(int len) {this.len = len;}// Set the number of people to count public void setK(int k) {this.k = k;}// Start playpublic void play() {Child temp = this.firstChild;// 1. Find the person who starts counting for (int i = 1; i < k; i++) {temp = temp.nextChild;}while (this.len != 1) {// 2. Count m for (int j = 1; j < m; j++) {temp = temp.nextChild;}// Find the previous child to get out of the circle Child temp2 = temp;while (temp2.nextChild != temp) {temp2 = temp2.nextChild;}// 3. Exit the child who counts to m, exit temp2.nextChild = temp.nextChild;// Let temp point to the next child who counts temp = temp.nextChild;// this.show(); this.len--;}// The last child System.out.println("Last out of the circle" + temp.no);}// Initialize the ring-link list public void createLink() {for (int i = 1; i <= len; i++) {if (i == 1) {// Create the first child Child ch = new Child(i); this.firstChild = ch;this.temp = ch;} else {if (i == len) {// Create the first child Child ch = new Child(i);temp.nextChild = ch;temp.nextChild = this.firstChild;} else {// Continue to create the child Child ch = new Child(i);temp.nextChild = ch;temp = ch;}}}}// Print the ring-linked list public void show() {Child temp = this.firstChild;do {System.out.print(temp.no + " ");temp = temp.nextChild;}while (temp != this.firstChild);}}result:
Summarize
The above is all the content of this article about the example analysis of the Joseph problem in Java programming, and I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!