問題描述

這個學期Amy開始學習一門重要課程——線性代數。學到行列式的時候，每次遇到對給定的序列計算其逆序數，她都覺得是個很鬧心的事。所以，她央求她的好朋友Ray為她寫一段程序，用來解決這樣的問題。作為回報，她答應在周末舞會上讓Ray成為她的倫巴舞舞伴。所謂序列A的逆序數，指的是序列中滿足i<j，A[i]>A[j]的所有二元組<i, j>的個數。

輸入

輸入文件包含若幹個測試案例。每個案例的第一行僅含一個表示序列中元素個數的整數N（1《=N《=500000）。第二行含有N個用空格隔開的整數，表示序列中的N個元素。每個元素的值不超過1 000 000 000。N=0是輸入數據結束的标志。

輸出

每個案例僅輸出一行，其中隻有一個表示給定序列的逆序數整數。

輸入樣例

3☐ 1 2 3 2 2 1 0

輸出樣例

0 1

理解問題是解決問題的最基本的要求，理解計算問題要抓住三個要素：輸入、輸出和兩者的邏輯關系。這三個要素中，輸入、輸出數據雖然是問題本身明确給定的，如果輸入包含若幹個案例則要理清每個案例的數據構成。

例如，問題0-1的輸入文件inputdata（本書所有計算問題的輸入假設均存于文件中，統一記為inputdata）中含有若幹個測試案例，每個案例有兩行輸入數據。第1行中的一個整數N表示案例中給定序列的元素個數。第二行含有表示序列中N個元素的N個整數。當讀取到的N=0時意味着輸入結束。

所謂輸入、輸出數據之間的邏輯關系，實質上指的是一個測試案例的輸入、輸出數據之間的對應關系。為把握這一關系，往往需要認真、仔細地閱讀題面，在欣賞題面闡述的故事背景之餘，應琢磨、玩味其中所交代的反應事物特征屬性的數據意義，以及由事物變化、發展所引發的數據變化規律，由此理順各數據間的關系，這是設計解決問題的算法的關鍵所在。

例如，如果我們把問題0-1的一個案例的輸入數據組織成一個數組A[1..N]，我們就要計算出序列中使得i<j，A[i]>A[j]成立的所有二元組<i, j>，統計出這些二元組的數目，作為該案例的輸出數據加以輸出——作為一行寫入輸出文件outputdata（本書所有計算問題的輸出假設均存于文件中，統一記為outputdata）。

對問題有了正确的理解之後，就需要根據數據間的邏輯關系，找出如何将輸入數據對應為正确的輸出數據的轉換過程。這個過程就是通常所稱的“算法”。通俗地說，算法就是計算問題的解決之道。

例如，對問題0-1的一個案例數據A[1..N]，為計算出它的逆序數，我們設置一個計數器變量count（初始化為0）。從j=N，A[j]開始，依次計算各元素與其前面的元素（A[1..j−1]）構成的逆序個數，累加到count中。當j<2時，結束計算返回count即為所求。

有了解決問題的正确算法，就可以利用一種計算機程序設計語言将算法實現為可在計算機上運行的程序。

本文内選用業界使用最廣泛、最成熟的C 語言來實現解決每一個問題的算法。

C 語言是面向對象的程序設計語言，它為程序員提供了一個龐大的标準庫。有趣的是，C 脫胎于C語言。所以，讀者若具有C語言某種程度的訓練，對于理解本書提供的C 代碼一定是大有裨益的。閑話少說，讓我們先來一睹C 語言程序的“芳容”吧。

解決問題0-1“計算逆序數”的C 程序如下。

1 #include <fstream> 2 #include <iostream> 3 #include <vector> 4 using namespace std; 5 int getTheInversion(vector<int> A){ 6 int N=int(A.size()); 7 int count=0; 8 for (int j=N-1; j>0; j--) 9 for (int i=0; i<j; i ) 10 if(A[i]>A[j]) 11 count ; 12 return count; 13 } 14 int main(){ 15 ifstream inputdata("Get The Inversion/inputdata.txt");//輸入文件流對象 16 ofstream outputdata("Get The Inversion/outputdata.txt");//輸出文件流對象 17 int N=0; 18 inputdata>>N; 19 while (N>0) { 20 vector<int> A(N); 21 for (int i=0; i<N; i ) 22 inputdata>>A[i]; 23 int result=getTheInversion(A); 24 cout<<result<<endl; 25 outputdata<<result<<endl; 26 inputdata>>N; 27 } 28 inputdata.close(); 29 outputdata.close(); 30 return 0; 31 }

我們可以把程序分成三部分觀察。

• 第一部分就是程序中的第1～4行，執行預編譯指令。
• 第二部分是第5～13行的函數getTheInversion定義。
• 第三部分是第14～31行，程序的主函數。下面我們就這三個部分逐一加以簡單說明。

① #include指令用來為程序引入“庫”——包含各種已定義的數據類型、類、函數等，實現優質代碼的重用，以提高程序設計的工作效率和程序的質量——搭建一座方便之橋。由于C 中任何運算成分（類型、變量、常量、函數……）均需先聲明、後使用，所以頭文件中就聲明了一組程序所需的具有特殊意義的運算成分。用include指令将指定的頭文件加載進來，程序員就可以方便地訪問這些成分了。此處，首行指令#include <fstream>意味着本程序可以使用系統提供的文件輸入輸出流類的對象，方便地輸入、輸出數據。本書中所有算法的實現代碼涉及輸入輸出的操作都需要進行文件的讀寫操作，所以這條指令将出現在每一個程序文件的首要位置。後面的兩條分别引入控制台輸入輸出對象（cin、cout）和向量類（vector，這是C 标準模闆庫STL提供的可變長數組類模闆）。這些類、對象的引入給大家帶來了極大的方便。語句using namespace std（語句以分号結尾）指出，以上引入的類或對象都是标準庫中的，可按名稱直接訪問。

② 細心的讀者可能已經發現，第5～13行定義的函數int getTheInversion(vector<int> A)就是對算法0-1中僞代碼過程GET-THE-INVERSION(A)的實現。除了某些細節，程序代碼與僞代碼幾乎是一樣的。如果你也有這樣的感覺，我們就有了一種默契：隻要有了僞代碼，我們就能很快地寫出它的實現程序——算法僞代碼就是程序開發的“施工藍圖”。

③ 第14～31行定義的main函數也就是我們在算法0-1之前描述的“計算逆序數”問題數據的輸入與輸出的僞代碼的實現。如果了解到“>>”和“<<”是C 數據流（文本文件就是一個數據流）的輸出、輸入操作符，則會感覺到這段代碼幾乎就是僞代碼的翻版。

程序0-1存儲為文件夾Get The Inversion的文件Get The Inversion.cpp。讀者要在計算機上運行這個程序，需要在你的計算機上安裝一個C 開發軟件（譬如，在PC上安裝一個Visual C 軟件，在iMac上安裝一個Xcode），然後創建一個項目，在其中加載文件laboratory/Get The Inversion/Get The Inversion.cpp。

同樣，解決問題0-2“移動電話”的C 程序是存于文件夾laboratory/Mobil Phone中的文件Mobil Phone.cpp。

END

喜歡的朋友歡迎轉發到朋友圈

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!