题意：只能交换相邻的数。要把一个数组这样交换以形成升序。问最少交换次数的不同交换顺序有多少种。
思路：还是没想到，看到别人题解中一句话，茅塞顿开：每次从头选两个需要交换的位置进行交换。只有降序才需要交换，而且可以看到每次降序的调换都是有意义的。这样每次从头找一个需要交换的位置，就是不同的方案。当某次从头扫描到尾没有需要交换的位置时，则已经排好序，就是交换次数，用一个flag变量标志。
0.022s，还好，，就没有剪枝优化。这题还是可以剪枝的。
这题对回溯法的应用和思路很有启发意义~
Code：
#include<stdio.h>void dfs(int cnt,int n);void swap(int *a,int i,int j);int a[6];int bestcnt;int num;int main(){ int t=1; int n; while(scanf("%d",&n)==1 && n) {for(int i=0;i<n;++i) scanf("%d",&a[i]);num=0;bestcnt=500;dfs(0,n);printf("There are %d swap maps for input data set %d.\n",num,t++); } return 0;}void dfs(int cnt, int n){ int flag=0; for(int i=0;i<n-1;++i) {if(a[i]>a[i+1]){flag=1;swap(a,i,i+1);dfs(cnt+1,n);swap(a,i+1,i);} } if(flag==0) {if(cnt && cnt<bestcnt) { num=1; bestcnt=cnt;}else if(cnt==bestcnt) { num++;}}}void swap(int *a,int i,int j){ int t=a[i]; a[i]=a[j]; a[j]=t;}
你的内心会被洗成一片空白，自由而宁静，
