接上題：3升、5升的無刻度水杯是否可以倒出正好4升水？
或者問：a升、b升的無刻度水杯是否可以倒出正好c升水？
根據題目的要求，我們只需要判斷是否可行，而不需要給出倒水的步驟。怎麼求倒水的步驟，在介紹BFS（廣度優先搜索）算法的時候再講。
雖然水杯沒有刻度， 但我們總是可以倒入整杯的水 +a，+b，或者倒出整杯的水 -a，-b。 那麼我們可以把問題簡化為一個表達式。
x * a + y * b = c
也就是說，倒入或倒出x次a杯，倒入或倒出y次b杯，是否可以得到c升水。我們要求解的是，是否存在這樣的整數 x， y 使得等式成立。（注意，x,y可以是負數）
比如3升，5升倒出4升，就是求解
x * 3 + y * 5 = 4
是否成立。
顯然， x = -2 , y = 2 時
-2 * 3 + 2 * 5 = 4
所以，3升，5升可以倒出4升。
那麼怎麼判斷，x，y 是否有解呢？
法國數學家艾蒂安·裴蜀已經給出了答案。
裴蜀定理（或貝祖定理，Bézout's identity）
註：通俗簡化的描述
整數a、b和它們的最大公約數c。
一定存在整數x,y，使ax+by=c成立。
若d是c的倍數，顯然也一定存在整數x,y，使得 ax+by=d成立。
3和5的最大公約數是1，所以一定存在 x，y 使得如下等式成立。
x * 3 + y * 5 = 1 * 4
實際上，兩個容量互質的水杯，可以倒出任意容量的水。
雖然聽上去有些不可思議，但的確如此。
比如說13 和 61互質，所以這樣的兩個水杯可以倒出任意容量的水。
所以，求解如下等式，x,y是否有整數解
x * a + y * b = c
就是先算 a，b 的最大公約數，然後判斷 c 是不是 a,b最大公約數的正整數倍。
而數學上，求兩個數的最大公約數，有一個非常古老、著名的算法：歐幾裡得算法。
歐幾裡得算法
歐幾裡得算法是特別有意思的一個算法。因為它
特別古老，可以說是最古老的算法之一。
特別能唬人，直接用歐幾裡得的名字命名。
特別重要和廣泛的應用。擴展歐幾裡得算法是RSA加密算法的基石。如果沒有RSA加密算法，網際網路世界將毫無安全可言，網上交易將不復存在。後面在講字符串的時候會介紹RSA加密算法。
但是它又特別簡單。它有一個通俗的名字：輾轉相除法。
歐幾裡得算法來自於歐幾裡得定理。
歐幾裡得定理：
兩個整數的最大公約數等於其中較小的那個數和兩數相除餘數的最大公約數。
比如說，求465和69的最大公約數。
根據定理 465和69的最大公約數等於69(兩者較小的一個) 和 51(兩者相除餘數)的最大公約數。就如下圖。通過輾轉相除，最後得到465和69的最大公約數是3。
Python實現歐幾裡得算法
輾轉相除法顯然更適合用while循環來做，因為我們事先不清楚需要循環多少次。
m = 465
n = 69
while m % n != 0:
temp = n
n = m % n
m = temp
print(n)
注意temp的作用。
如果沒有temp，寫成下面這樣。
n = m % n
m = n
此時m = n 的那個n已經不是原來那個n啦！
Python中，有一種更簡潔的寫法。
多變量同時賦值。
m = 465
n = 69
while m % n != 0:
n , m = m % n , n
print(n)
n , m = m%n , n
對兩個變量同時賦值，Python總會先完成右邊的計算，再統一進行賦值。
Python最最基本的內容到這裡就介紹完了。
下篇將是小結和精選的幾道階段練習題。
不過完成這些習題，還要補充2個小知識點。
Python的鍵盤輸入
Python提供了 內置函數 input() 從標準輸入讀入一行文本，默認的標準輸入是鍵盤。
如上圖，當執行 a = input() 時，會出現一個輸入框一直等待你的輸入。
用 print(a) 把 a 列印出來，正是你在鍵盤上輸入的內容。
a = input()
print(a)
要注意的是，鍵盤上輸入的內容默認都會當成字符串。
如果你想要的是數字，別忘記通過 int() 函數轉換為數字。
a = input()
b = input()
c = int(a) + int(b)
print(c)
print()的更多用法
print()列印多個變量，多個變量用逗號分隔
print()不換行。 print()函數默認是換行的。如果想讓它不換行，可以通過end 參數。
print()格式化。 如下程序，用%d，%d，%d先佔據了3個位置，然後在%符號後面用括號內的（i,j,i*j）分別對應前面的3個位置。
注意：
%d 表示格式化為整數，會把對應的變量當做整數處理。
常用的還有
%f 格式化為浮點數。
%s 格式化為字符串。
猜數字的遊戲
隨機生成一個0~100之間的數字。
讓別人通過鍵盤輸入數字來猜。如果猜對了，列印「猜對了」。
否則，列印「小了！」 或者 「大了！」
微信公眾號同名