Java implementation of the classic problem Joseph's problem

I have more time recently and I have time to work on Java. I personally feel that there are too many syntaxes to learn in this language, so I don’t want to learn them one by one. On a whim, I hung up the source code of struct2, and it was as deep as the sea. It makes me dizzy, let’s start with the simplest one.

The Joseph problem is also known as the lost handkerchief problem. Using C or Java's One-way circular linked list can be a better solution, but it is certainly not the simplest method. It's just a small homework question in the process of learning Java.

The source of the problem is that the famous Jewish historian Josephus has the following story: After the Romans occupied Chotapat, 39 Jews hid in a cave with Josephus and his friends. The Jews decided that they would rather die than be caught by the enemy, so they decided on a way to commit suicide. 41 people lined up in a circle, counting from the first person, and every time the third person was counted, the person must commit suicide, and then the next person counted. Count again until everyone commits suicide. However, Josephus and his friends did not want to comply. First start with one person, cross k-2 people (because the first person has been crossed), and kill the kth person. Then, go past k-1 people and kill the kth person. This process continues along the circle until finally only one person remains, and this person can continue to live. The question is, where do you stand in the first place to avoid being executed? Josephus asked his friend to pretend to obey first. He placed his friend and himself in the 16th and 31st positions, thus escaping the death game.

For specific requirements, please refer to 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(" ");
	}
}

Related recommendations:

PHP-Java-Bridge usage notes, php-java-bridge

java learning essay---trick vector, java essay---vector

The above is the detailed content of Java implementation of the classic problem Joseph's problem. For more information, please follow other related articles on the PHP Chinese website!