【读书笔记】算法漫步 第2章

问题1 量水问题

 

布鲁斯·威利斯主演的电影《虎胆龙威3》中有一个经典的倒水问题情节（58分钟），电影中主角需要用一个 3 加仑的桶和一个 5 加仑的桶，准确装出 4 加仑的水，放到定时器上，否则炸弹会爆炸。

量水问题，是很多脑筋急转弯的题目，还是某些公司的面试题，了解这个问题的求解方法还有点用处的……

 

问题实例：用一个 3 加仑的桶和一个 5 加仑的桶，准确装出 4 加仑的水。

问题：用一个a升的捅，一个b升的桶，要求量出t升的水，是否有可能？如果可能，实施的步骤如何？

计算机算法问题：

问题1

输入：两个不全为零的非负整数a、b

输出：整数d = GCD（a, b）。 //注释GCD是求最大公约数

问题2

输入：两个非负整数a、b，且GCD（a，b） = 1。

输出：两个整数x、y，满足ax + by = 1。

 

【注意，作者在这里，要告诉读者，问题实例，问题，以及算法问题有什么区别，值得学习体会】

 

求解量水问题，需要的数论知识（数学知识）

任给两个正整数a、b，表达式ax + by（x、y为整数）称为a、b的线性组合。这个表达式的最小正值就是a、b的最大公约数。

求解问题1，需要的数学知识

GCD（a，b） = GCD（b，a mod b）//注释 mod 是 求两数相除的余数

求解问题2，需要的数学知识

a mod b = a - ⌊a/b ⌋b  //注释⌊a/b ⌋是a除以b的商的整数部分

 

有了这写数学知识，那么可以知道求解量水问题的算法思路（算法逻辑）：

求解问题1，最有名的算法是欧几里得算法（建议百度，进行扩展学习）

求解问题2, 用扩展欧几里得算法

 

编程实现欧几里得算法，最常见的是递归实现（程序与数据结构）

 

本书对欧几里得算法进行了算法分析（正确性分析，和算法代价分析，这是算法学习的必修课），具体请读书

还留了一个读者练习题，编写算法，给出量水问题求解的操作过程。

 

 

【作者感受】

欧几里得算法基本是每本程序设计语言，数据结构或算法教材必有的例题，因为它是已知的最古老的算法。它是学习递归的经典例题，最重要的、最关键是它是计算最大公约数的最有效的方法。知道求解最大公约数用欧几里得算法，知道用递归实现欧几里得算法是IT人基本知识。