趣题学算法 - (EPUB全文下载)

文件大小：0.42 mb。
文件格式：epub 格式。
书籍内容：

趣题学算法
Chapter 0 从这里开始
Chapter 1 计数问题
Chapter 2 数据集合与信息查找
Chapter 3 现实模拟
Chapter 4 组合优化问题
Chapter 5 动态规划与贪婪策略
Chapter 6 图的搜索算法
Chapter 7 数论问题
Chapter 8 动手做
Chapter 9 C++程序设计
Chapter 0　从这里开始
0.1　App程序与算法
0.2　计算问题
0.3　算法的伪代码描述
0.4　算法的正确性
0.5　算法分析
0.6　算法运行时间的渐近表示
0.7　算法的程序实现
0.8　从这里开始
0.1　App程序与算法
信息时代，人们时刻都在利用各种App解决生活、工作中的问题，或获取各种服务。早晨，手机里设定的闹钟铃声（或你喜欢的音乐）将你唤醒。来到餐厅，你用手中的IC卡到取餐处的刷卡机上支付美味早餐的费用。上班途中，打开手机上的音乐播放器，用美妙的乐声，打发掉挤在公交车上的乏味的时间。上班时，利用计算机中的各种办公软件处理繁忙的业务。闲暇时，你用平板电脑里的视频程序看一部热映的大片，或在淘宝网上选购你喜欢的宝贝。晚间，你用QQ或Facetime与远方的朋友聊天、交流情感……凡此种种，不一而是。
五彩缤纷的App后面是什么？这些神奇的体验是怎么创造出来的？如果你对这样的问题感兴趣的话，我们就成为朋友了。从这里开始，我们将探索创造App——计算机（及网络）应用程序的基本原理和基本技能。
其实，能用计算机（包括各种平板电脑、智能手机）解决的是所谓的“计算问题”，也就是有明确的输入与输出数据的问题。解决计算问题就是用一系列基本的数据操作（算术运算、逻辑运算、数据存储等）将输入数据转换成正确的输出数据。能达到这一目标的操作序列称为解决这一计算问题的“算法”。App就是在一定的计算机平台（计算机设备及其配备的操作系统）上，用这个计算机系统能识别的语言来实现算法的程序。
因此，对上述的第一个问题，我们的答案是：App背后的是算法。算法是解决计算问题的方案。要用计算机来解决应用问题，首先要能将该问题描述成计算问题——即明确该问题的输入与输出数据。只有正确、明白地描述出计算问题，才有可能给出解决该问题的算法。作为起点，本书并不着眼于如何将一个实际的应用形式化地描述为一个计算问题，而是向你描述一些有趣的计算问题，并研究、讨论如何正确、有效地解决这些问题。通过对这些问题的解决，使我们对日常面对的那些App有着更清醒、更理智的认识。可能的话，也许哪一天你也能为你自己，或者朋友、爱人创造出你和他们喜欢的App。
0.2　计算问题
上面已经说到什么是计算问题，下面就来看一个有趣的计算问题。
问题0-1　计算逆序数
问题描述
这个学期Amy开始学习一门重要课程——线性代数。学到行列式的时候，每次遇到对给定的序列计算其逆序数，她都觉得是个很闹心的事。所以，她央求她的好朋友Ray为她写一段程序，用来解决这样的问题。作为回报，她答应在周末舞会上让Ray成为她的伦巴舞舞伴。所谓序列A的逆序数，指的是序列中满足iA[j]的所有二元组的个数。
输入
输入文件包含若干个测试案例。每个案例的第一行仅含一个表示序列中元素个数的整数N（1N500000）。第二行含有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]，我们就要计算出序列中使得iA[j]成立的所有二元组，统计出这些二元组的数目，作为该案例的输出数据加以输出——作为一行写入输出文件outputdata（本书所有计算问题的输出假设均存于文件中，统一记为outputdata）。
对问题有了正确的理解之后，就需要根据数据间的逻辑关系，找出如何将输入数据对应为正确的输出数据的转换过程。这个过程就是通常所称的“算法”。通俗地说，算法就是计算问题的解决之道。
例如，对问题0-1的一个案例数据A[1..N]，为计算出它的逆序数，我们设置一个计数器变量count（初始化为0）。从j=N，A[j]开始，依次计算各元素与其前面的元素（A[1..j−1]）构成的逆序个数，累加到count中。当j<2时，结束计算返回count即为所求。 0.3　算法的伪代码描述 上一节最后一段使用自然语言（汉语）描述了解决“计算逆序数”问题的算法。即如何将输入数据转换为输出数据的过程。在需要解决的问题很简单的情况下（例如“计算逆序数”问题），用自然语言描述解决这个问题的算法是不错的选择。但是，自然语言有一个重要特色——语义二岐性。语义二岐性在文学艺术方面有着非凡的作用：正话反说、双关语……。由此引起的误会、感 ............

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。