淺談 分而治之-歐幾里得演算法
- 一、拋出問題
- 二、歐幾里得演算法及證明
- 一、演算法
- 二、證明
此問題討論來源于《演算法圖解》[美] Aditya Bhargava
一、拋出問題
假設你有一小塊田地，面積是1680*640，你要將這塊地均勻地分成方塊，并且分出地方塊要盡可能大，你該如何分？
首先你可能想到，我直接對半分一下就好了，但是題中是需要分成的是方塊；那你可能想到，我先按方塊來分，然后對剩下不是方塊的部分，我再分成方塊，但是這就違背了均勻的題意，所以，應該如何來分呢？
我們可以使用分而治之的思想來解決問題，首先找出一個條件：一條邊的長度是另一條邊的整數倍，這樣分出的土地正好是方塊，另外一個就是如何把問題逐步分解來滿足這個條件，
-
首先根據長方形最短的邊來分得正方形，但是這會余下一塊土地，如圖，
-
然后對余下的土地重復上述步驟，如圖，
-
最侄訓分成一條邊是另一條邊的倍數，也就達到了第一個條件，所以這塊土地可以分成80*80的最大均勻方塊，
這個問題用到的就是分而治之的思路，同時里面也有遞回的映射，這里就不做討論了，
但是為什么會有這么一種方法呢？它背后的原理是什么呢？如果深究，就請繼續看下面的歐幾里得演算法，
二、歐幾里得演算法及證明
一、演算法
上面問題的解決歸結到數學上，其實就屬于求解兩個數的最大公約數，說到這里可能很多人明白了，讓我們繼續往下看吧，
歐幾里得演算法是求解最大公約數，A和B的最大公約數使用GCD(A,B)（Greatest Common Divisor）表示，它的性質是：
- 如果A=0，GCD(0,B) = B,GCD(A,B) = B;
- 如果B=0，GCD(A,0) = A,GCD(A,B) = A;
- 如果A,B不為0.那么找出A = B*Q + R.得出GCD(A,B) = GCD(B,R)，然后重復此步驟直到滿足性質一或者性質二，也即A=0或B=0;其中Q為整數，R為在0到B-1之間的整數；
使用此演算法來計算上述例子，你就會發現上述例子思想就是歐幾里得演算法，
若你想繼續深究，可以繼續往下閱讀歐幾里得演算法的性質證明，看看它是如何得出上面三個性質的，
二、證明
下面我們來證明歐幾里得演算法如何求得A和B的最大公約數，
首先看前兩條性質，如果B=0，GCD(A,0) = B,GCD(A,B) = A;
- 能整除A的最大整數是A；
- 對于任何整數C，我們寫成 C*0 = 0，我們可以得到任何整數都可以整除0；所以我們可以得出A可以整除0，也可以理解成，A是0的約數，0是A的約數；
- 所以在在0和A中選取最大公約數，那么就是A，所以GCD(A,0) = A;
- 同理用在A=0的情況
下面我們來看第三條性質，我們需要逐步證明，來讓程序看得簡單：
要證明GCD(A,B) = GCD(B,R)，我們先證明GCD(A,B) = GCD(B,A-B)
我們駕駛有三個數A,B,C，其中C=A-B
1、證明：GCD(A,B)整除C
- 通過GCD(A,B)的定義來看，GCD(A,B)可以整除A，所以A一定是GCD(A,B)的倍數，例如 X*GCD(A,B) = A
- 同理B也是GCD(A,B)的倍數Y*GCD(A,B) = B；
- 因為A - B = C,所以
X * GCD(A,B) - Y * GCD(A,B) = C,
(X-Y)GCD(A,B) = C
所以得證GCD(A,B)可以整除C
2、證明：GCD(B,C)可以整除A
- 同上通過定義，GCD(B,C)可以整除B和C，B,C均為GCD(B,C)的倍數，有:
M * GCD(B,C) = B; N * GCD(B,C) = C - 由A-B=C得B+C=A
M * GCD(B,C) + N * GCD(B,C) = A
(M+N) GCD(B.C) = A 所以得證
3、證明：GCD(A,B)=GCD(A,A-B)
- GCD(A,B)可以整除B，上述已證明也可以整除C，所以得出GCD(A,B)是B和C的公約數（不一定是最大公約數）
- 所以GCD(A,B)一定是小于等于B和C的最大公約數，也即GCD(A,B)小于等于GCD(B,C)
- 同理，GCD(B,C)可以整除B和A，所以是B和A的公約數，所以有GCD(B,C)小于等于GCD(A,B)
- 所以得出GCD(A,B) = GCD(B,C)，也即GCD(A,B) = GCD(B,C) = GCD(B,A-B)
上述三個證明課=可歸納為此圖：
4、最后證明：GCD(A,B) = GCD(B,R)
- GCD(A,B) = GCD(B,A-B),其中括號內可以互換順序，GCD(A,B) = GCD(A-B,B)
- 由前面證明1和2可知：
GCD(A,B)=GCD(A-B,B)=GCD(A-2B,B)=GCD(A-3B,B)=…=GCD(A-Q?B,B) - 因為A = B * Q + R,所以R = A-Q * B
- 所以得證GCD(A,B) = GCD(B,R)
證畢
人在學習的時候，總會聽自己想聽的內容，從而會忽略一些重要知識，所以溫故知新，建議收藏，
參考網站：https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/267499.html
標籤：其他
下一篇：K8S基礎