Java-Implementierung des klassischen Problems Josephs Problem

Ich habe in letzter Zeit mehr Zeit und habe Zeit, an Java zu arbeiten. Ich persönlich habe das Gefühl, dass es in dieser Sprache zu viele Syntaxen gibt, deshalb möchte ich sie nicht aus einer Laune heraus lernen. Ich habe den Quellcode von struct2 hochgeladen und es fühlt sich an wie in der Tiefsee. Es macht mich schwindelig. Beginnen wir mit dem einfachsten.

Das Joseph-Problem ist auch als Problem des verlorenen Taschentuchs bekannt. Die Verwendung von C++ oder Javas unidirektionaler zirkulärer verknüpfter Liste kann eine bessere Lösung bieten, ist aber sicherlich nicht die einfachste Methode. Es ist nur eine kleine Hausaufgabe beim Erlernen von Java.

Die Ursache des Problems ist, dass der berühmte jüdische Historiker Josephus die folgende Geschichte hat: Nachdem die Römer Chotapat besetzt hatten, versteckten sich 39 Juden mit Josephus und seinen Freunden in einer Höhle vom Feind gefangen werden, also entschieden sie sich für einen Weg, Selbstmord zu begehen. 41 Menschen stellten sich in einem Kreis auf, gezählt von der ersten Person, und jedes Mal, wenn die dritte Person gezählt wurde, musste die Person Selbstmord begehen, und dann die nächste Person Zählen Sie erneut, bis alle Selbstmord begehen. Josephus und seine Freunde wollten jedoch nicht nachkommen. Beginnen Sie zunächst mit einer Person, kreuzen Sie k-2 Personen (da die erste Person gekreuzt wurde) und töten Sie die kte Person. Gehen Sie dann an k-1 Personen vorbei und töten Sie die kte Person. Dieser Prozess setzt sich im Kreis fort, bis schließlich nur noch eine Person übrig bleibt und diese Person weiterleben kann. Die Frage ist: Wo stehen Sie überhaupt, um einer Hinrichtung zu entgehen? Josephus bat seinen Freund, zuerst so zu tun, als würde er gehorchen. Er platzierte seinen Freund und sich selbst auf der 16. und 31. Position und entging so dem Todesspiel.

Spezifische Anforderungen finden Sie unter Du Niang: Joseph's Question

public class Demo4 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CycLink cyclink = new CycLink();
		int len=41;
		int k=1;
		int m=3;
		cyclink.setLen(len);
		cyclink.creatLink();
		cyclink.show();
		cyclink.setK(k);
		cyclink.setM(m);
		cyclink.playgame();
	}

}
class Node
{
	int no;
	Node nextNode = null;
	//节点的构造函数
	public Node(int no)
	{
		//给一个编号
		this.no = no;
	}
}
//环形链表
class CycLink
{
	//先定义一个指向链表第一个节点的引用
	//指向第一个节点的引用不能动
	Node firstNode = null;//没有新开辟空间，它在纸上谈兵！！！！
	Node tempNode =null;//跑龙套的选手！！！很重要！！！！（纸上谈兵）
	int len = 0;//表示共有多少个节点(Node)
	int k =0;//表示要从第k个节点开始计数
	int m =0;//表示每数到m个节点要被删除
	//设置链表的大小（长度）
	public void setLen(int len)
	{
		this.len = len;
	}
	
	//设置从第k个人开始计数
	public void setK(int k)
	{
		this.k=k;
	}
	
	//设置从第m个人开始计数
		public void setM(int m)
		{
			this.m=m;
		}
	//初始化环形链表
	public void creatLink()
	{
		for(int i=1;i<= len ;i++)
		{
			if(i==1)
			{
				//创建第一个节点
				Node ch=new Node(i);//ch可不是纸上谈兵，实实在在的开辟了空间
				this.firstNode = ch;//“纸上”的firstNode指向了有实际空间的ch
				this.tempNode = ch;//“纸上”的tempNode指向了有实际空间的ch
			}
			else //其余节点（不是第一个头结点）
			{
				if(i==len)//（如果要创建最后一个节点）
				{
					//创建最后一个节点
					Node ch=new Node(i);//创建（实际开辟）最后节点，以第二个为例
					tempNode.nextNode = ch;//"纸上"的tempNode.nextNode指向2节点
					tempNode = ch;//在“纸上”变更龙套选手
					tempNode.nextNode = this.firstNode;//纯粹纸上谈兵，龙套（最后节点）的下个节点指回初始节点
				}
				else
				{
					//继续创建一个节点
					Node ch=new Node(i);//创建（实际开辟）下一个节点，以第二个为例
					tempNode.nextNode = ch;//"纸上"的tempNode.nextNode指向2节点
					tempNode = ch;//在“纸上”变更龙套选手
				}
			}
		}
	}
	//开始丢手帕游戏
	public void playgame()
	{
		//1、找到第k个节点
		Node temp1=null;
		Node temp2=null;
		temp1 = firstNode;
		
		for(int i=1; i<k; i++)
		{
			temp1=temp1.nextNode;
		}
		int cn=1;//删除的顺序标志
		while(len!=1)
		{
		//2、从第1步中找到的k人开始计数，找第m-1个用户（方便第3步修改其下个节点的指向）
			for(int j=1; j<m-1; j++)
			{
				temp1=temp1.nextNode;
			}
		//3、将第2步中找到的用户修改其下个节点的指向
			temp2=temp1.nextNode;//temp2就是要被删去的节点
			System.out.println("第"+cn+"个删除的节点编号："+ temp2.no);
			temp1.nextNode=temp2.nextNode;
			temp1 = temp1.nextNode;
			cn++;
			len--;
		}
		//4、显示最后剩下的节点
		System.out.println("最后剩下的节点是："+temp1.no);
	}
	//打印该循环链表
	public void show()
	{
		//定义个龙套选手
		Node temp=this.firstNode;//将“龙套”选手的“帽子”扣在第一个节点上
		System.out.print("初始节点编号： ");
		do {
			System.out.print(temp.no+" ");
			temp = temp.nextNode;
		}while(temp!=this.firstNode);
		System.out.println(" ");
	}
}

Verwandte Empfehlungen:

PHP-Java-Bridge-Nutzungshinweise, php-java-bridge

Java-Lernaufsatz---Trick-Vektor, Java-Aufsatz---Vektor

Das obige ist der detaillierte Inhalt vonJava-Implementierung des klassischen Problems Josephs Problem. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!