uva 110 Meta-Loopless Sorts 用程序寫程序 有點復雜的回溯水題

題目要求寫一個直接用比較排序的pascal程序，挺有趣的一題。

我看題目數據范圍就到8，本來以為貪個小便宜，用switch輸出。

然後發現比較次數是階乘級別的，8的階乘也是挺大的，恐怕會交不上去。

於是改用回溯法。

其實他比較時就是把後面的數一個一個向前比較，然後插到那位前面，繼續回溯。

else的處理比較麻煩而已，改了好久終於跟標准答案一樣了。

縮進沒有處理，提交上去就ac了，看來oj沒有檢查縮進呢，如果有檢查就還得處理一下了。

代碼：（未進行縮進處理）

#include <cstdio>   
const int maxn = 10;  
  
int n, arr[maxn];  
  
void insert_sort(int p, int c) {        //插入排序   
    for (int i = c; i > p; i--)  
        arr[i] = arr[i - 1];  
    arr[p] = c;  
}  
  
int dfs(int d) {  
    int tmp[d + 1];                     //創建數組儲存原來的數值，不然會亂掉   
    for (int j = 1; j <= n; j++)  
        tmp[j] = arr[j];  
    for (int i = d; i >= 1; i--) {           //循環從現排好的串後序進行dfs   
        printf("if %c < %c then\n", arr[i] + 'a' - 1, d + 'a');  
        insert_sort(i + 1, d + 1);          //將接下去的字母插入到i+1的位置   
        if (d + 1 == n) {                   //dfs到最深處，輸出   
            printf("writeln(");  
            printf("%c", arr[1] + 'a' - 1);  
            for (int j = 2; j <= d + 1; j++)  
                printf(",%c", arr[j] + 'a' - 1);  
            printf(")\n");  
            printf("else\n");  
        }  
        else {  
            dfs(d + 1);  
            printf("else\n");  
        }  
        for (int j = 1; j <= n; j++)     //還原數組   
            arr[j] = tmp[j];  
    }  
    insert_sort(1, d + 1);                  //下面是對最後一個情況，即字母插到整個數組前面，這裡是沒有else的   
    if (d + 1 == n) {  
        printf("writeln(");  
        printf("%c", arr[1] + 'a' - 1);  
        for (int j = 2; j <= d + 1; j++)  
            printf(",%c", arr[j] + 'a' - 1);  
        printf(")\n");  
    }  
    else  
        dfs(d + 1);  
    for (int i = 1; i <= n; i++)  
        arr[i] = tmp[i];  
}  
  
int main() {  
    int t;  
    scanf("%d", &t);  
    while (t--) {  
        scanf("%d", &n);  
        //前面部分   
        printf("program sort(input,output);\nvar\n");  
        printf("a");  
        for (int i = 2; i <= n; i++)  
            printf(",%c", i + 'a' - 1);  
        printf(" : integer;\nbegin\nreadln(");  
        printf("a");  
        for (int i = 2; i <= n; i++)  
            printf(",%c", i + 'a' - 1);  
        printf(");\n");  
        dfs(0);             //開始深搜   
        printf("end.\n");  
        if (t != 0)  
            printf("\n");  
    }  
    return 0;  
}  

#include <cstdio>
const int maxn = 10;

int n, arr[maxn];

void insert_sort(int p, int c) {		//插入排序
	for (int i = c; i > p; i--)
		arr[i] = arr[i - 1];
	arr[p] = c;
}

int dfs(int d) {
	int tmp[d + 1];						//創建數組儲存原來的數值，不然會亂掉
	for (int j = 1; j <= n; j++)
		tmp[j] = arr[j];
	for (int i = d; i >= 1; i--) {			//循環從現排好的串後序進行dfs
		printf("if %c < %c then\n", arr[i] + 'a' - 1, d + 'a');
		insert_sort(i + 1, d + 1);			//將接下去的字母插入到i+1的位置
		if (d + 1 == n) {					//dfs到最深處，輸出
			printf("writeln(");
			printf("%c", arr[1] + 'a' - 1);
			for (int j = 2; j <= d + 1; j++)
				printf(",%c", arr[j] + 'a' - 1);
			printf(")\n");
			printf("else\n");
		}
		else {
			dfs(d + 1);
			printf("else\n");
		}
		for (int j = 1; j <= n; j++)		//還原數組
			arr[j] = tmp[j];
	}
	insert_sort(1, d + 1);					//下面是對最後一個情況，即字母插到整個數組前面，這裡是沒有else的
	if (d + 1 == n) {
		printf("writeln(");
		printf("%c", arr[1] + 'a' - 1);
		for (int j = 2; j <= d + 1; j++)
			printf(",%c", arr[j] + 'a' - 1);
		printf(")\n");
	}
	else
		dfs(d + 1);
	for (int i = 1; i <= n; i++)
		arr[i] = tmp[i];
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		//前面部分
		printf("program sort(input,output);\nvar\n");
		printf("a");
		for (int i = 2; i <= n; i++)
			printf(",%c", i + 'a' - 1);
		printf(" : integer;\nbegin\nreadln(");
		printf("a");
		for (int i = 2; i <= n; i++)
			printf(",%c", i + 'a' - 1);
		printf(");\n");
		dfs(0);				//開始深搜
		printf("end.\n");
		if (t != 0)
			printf("\n");
	}
	return 0;
}