uva331

 

交换一个数组的相邻两个元素可以达到对数组排序的功能，类似于冒泡排序，但交换的方案可能不止一种。比如说数组A【3】为3,2,1，要想排为1,2,3，可以先交换位置1和2的元素（数组变为2，3，1），然后交换位置2和3的元素（变为2，1，3），最后交换位置1和2的（变为1，2，3），此为方案一，具体可以用1,2,1（数字即每次交换的第一个数的位置）来描述。当然还可以先交换位置2和3（312），然后交换位置1和2（132）最后交换位置2和3（123），如上的描述方法便是2,1,2，此为方案二。当然这样的方案是无穷多的，比如1，1，2，1，2同样可以实现排序，但这种情况下前两次交换是在做无用功，不是移动次数最小的方案。此题要求出移动次数最少的方案有多少个，如例子中的情况就只有2种方案。

 

理解了题意就不难做了，还是继续回溯，达到顺序后方案数加1，如果一开始就是顺序的话则不进行深搜。

 

#include<iostream>  
  
using namespace std;  
  
int n,result,data[5];  
  
bool isorder()  
{  
    for (int i=0;i<n-1;i++)  
        if (data[i]>data[i+1])  
            return false;  
    return true;  
}  
void dfs()  
{  
    int tmp,i;  
    if (isorder())  
        result++;  
    else  
    {  
        for(i=0;i<n-1;i++)  
        {  
            if (data[i]>data[i+1])  
            {  
                tmp=data[i];data[i]=data[i+1];data[i+1]=tmp;  
                dfs();  
                tmp=data[i];data[i]=data[i+1];data[i+1]=tmp;  
            }  
        }  
    }  
  
}  
int main()  
{  
    int col=0;  
    while (cin>>n&&n)  
    {  
        col++;  
        for (int i=0;i<n;i++)  
            cin>>data[i];  
        result=0;  
        if (!isorder())  
            dfs();  
        cout<<"There are "<<result<<" swap maps for input data set "<<col<<"."<<endl;  
  
    }  
    return 0;  
}  

 

 

补充：软件开发 , C++ ,