光影切割问题之求解逆序数

1. 问题

编程之美1.7光影切割问题可以概括为：

设有两条完全相同的垂直方向上的两条长度相同的线段a和b，且它们对应的端点在同一水平线上。

已知：在这两条线段之间存在n条线段，且每条线段的起点都在线段a上，终点在线段b上。

求：这n条线段将线段a和b构成的矩形平面分割成的块数B。

2. 求解

方法一：不难发现B = n + 1 + i，其中i表示图中直线的个数。因此该问题就转化为求直线交点个数的问题。

方法二：更为巧妙，进一步将问题转化为求逆序数问题。但书中没有给出如何求解逆序数。

3. 求逆序数

3.1 构造测试数据集

以下为我用于产生测试数据的代码，共差生9999个随机整数。值得注意的是该数据集中存在相同的元素，在求解逆序数时应特别注意。产生的随机数将存储到文件dataSource.txt中。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define DATANUM 9999 int main() { int i = 0; int temp; srand((unsigned)time(NULL)); ofstream fin("dataSource.txt"); for (i=0; i
        
        

 
 
        
3.2 问题分析
 
        
 以下部分纯属个人理解，如有不正确欢迎大家指正。
 
        
 一个数的逆序数为在它后边比它小的数据的个数。如有序列3、1，对数据3来说后边只有一个1比它小，因此它的逆序数为1；而对于1来说后边没有数据，则它的逆序数为0。
 
        
 仔细分析后不难发现一个数串所有逆序数之和与排序时数据交换的次数相同（按照从小到大的顺序排列）。例如有序列3、2、1，用冒泡排序需要交换3次，明显与该序列的逆序数相等。
 
        
 实际上选择枢纽为2的快排，只需交换了一次。简单分析可得：快速排序没有进行1和3的比较，而逆序数需要考虑任何两个数字之间的关系。因此快速排序不可用，且不稳定的排序算法也是不可用的，因为他们会交换相同数字之间的位置。另外逆序数可以用分支法来求解，即归并算法。以下为用冒泡排序和归并排序求解逆序数的实现。
 
        
#include 
         
          
#include 
          
            #include 
           
             #include 
            
              using namespace std; #define MAXNUM 9999 #define MAXNUMlENGTH 10 void readData(int sourceData[MAXNUM]); int bubbleSort(int sourceData[MAXNUM]); int merge(int sourceData[MAXNUM], const int lStart, const int lEnd, const int rStart, const int rEnd); int mergesort(int sourceData[MAXNUM], int begin, int end); void output(int sourceData[MAXNUM]); int main() { int sourceData[MAXNUM]; readData(sourceData); int choice = 0; int flag = 1; while (flag) { cout<<"Run BullSort, please input 0"<
             
              >choice; switch (choice) { case 0: flag = 0; cout<<"BullleSort result: "; cout<
              
               >tempc) { sourceData[i++] = atoi(tempc); } fin.close(); } //ascending int bubbleSort(int sourceData[MAXNUM]) { int exchangeTime = 0; int temp = 0; for (int i=0; i
               
                sourceData[j]) { temp = sourceData[j-1]; sourceData[j-1] = sourceData[j]; sourceData[j] = temp; exchangeTime++; } } } return exchangeTime; } void output(int sourceData[MAXNUM]) { for (int i=0; i
                
                 >1; return mergesort(sourceData, begin, mid) + mergesort(sourceData, mid+1, end) + merge(sourceData, begin, mid, mid+1, end); } }