《趣题学算法》—第0章0.7节算法的程序实现

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

0.7 算法的程序实现
有了解决问题的正确算法，就可以利用一种计算机程序设计语言将算法实现为可在计算机上运行的程序。本书选用业界使用最广泛、最成熟的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 j--)

9 for (int i=0; i i++)

10 if(A[i] A[j])

11 count++;

12 return count;

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 i++)

22 inputdata A[i];

23 int result=getTheInversion(A);

24 cout result endl;

25 outputdata result endl;

26 inputdata N;

28 inputdata.close();

29 outputdata.close();

30 return 0;

程序0-1 实现解决“计算逆序数”问题算法的C++程序

关于C++语言的各种细节（语言基础、支持语言的库、运用语言的各种技术等），我们将在本书的第9章，通过实现本书中算法的实际代码展开讨论。此处，我们仅仅借程序0-1做一个初步的认识。

我们可以把程序分成三部分观察。第一部分就是程序中的第1～4行，执行预编译指令。第二部分是第5～13行的函数getTheInversion定义。第三部分是第14～31行，程序的主函数。下面我们就这三个部分逐一加以简单说明。

① #include指令用来为程序引入“库”——包含各种已定义的数据类型、类、函数等，实现优质代码的重用，以提高程序设计的工作效率和程序的质量——搭建一座方便之桥。由于C++中任何运算成分（类型、变量、常量、函数……）均需先声明、后使用，所以头文件中就声明了一组程序所需的具有特殊意义的运算成分。用include指令将指定的头文件加载进来，程序员就可以方便地访问这些成分了。此处，首行指令#include 意味着本程序可以使用系统提供的文件输入输出流类的对象，方便地输入、输出数据。本书中所有算法的实现代码涉及输入输出的操作都需要进行文件的读写操作，所以这条指令将出现在每一个程序文件的首要位置。后面的两条分别引入控制台输入输出对象（cin、cout）和向量类（vector，这是C++标准模板库STL提供的可变长数组类模板）。这些类、对象的引入给大家带来了极大的方便。语句using namespace std（语句以分号结尾）指出，以上引入的类或对象都是标准库中的，可按名称直接访问。

② 细心的读者可能已经发现，第5～13行定义的函数int getTheInversion(vector 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。

异步社区 异步社区(www.epubit.com)是人民邮电出版社旗下IT专业图书旗舰社区，也是国内领先的IT专业图书社区，致力于优质学习内容的出版和分享，实现了纸书电子书的同步上架，于2015年8月上线运营。公众号【异步图书】，每日赠送异步新书。