UVA110- Meta-Loopless Sorts(模擬全排列)

UVA110- Meta-Loopless Sorts(模擬全排列)

題目鏈接

題意：給你n個數，要求按照題目所給的規則大小排序，輸出所有可能的結果。

思路：其實求出來的所有序列是n個數的全排列，那麼難點在於怎麼按照題目所給的格式輸出。我們可以看出其實是在已知的序列上插空，所以就可以使用回溯來插入元素，這裡可以使用vector，方便元素的插入。

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int MAXN = 10;

char str[MAXN];
int n;

void space(int cnt) {
    for(int i = 0; i < cnt; i++)  
        printf("  ");  
}

void deal(int cur, vector &s) {
    if (cur == n) {
        space(n);
        printf("writeln("); 
        printf("%c", s[0]);
        for (int i = 1; i < n; i++) 
            printf(",%c", s[i]);
        printf(")\n");
        return;
    }
    else {
        for (int i = cur; i >= 0; i--) {
            space(cur);
            if (i < cur) 
                printf("else ");
            if (i)
                printf("if %c < %c then", s[i - 1], cur + 'a');
            printf("\n"); 
            vector ss(s); 
            ss.insert(ss.begin() + i, 'a' + cur);
            deal(cur + 1, ss);
        }  
    }  
}

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &n);     
        for (int i = 0; i < n; i++)
            str[i] = 'a' + i;
        printf("program sort(input,output);\nvar\n");
        printf("%c", str[0]);
        for (int i = 1; i < n; i++)
            printf(",%c", str[i]);
        printf(" : integer;\nbegin\n");
        printf("  readln(%c", str[0]);
        for (int i = 1; i < n; i++)
            printf(",%c", str[i]);
        printf(");\n");
        vector s;
        s.push_back('a');
        deal(1, s);
        printf("end.\n");
        if (cas)
            printf("\n"); 
    }
    return 0;
}