어떻게 자바 재 귀 를 이용 하여'9 연쇄'공식 을 해결 합 니까?

이전에 재 귀 에 관 한 것 을 조금 쓴 적 이 있다클릭 하여 링크 열기그리고 어 렸 을 때 자신 이 놀 았 던 장난감 인 9 연쇄 를 생각 했다.어 렸 을 때 자신 이 놀 면서 필기 로 이 물건 의 공식 을 풀 었 던 것 은 십 여 년 전의 일이 다.이틀 전에 갑자기 9 연쇄 의 기본 적 인 조작 은 바로 재 귀 이 고 매우 표준적 인 재 귀 과정 이라는 것 이 생각 났 다.
9 연쇄 게임 의 규칙 은 한 마디 로 요약 하면 어떤 고 리 를 지우 거나 어떤 고 리 를 채 우려 면 이 고리 의 앞 고 리 를 보존 하고 그 전의 모든 고 리 를 지 워 야 한 다 는 것 이다.예 를 들 어 9 번 고 리 를 지우 거나 장 착 하려 면 8 번 고 리 를 보관 하고 8 번 고 리 를 모두 지 울 수 있 습 니 다)그 중 1 번 고 리 는 직접 지 울 수 있 습 니 다.(사실 첫 번 째,두 번 째,이 두 고 리 는 함께 장 착하 고 같이 지 울 수 있 습 니 다.우 리 는 논리 적 으로 첫 번 째 고 리 는 자 유 롭 게 이동 할 수 있 도록 규정 할 뿐 입 니 다)
그러면 재 귀적 인 사상 에 따라 이 문 제 를 실현 하 는 것 은 비교적 간단 하 다.앞서 언급 한 것 과 달리 이번 에는 특정한 고리 에 대한 조작 이 하나 가 아니 라 설치 와 제거 두 가지 기본 적 인 조작 과 관련 되 기 때문에 9 연쇄 에 대해 하나의 표시 상 태 를 설정 해 야 한다.state:9 연쇄 는 위 에 있 고 state=1.9 연 대 는 아래 에 있 습 니 다.state=0.이것 은 Node 클래스 에서 이 루어 집 니 다.c++의 struct 와 같다)

그 중에서 num 속성 은 링 번 호 를 나타 내 고 state 는 링 의 상 태 를 나타 낸다.
두 번 째 로 준비 해 야 할 것 은 Array List 로 이 루어 진 스 택 을 이용 하여 모든 state=1 의 링 을 스 택 에 누 르 는 것 입 니 다.9 연쇄 규칙 에서 요구:특정한 고 리 를 조작 하려 면 이 고리 의 앞 고리 state=1 을 확보 하고 창고 꼭대기 에 있어 야 합 니 다.
세 번 째 는 조작 과정 move 입 니 다.state 에 따라 move 동작 을 설정 합 니 다.

준비 조건 이 다 되 었 으 니,바로 설계 재 귀 를 실현 해 야 한다.먼저 디자인 의 사상(위조 코드)을 써 보 세 요.

play(n){
	n=1://    
		move(n);
	n>1:
		while(!deal)//           
		{
			(n-1).state=1://     
				stack.pop=n-1://      
					move(n);
					deal=true;
					stack.remove(size-2);//  n      （                     ）
				stack.pop!=n-1://       
					for(i=n-2 to 1)
						find index where index.state!=0;//             （    n-1     ）
					play(index);//            
			
			(n-1).state=0://      
				play(n-1);//         （           ，        ）	
		}
}

이것 은 특정한 고 리 를 옮 기거 나 설치 하 는 작업 일 뿐 전체 게임 을 끝 낼 경우 함 수 를 실행 할 때 높 은 것 에서 낮은 것 으로 순서대로 이 고 리 를 옮 겨 야 합 니 다.(main 함수 참조).main 함수 에 서 는 9 연쇄 의 초기 상태 와 스 택 의 초기 상 태 를 초기 화 해 야 합 니 다.(메 인 함수 참조)
실행 결 과 는 다음 과 같 습 니 다.(네 개의 링)

구체 적 으로 실현 하고 코드 를 직접 붙 입 니 다.

import java.util.*;
public class NC {
	
	public static void move(Node node) {
		if(node.state==1)
			System.out.println("down "+node.num);
		else
			System.out.println("up "+node.num);
	}
	
	public void play(Node[]node,ArrayList<Node> list,int n) {
		boolean deal=false;
 
		if(n==1) {
			if(node[n].state==1)
			{
				move(node[n]);// move the 1st;
				node[n].state=0;
				list.remove(list.size()-1);
			}
			else
			{
				move(node[n]);
				node[n].state=1;
				list.add(node[n]);
			}
		}
		else {
			while(!deal)
			{
				if(node[n-1].state==1) {//     
					if(list.get(list.size()-1).num==n-1)//      
					{
						if(node[n].state==1)
						{
							move(node[n]);
							node[n].state=0;
							deal=true;
							list.remove(list.size()-2);
						}
						else
						{
							move(node[n]);
							node[n].state=1;
							deal=true;
							list.add(list.size()-1,node[n]);
						}
					}
					else//     ，         
					{
						int index=1;
						for(int i=n-2;i>0;i--)//                    。
						{
							if(node[i].state==1) {
								index=i;
								break;
							}
						}
						play(node,list,index);//                 
					}
				}
				//-------------------------------------------------------------------------				
				else if(node[n-1].state==0) {//      
					
					play(node,list,n-1);
			}
		}
	}
	
 
		
	}
	public static void main (String[]args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		Node []node= new Node[n+1];
		for(int i=1;i<n+1;i++)
			node[i]=new Node(i,1);
		ArrayList<Node> list= new ArrayList();
		for(int j=n;j>0;j--)
			list.add(node[j]);
		NC nc= new NC();
		for(int t=n;t>0;t--)
			nc.play(node, list,t);		
	}
}
 
class Node{
	int num;
	int state;
	public Node(int num,int state) {
		this.num=num;
		this.state=state;
	}
}

총결산
자바 재 귀 를 이용 하여'9 연쇄'공식 을 해결 하 는 방법 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 재 귀'9 연쇄'공식 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!