《趣题学算法》—第0章0.2节计算问题

本节书摘来自异步社区《趣题学算法》一书中的第0章0.2节计算问题，作者徐子珊,更多章节内容可以访问云栖社区“异步社区”公众号查看。

0.2　计算问题
上面已经说到什么是计算问题，下面就来看一个有趣的计算问题。

问题描述
这个学期Amy开始学习一门重要课程——线性代数。学到行列式的时候，每次遇到对给定的序列计算其逆序数，她都觉得是个很闹心的事。所以，她央求她的好朋友Ray为她写一段程序，用来解决这样的问题。作为回报，她答应在周末舞会上让Ray成为她的伦巴舞舞伴。所谓序列A的逆序数，指的是序列中满足iA[j]的所有二元组 的个数。

输入
输入文件包含若干个测试案例。每个案例的第一行仅含一个表示序列中元素个数的整数N（1leqslantNleqslant500000）。第二行含有N个用空格隔开的整数，表示序列中的N个元素。每个元素的值不超过1 000 000 000。N=0是输入数据结束的标志。

输出

每个案例仅输出一行，其中只有一个表示给定序列的逆序数整数。

输入样例

输出样例

0
1

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

例如，问题0-1的输入文件inputdata（本书所有计算问题的输入假设均存于文件中，统一记为inputdata）中含有若干个测试案例，每个案例有两行输入数据。第1行中的一个整数N表示案例中给定序列的元素个数。第二行含有表示序列中N个元素的N个整数。当读取到的N=0时意味着输入结束。

所谓输入、输出数据之间的逻辑关系，实质上指的是一个测试案例的输入、输出数据之间的对应关系。为把握这一关系，往往需要认真、仔细地阅读题面，在欣赏题面阐述的故事背景之余，应琢磨、玩味其中所交代的反应事物特征属性的数据意义，以及由事物变化、发展所引发的数据变化规律，由此理顺各数据间的关系，这是设计解决问题的算法的关键所在。

例如，如果我们把问题0-1的一个案例的输入数据组织成一个数组A[1..N]，我们就要计算出序列中使得iA[j]成立的所有二元组，统计出这些二元组的数目，作为该案例的输出数据加以输出——作为一行写入输出文件outputdata（本书所有计算问题的输出假设均存于文件中，统一记为outputdata）。

对问题有了正确的理解之后，就需要根据数据间的逻辑关系，找出如何将输入数据对应为正确的输出数据的转换过程。这个过程就是通常所称的“算法”。通俗地说，算法就是计算问题的解决之道。

例如，对问题0-1的一个案例数据A[1..N]，为计算出它的逆序数，我们设置一个计数器变量count（初始化为0）。从j=N，A[j]开始，依次计算各元素与其前面的元素（A[1..j−1]）构成的逆序个数，累加到count中。当j<2时，结束计算返回count即为所求。