登山路

来自计算思维百科
跳转至: 导航搜索
登山路1.jpg

名山“末日火山”有一条超长的登山路。此路沿着山脊上下起伏,由于路程太长,没有特殊装备就无法走完全程。为了促进旅游行业,人们想另行开发此登山路的几个路段。

登山路上每隔100米就有一个指示牌,每个指示牌标明了当前位置的海拔高度。一段登山路的难度是该段登山路中指示牌记录的最高海拔和最低海拔之差。现旅游开发部有一段登山路中各指示牌上的海拔高度,如下图所示,想要计算出该段登山路的难度。

登山路2.jpg

解决方案

我们将上图的指示牌和高度建表如下:

指示牌序号

0

1

2

3

4

5

海拔高度

3

5

8

10

6

7

这个问题其实就是要求“最大值和最小值之差”。

方案一:蛮力法

既然要求最大值和最小值之差,那么蛮力法的思路就是遍历表格,先找出最小值3,再找出最大值10,最后两数相减就是该段登山路的难度“7”。可是我们发现一共遍历了两遍表格,如果数据一多,这是很浪费时间的。

运用的计算思维

蛮力法运用的是“机械化”的思维方式,“粗暴”却不够快。

方案二:排序预处理

我们知道一组按顺序排列的数,最大值和最小值分别位于第一个和最后一个,那么我们可以先对表格进行排序(排序可以用快速排序方法)。

指示牌序号

0

1

4

5

2

3

海拔高度

3

5

6

7

8

10

这样,我们只需要遍历一次表格就能很快找到最大值和最小值。

运用的计算思维

顺序数组的特点启发我们想到对表格进行排序预处理的方法,加上“快速排序”的支持,有效地解决了问题。相比蛮力法,节省了很多时间。运用了“启发式”的计算思维。

(附:启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法,而不是系统地、以确定的步骤去寻求答案。)

方案三:区间树法

区间树的基本思路是,建立表示给定数组各区间的二叉树。区间树的根结点是整个区间。对本题建立的区间树如下:注意,建立这棵树时,下面的最小值和最大值是没用的,这些值是从叶子节点反推出来的。

登山路3.png

在建立区间树后,我们从叶结点开始求出每个小区间的最大值和最小值,小区间合并成大区间时,只需要分别比较两个小区间的最小值和最大值就能求出大区间的最小值和最大值。

运用的计算思维

我们将区间[0,5]一步步分成多个子区间,先求出子区间的最大值和最小值,通过合并求出大区间的最大值和最小值,最后得到最终答案。这是典型的分治法解决问题的思路。将大问题分解成小问题,对小问题求解后合并成大问题的解答,运用的是“分解”的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015