問題1 量水問題

?

布魯斯·威利斯主演的電影《虎膽龍威3》中有一個(gè)經(jīng)典的倒水問題情節(jié)（58分鐘），電影中主角需要用一個(gè) 3 加侖的桶和一個(gè) 5 加侖的桶，準(zhǔn)確裝出 4 加侖的水，放到定時(shí)器上，否則炸彈會(huì)爆炸。

量水問題，是很多腦筋急轉(zhuǎn)彎的題目，還是某些公司的面試題，了解這個(gè)問題的求解方法還有點(diǎn)用處的……

?

問題實(shí)例：用一個(gè) 3 加侖的桶和一個(gè) 5 加侖的桶，準(zhǔn)確裝出 4 加侖的水。

問題：用一個(gè)a升的捅，一個(gè)b升的桶，要求量出t升的水，是否有可能？如果可能，實(shí)施的步驟如何？

計(jì)算機(jī)算法問題：

問題1

輸入：兩個(gè)不全為零的非負(fù)整數(shù)a、b

輸出：整數(shù)d = GCD（a, b）。 //注釋GCD是求最大公約數(shù)

問題2

輸入：兩個(gè)非負(fù)整數(shù)a、b，且GCD（a，b） = 1。

輸出：兩個(gè)整數(shù)x、y，滿足ax + by = 1。

?

【注意，作者在這里，要告訴讀者，問題實(shí)例，問題，以及算法問題有什么區(qū)別，值得學(xué)習(xí)體會(huì)】

?

求解量水問題，需要的數(shù)論知識(shí)（數(shù)學(xué)知識(shí)）

任給兩個(gè)正整數(shù)a、b，表達(dá)式ax + by（x、y為整數(shù)）稱為a、b的線性組合。這個(gè)表達(dá)式的最小正值就是a、b的最大公約數(shù)。

求解問題1，需要的數(shù)學(xué)知識(shí)

GCD（a，b） = GCD（b，a mod b）//注釋 mod 是 求兩數(shù)相除的余數(shù)

求解問題2，需要的數(shù)學(xué)知識(shí)

a mod b = a - ?a/b ?b ?//注釋?a/b ?是a除以b的商的整數(shù)部分

?

有了這寫數(shù)學(xué)知識(shí)，那么可以知道求解量水問題的算法思路（算法邏輯）：

求解問題1，最有名的算法是歐幾里得算法（建議百度，進(jìn)行擴(kuò)展學(xué)習(xí)）

求解問題2, 用擴(kuò)展歐幾里得算法

?

編程實(shí)現(xiàn)歐幾里得算法，最常見的是遞歸實(shí)現(xiàn)（程序與數(shù)據(jù)結(jié)構(gòu)）

?

本書對(duì)歐幾里得算法進(jìn)行了算法分析（正確性分析，和算法代價(jià)分析，這是算法學(xué)習(xí)的必修課），具體請(qǐng)讀書

還留了一個(gè)讀者練習(xí)題，編寫算法，給出量水問題求解的操作過程。

?

?

【作者感受】

歐幾里得算法基本是每本程序設(shè)計(jì)語言，數(shù)據(jù)結(jié)構(gòu)或算法教材必有的例題，因?yàn)樗且阎淖罟爬系乃惴?。它是學(xué)習(xí)遞歸的經(jīng)典例題，最重要的、最關(guān)鍵是它是計(jì)算最大公約數(shù)的最有效的方法。知道求解最大公約數(shù)用歐幾里得算法，知道用遞歸實(shí)現(xiàn)歐幾里得算法是IT人基本知識(shí)。