창고 의 합 법 적 인 출력 시퀀스

창고 의 합 법 적 인 출력 시퀀스
최근 에 스 택 을 쓴 실험 문 제 는 추가 문제 에서 합 법 적 인 출력 서열 과 관련된다.
< 1 > 스 택 의 입력 서열 이 1, 2, 3,..., n 이 라 고 가정 하고 디자인 알고리즘 은 주어진 서열 을 실현 하여 이 스 택 의 합 법 적 인 출력 서열 인지 여 부 를 판단 합 니 다. <2 > 스 택 의 입력 서열 이 1, 2, 3,..., n 이 라 고 가정 하고 디자인 알고리즘 은 가능 한 모든 스 택 서열 을 구한다.
첫째, 인터넷 에서 규칙 을 찾 을 수 있 습 니 다. 스 택 서열 이 합 법 적 인지 판단 하 는 규칙 은 스 택 서열 에 있 습 니 다. 요소 i 이후 모든 i 보다 작은 요소 간 에 내림차 순 으로 배열 되 어야 합 니 다. 요소 i 는 처음부터 뒤로 옮 겨 다 녀 야 합 니 다.따라서 두 순환 과 한 변 수 를 도입 해 최소 치 를 표시 한 뒤 순서대로 비교 해 야 한 다 는 판단 이다.

bool StackArray::JudgeMatchedStackArray(int a[],int len)
{
    int low=0;//           
    for(int i=0;i<len;++i)//  i        
    {
        low=a[i];
        for(int j=i;j<len;++j)//   i      ，    
        {
            if(a[j]/ / 우선 원소 i 보다 작은 원 소 를 찾 아야 합 니 다.
{
if(a[j]>low)
return false;
else / / 이 요소 들 이 내림차 순 으로 배열 되 어 있 는 지 검증 합 니 다.
low = a[j];
}
}
}
return true;
}

두 번 째 질문 은 비교적 복잡 하고 기본 적 인 사 고 는 재 귀적 으로 해결 하 는 것 이다.여기에 사고방식 을 제공 하 는 두 개의 인터넷 주 소 를 붙인다.
1. (1) 우 리 는 전에 말 했 듯 이 합 법 적 인 스 택 시퀀스 조건: 모든 스 택 수 이후 의 것 과 이 수의 수 보다 작은 것 은 반드시 내림차 순 으로 배열 해 야 한다.예 를 들 면 하나, 둘, 다섯, 셋, 넷.5 에 대해 말하자면 뒤의 3, 4 는 모두 5 보다 작 지만 3, 4 는 오름차 이다.합 법 적 인 스 택 시퀀스 가 아 닐 겁 니 다.이 를 통 해 우 리 는 모든 배열 을 구하 고 그 중에서 불법 서열 을 제거 할 수 있다 는 것 을 알 수 있다.분명히 서열 의 길이 가 증가 할 때 불필요 한 계산 이 너무 많 고 효율 이 너무 낮다.(2) 스 택 에 들 어가 서 스 택 을 나 가 는 과정 을 모 의 하면 매번 두 가지 선택 이 있 습 니 다. 스 택 에 들 어가 거나 스 택 을 나 갑 니 다.분명히 귀속 방식 에 따라 실행 할 수 있다.그러나 또 하나의 문 제 는 일반적으로 귀속 되 고 귀속 차원 간 의 데이터 전송 문제 와 거의 관련 이 없다 는 것 이다.이 과정 을 모 의 할 때 스 택 의 정 보 는 상층 에서 하층 으로 전달 되 고 마지막 에 상층 으로 돌아 갈 때 반드시 스 택 의 상 태 는 하층 으로 바 뀌 었 다.해결 방법 은 하층 이 돌아 올 때 창고 의 원래 상 태 를 회복 하 는 것 이다.이렇게 돌아 가면 틀 리 지 않 을 거 야. -모든 스 택 시퀀스 구하 기
의사 코드 원본

dostack(    ，   ，    )  

if(      )  
{  
        if(     )  
    {
                   
    }
    else  
    {
             ，        

        dostack(    ，   ，    )
    }
}
else  
{
        if(     ) 
    { 
                  2、   2、    2 //            ，
        //           ，          

               2         2  

        dostack(    2，   2，    2)
    }

                     

    dostack(    ，   ，    ) 
}

한 창고 의 출고 서열 을 계산 하려 면 몇 가지 가능성 이 있 습 니까?상기 코드 1 에 기술 변 수 를 추가 하고 마지막 으로 가능 한 종 수 를 표시 할 수 있 습 니 다.모든 가능 한 문 제 를 출력 할 필요 가 없 는 경우 에 도 해당 하 는 계산 공식 이 있다. I (n) 에 대해 C (2n, n) - C (2n, n - 1) 개의 스 택 시퀀스 가 있다.
부호 블록

void StackArray::PopOrderStackArray(StackArray other,QueueArray another)
//      ，other      ，another       
{
    if(EmptyStackArray())
    {
        if(other.EmptyStackArray())
            another.printQueueArray();
        else
        {
            another.insertQueueArray(other.PopStackArray());
            PopOrderStackArray(other,another);
        }
    }
    else
    {
        if(!other.EmptyStackArray())
        {
            StackArray a(*this),b(other);
            QueueArray c(another);
            c.insertQueueArray(b.PopStackArray());
            a.PopOrderStackArray(b,c);
        }
        other.PushStackArray(PopStackArray());
        PopOrderStackArray(other,another);
    }
    return ;
}

실행 결 과 는 다음 과 같 습 니 다.
1 2 3 1 3 2 2 1 3 2 3 1 3 2 1