问题0-1　计算逆序数

问题描述

这个学期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 322 10

输出样例

01

理解问题是解决问题的最基本的要求，理解计算问题要抓住三个要素：输入、输出和两者的逻辑关系。这三个要素中，输入、输出数据虽然是问题本身明确给定的，如果输入包含若干个案例则要理清每个案例的数据构成。

例如，问题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

喜欢的朋友欢迎转发到朋友圈