집 > 기사 > Java > 고전적인 문제의 Java 구현 Joseph의 문제

고전적인 문제의 Java 구현 Joseph의 문제

坏嘻嘻원래의: 2018-09-14 15:17:511686검색

최근에는 Java 작업에 시간이 더 생겼습니다. 개인적으로 이 언어는 배워야 할 구문이 너무 많다고 생각해서 기분 좋게 끊었습니다. struct2의 소스 코드입니다. 일단 들어가 보면 바다처럼 깊습니다. 가장 간단한 것부터 시작하겠습니다.

요셉 문제는 잃어버린 손수건 문제로도 알려져 있습니다. C++ 또는 Java의 단방향 순환 연결 목록을 사용하는 것이 더 나은 솔루션일 수 있지만 확실히 가장 간단한 방법은 아닙니다. Java를 배우는 과정에서 작은 숙제일 뿐입니다.

질문의 출처는 유명한 유대 역사가 요세푸스가 다음과 같은 이야기를 했다고 합니다. 로마인들이 호타팟을 점령한 후, 39명의 유대인들이 요세푸스와 그의 친구들과 함께 동굴에 숨었고, 39명의 유대인들은 차라리 죽기를 결심했습니다. 적에게 잡히기 싫어서 41명이 원형으로 줄을 섰고, 세 번째 사람이 셀 때마다 그 사람이 자살을 해야 했다. 다음 사람이 다시 숫자를 세었다. 모두가 자살할 때까지 말이다. 그러나 요세푸스와 그의 친구들은 이를 따르기를 원하지 않았습니다. 먼저 한 사람부터 시작해 k-2명을 건너고(첫 번째 사람이 넘어갔기 때문에), k번째 사람을 죽인다. 그런 다음 k-1명을 지나서 k번째 사람을 죽이세요. 이 과정은 마침내 한 사람만 남을 때까지 원을 따라 계속되며, 이 사람은 계속 살 수 있습니다. 문제는 처형당하지 않으려면 애초에 어디에 서느냐는 것이다. 요세푸스는 친구에게 먼저 순종하는 척 해달라고 부탁했고, 자신과 친구를 16위와 31위에 올려 데스게임에서 벗어났습니다.

구체적인 요구 사항은 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(" ");
	}
}

고전적인 문제의 Java 구현 Joseph의 문제

관련 기사