ホームページ > 記事 > Java > 古典的な問題の Java 実装ジョセフの問題

古典的な問題の Java 実装ジョセフの問題

坏嘻嘻オリジナル: 2018-09-14 15:17:511686ブラウズ

最近は時間ができて、Java に取り組む時間ができました。個人的には、この言語を学ぶには構文が多すぎると感じているので、気まぐれに 1 つずつ学習したくありません。 struct2 のソースコードを表示すると、海のように深かったのでめまいがします。最も単純なコードから始めましょう。

ジョセフ問題は、紛失したハンカチ問題としても知られています。 C または Java の 一方向循環リンクリスト を使用することは、より良い解決策になる可能性がありますが、これは確かに最も単純な方法ではありません。これは、Java を学習する過程での小さな宿題の質問にすぎません。

問題の原因は、有名なユダヤ人歴史家ヨセフスの次のような物語です。ローマ人がチョタパットを占領した後、39 人のユダヤ人がヨセフスとその友人たちとともに洞窟に隠れました。敵に捕まってしまうため、41人が円形に並び、最初の人から数えて3人目になるごとにその人が自殺し、次の人が自殺するという方法をとった。全員が自殺するまでもう一度数えます。しかし、ヨセフスと彼の友人たちは従いたくありませんでした。まず 1 人から始めて、k-2 人を横切り (最初の人が横切られているため)、k 人目を殺します。次に、k-1 人を通り過ぎて、k 人目を殺します。このプロセスは円に沿って続き、最終的に 1 人だけが残り、その人が生き続けることができます。問題は、処刑を避けるためには、そもそもどこに立っているのかということだ。ヨセフスは友人にまず従うふりをするよう頼み、友人と自分を16位と31位に配置し、デスゲームから逃れた。

特定の要件については、Du Niang: Joseph の質問を参照してください。

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(" ");
	}
}

古典的な問題の Java 実装 ジョセフの問題

関連記事

古典的な問題の Java 実装ジョセフの問題