uva-331-枚举-交换的方案数-白红宇

uva-331-枚举-交换的方案数

阅读量：5887 次

发布时间：2019-06-19

本文共 991 字，大约阅读时间需要 3 分钟。

　　题意:冒泡排序,最小交换数的前提下有多少用方案把数组变成从小到大的顺序,

　　注意: 3 2 1

3的下表是1 2的是2 1的是3 交换 3 2,那么第一个交换数是1

最小交换数=逆序数的和

那么,只要我们不做无用的交换,交换次数一定是最小的

#include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include 
              
               #include
               
                #include 
                
                 #include 
                 
                  using namespace std;int n;int a[10];int total = 0;void swap(int s, int e){ int t; t = a[s]; a[s] = a[e]; a[e] = t;}int ok = 0;int search(){ for(int i = 0; i < n - 1; i++) { if(a[i] > a[i + 1]) { swap(i,i+1); ok=1; search(); ok=0; swap(i,i+1); } } if(ok) total++; return 0;}int main(){ freopen("d:\\1.txt", "r", stdin); string str="There are %d swap maps for input data set %d.\n"; int t = 0; while (cin >> n && n) { total = 0; ++t; for(int i = 0; i < n; i++) cin >> a[i]; search(); printf(str.c_str(),total,t); } return 0;}