0,1,2,…,…,(n-1) 共n个数依次进/出栈,要求找出所有序列。

某1时刻,对某数k和栈stack,可能的动作有2

  • k进栈
  • stack做pop动作

只要写1递归函数,涵盖这两种可能,递归结束条件是当前k=n

#include <stdio.h>
#include <string.h>

#define N 4

int stack[N];
char string[N];
long count=0;

void enumerateStack(int* stack, int top, int n, char* out) {
    if(n==N) {
        count++;
        int i;
/*
        int length=strlen(out);
        for(i=0;i<length;i++) {
            printf("%d", out[i]);
        }
*/
        printf("%s ", out);
        for(i=top-1;i>=0;i--) {
            printf("%c", stack[i]+'0');
        }
        printf("\n");
    } else {
        stack[top++]=n;
        enumerateStack(stack, top, n+1, out);
        top--;

        if(top>0) {
            top--;
            int length=strlen(out);
            out[length]=stack[top]+'0';
            out[length+1]='';
            enumerateStack(stack, top, n, out);
            stack[top]=out[length]-'0';
            top++;
            out[length]='';
        }
    }
}

int main() {
    string[0]='';
    string[N]='';

    enumerateStack(stack, 0, 0, string);
    printf("count=%d\n", count);

/*
    string[0]='0'+0;
    string[1]='0'+1;
    string[2]='0'+2;
    string[3]='0'+3;
    string[4]='';
    printf("%s\n", string);
    int i=atoi(string+3);
    printf("i=%d\n", i);
*/
    return 0;
}
Advertisements