UVa 110 沒有循環的排序程式

題意：構造Pascal的排序程式。初看是寫Pascal程式，不了解的以為會很難，但其實程式的大部分是固定的，直接printf就可以，主要在于寫比較的if-else部分。

思路：看sample out可以大概知道程式的構成，其他部分直接輸出，主要寫比較的部分。比較的時候，可以看成兩個集合，A是已排好序的，S是全集，cur是從左到右掃描S的目前位置。用遞歸寫的，前半部分是當目前位置cur到達n時，即可以輸出了；剩下的是如何填寫目前位置cur以及維持A是已排好序的這個性質。将新元素S[cur]從A的最右端往左開始比較，如果新元素S[cur]較大，則直接放在A的目前元素的右邊即i+1位置；否則，新元素較小，将A的目前元素右移一位，即拷貝到i+1位置，然後新元素繼續與左邊一個元素比較。還有一點就是因為數組傳到函數後會改變内容的，是以在每次傳函數前，新構造一個數組B，複制A數組的内容然後輸出。否則的話，不用B數組，直接傳A數組，對于兩個元素沒問題，對于三個元素的話，在if a<b 這個部分是正确的，而在這個條件開啟的else裡面就會發現沒有a了，而又兩個c，這就是因為遞歸雖然傳回了，但數組A已被修改，第一位a已被修改為c。另外，題目沒有說縮進的要求，果然送出後發現每行的縮進是沒有要求的，隻要保證writeln語句單獨在一行即可。

本地修改多次，一次AC，取得目前所做所有題目中最高排名74，之前最好是11234題排79。就是做得太慢了，想了好久才會，開始也在考慮縮進的問題、畢竟sample out中第一個if-else和後來的if-else縮進是不同的。。。

Code：

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

void solve(int n);
void compare(int n,char *A,char *S,int cur);

char str[]="abcdefghijklmn"; 

int main()
{
  int m;
  scanf("%d",&m);
  while(m-->0)
  {
    int n;
    scanf("%d",&n);
    solve(n);
    if(m) printf("\n");
  }
  return 0;  
}

void solve(int n)
{
  printf("program sort(input,output);\n");
  printf("var\n");
  for(int i=0;i<n-1;++i) printf("%c,",str[i]);
  printf("%c : integer;\n",str[n-1]);
  printf("begin\n");
  printf("  readln(");
  for(int i=0;i<n-1;++i) printf("%c,",str[i]);
  printf("%c);\n",str[n-1]);
  char A[10];
  compare(n,A,str,0);
  printf("end.\n");
}

void compare(int n,char *A,char *S,int cur)
{
  if(cur==n)
  {
    printf("writeln(");
    for(int i=0;i<cur-1;++i) printf("%c,",A[i]);
    printf("%c)\n",A[cur-1]);
    return ;        
  }
  for(int i=cur-1;i>=0;--i)
  {
    printf("  if %c < %c then\n",A[i],S[cur]);
    A[i+1]=S[cur];
    char B[10];
    strcpy(B,A);
    compare(n,B,S,cur+1);
    printf("else\n");
    A[i+1]=A[i];
    A[i]=S[cur];
    //compare(n,A,S,cur+1);
  }
  A[0]=S[cur];//初始cur=0時 
  char B[10];
  strcpy(B,A);
  compare(n,B,S,cur+1);
}