두 개의 동 구성 문제 의 비 궁 거 해법.

최근 에 데이터 구조의 책 을 뒤 져 봤 는데 대학교 3 학년 수업 을 들 었 는데 지금 은 잊 어 버 린 내용 이 있 습 니 다.책의 마지막 장 '데이터 구조의 종합 응용' 에는 N 열 기차 가 역 에 드 나 드 는 문제 가 있 는데 문 제 를 간소화 했다. 바로 N 개의 수 드 나 드 는 문제 이다. 즉, N 개의 수 는 몇 가지 서로 다른 드 나 드 는 순서 가 있 는 지 (스 택 에 들 어 가 는 순서 만 고려 하고 수량의 크기, 즉 N 개의 '똑 같은' 수 는 고려 하지 않 는 다).
    그때 저 는 궁 거 법 으로 만 들 었 습 니 다. 즉, N 개 수의 출입 창고 의 전체 배열 을 구하 고 특정한 위치 에 존재 하 는 전진 창고 의 횟수 가 출고 횟수 보다 적은 배열 을 삭 제 했 습 니 다.지금 다시 생각해 보 니 자신 이 분석 한 키 가 줄 을 서 는 문제 가 떠 올 랐 다. 12 명의 키 가 다른 사람 이 두 줄 로 서 야 한다. 각 줄 은 반드시 작은 것 에서 높 은 것 으로 배열 해 야 한다. 그리고 두 번 째 줄 은 대응 하 는 첫 번 째 줄 의 사람 보다 높다. 배열 방식 이 몇 가지 가 있 느 냐 고 물 었 다.
 
    사실 이 두 가지 문제 이전에 교묘 한 동구 관계 가 존재 했다. 키 가 줄 을 서 는 문제 에서 우 리 는 먼저 12 명의 키 가 다른 사람 을 키 에 따라 낮은 사람 에서 높 은 사람 으로 일렬 로 세 울 수 있다. 매번 에 팀 의 머리 를 첫 번 째 줄 이나 두 번 째 줄 의 꼬리 에 넣 을 때마다 첫 번 째 줄 의 인원 이 두 번 째 줄 보다 적지 않 으 면 된다.그 렇 기 때문에 언제나 두 번 째 줄 의 사람 은 반드시 첫 번 째 줄 의 높이 를 보장 한다.한편, N 개 수의 창고 출입 문제 에서 N = 12 를 가정 하면 창고 에 들 어 가 는 전체 작업 중의 순서 (전체 작업 은 창고 에 들 어 가 는 것 과 창고 에서 나 오 는 것 으로 구성) 를 키 줄 서기 문제 중의 첫 번 째 줄 에 놓 을 수 있다. 이에 따라 창고 에서 나 오 는 순 서 를 두 번 째 줄 에 놓 아 언제든지 첫 번 째 줄 에 들 어 가 는 횟수 가 적지 않 고 두 번 째 줄 의 창고 출입 횟수 를 확보 하면 된다.
 
    나 는 키 줄 서기 문 제 를 해결 하 는 코드 를 수정 했다. 마찬가지 로 가난 하지 않 은 방법 으로 이 문 제 를 해결 했다.

import java.util.Stack;

public class PushPopStack {

	private int count = 0;
	private int total = 0;
	private Stack<Integer> pushOrders = new Stack<Integer>();	//       

	public PushPopStack(int total) {
		this.total = total;
	}

	private void printOrders() {
		for (int operOrder = 1, i = 0; operOrder <= total; operOrder++) {
			if (i < pushOrders.size() && pushOrders.get(i) == operOrder) {
				System.out.print("   ");
				i++;
			} else {
				System.out.print("   ");
			}
		}
		System.out.println();
	}

	private void pushOrder(int order, int level) {
		pushOrders.push(order);
		if (level >= total / 2) {
			count++;
			printOrders(); //          
			pushOrders.pop();
			return;
		}

		for (int i = order + 1; i < 2 * (level + 1); i++)
			pushOrder(i, level + 1);
		pushOrders.pop();
	}

	public void pushPopOrder() {
		pushOrder(1, 1);
		System.out.println(total + "        " + count + "          。");
	}

	public static void main(String[] args) {
		PushPopStack stack = new PushPopStack(12);
		stack.pushPopOrder();
	}
}

 
    제 블 로그 에는 '알 리 바 바 의 키 줄 서기 문제 에 대한 생각' 이라는 글 이 있 는데 그 안에 상세 한 분석 과 해결 과정 이 있 습 니 다.사실은 이 두 가지 문제 에 대해 편리 한 해결 방법 이 하나 더 있다. 카 틀 란 공식 C (2n, n) / (n + 1) 를 사용 하여 n = N / 2 를 대 입 하면 전체적인 배열 수 를 구 할 수 있 지만 구체 적 인 배열 순 서 를 구 할 수 없다.제 가 인터넷 에서 검색 해 봤 는데 이런 동 질감 의 문제 가 아직도 적지 않 습 니 다. 그러나 구체 적 인 배열 순 서 를 구 할 때 비 궁 거 적 인 해결 방법 을 거의 보지 못 했 습 니 다. 그리고 여러분 께 다른 비 궁 거 적 인 해법 이 있 는 지 여 쭤 보 겠 습 니 다.