1. Introduction
Le problème de Joseph (parfois appelé la permutation de Josephs, est un problème qui apparaît en informatique et en mathématiques. Dans les algorithmes de programmation informatique, des problèmes similaires sont également appelés anneaux Joseph. Aussi connu sous le nom de "Problème de lancer de mouchoir".)
exemple:
Len a personnellement formé un cercle et a joué le jeu de mouchoirs à lancer. À partir de la Kth Person, en comptant à partir de 1. Lorsque M est compté, la personne qui compte M quittera le cercle, jusqu'à ce qu'il ne reste qu'une seule personne dans le cercle.
Analyse des problèmes et conception d'algorithmes
Le problème de Joseph n'est pas difficile, mais il existe de nombreuses solutions; Il existe de nombreuses variations dans la question. Voici une méthode de mise en œuvre.
Dans la question, les individus Len sont entourés d'un cercle, ce qui nous inspire à utiliser une chaîne circulaire pour la représenter. Nous pouvons utiliser un réseau structurel pour former une chaîne circulaire. Il y a deux membres dans la structure, l'un est le nœud de tête pointant vers le premier enfant, et l'autre est la température du nœud comme un jugement (responsable du jeu de soutien).
Le code spécifique est le suivant:
Package Demo11; / ** * Le problème de Joseph, transformé en un mouchoir * * @author ide CyclLink (); cyclink.setlen (15); cyclink.createLink (); cyclink.setk (2); cyclink.setm (2); cyclink.show (); cyclink.play ();}} // créer un enfant de classe d'enfant {// L'identité de l'enfant est int non; idThis.no = no;}} classe cycllink {// définir une référence au premier enfant dans la liste liée premier enfant // La référence au premier enfant ne peut pas être déplacée d'enfant firstchild = null; enfant temp = null; int len = 0; // indique le nombre d'enfants. {this.m = m;} // définir la taille de la liste liée publique void setlen (int len) {this.len = len;} // définir le nombre de personnes pour compter le public vide setk (int k) {this.k = k;} // start playpublic vide play () {enfant temp = this.firstchild; // 1. i ++) {temp = temp.nextchild;} while (this.len! = 1) {// 2. Count m for (int j = 1; j <m; j ++) {temp = temp.nextchild;} // trouve l'enfant précédent pour sortir de l'enfant de cercle temp2 = temp à m, sortir temp2.NextChild = temp.NextChild; // Laissez Temp pointer vers l'enfant suivant qui compte 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) {// Créer le premier enfant ch = nouveau enfant (i); this.firstChild = ch; this.temp = ch;} else {if (i == len) {// créer le premier enfant chan = new child (i); temp.nextchild = ch; temp.nextchild = this.firstchild;} else {// continue de créer l'enfant ch /}} Liste liée à l'anneau public void show () {enfant temp = this.firstchild; do {system.out.print (temp.no + ""); temp = temp.nextchild;} while (temp! = this.firstchild);}}résultat:
Résumer
Ce qui précède est tout le contenu de cet article sur l'exemple d'analyse du problème Joseph dans la programmation Java, et j'espère que cela sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!