輾轉相除法求最大公約數理解?首先看 代碼如下，代碼并不難，很多人都會寫，我來為大家講解一下關于輾轉相除法求最大公約數理解?跟着小編一起來看一看吧!
首先看 代碼如下，代碼并不難，很多人都會寫。
public static int f(int a, int b){
while(b != 0){
int temp = b;
b = a % b;
a = temp;
}
return a;
}
舉個例子，例如6，8按照代碼運行一遍。
a b
6 8
8 6
6 2
2 0
但是這個算法的原理可是折磨了我很久，不知道大家懂不懂這個原理
首先 摘自百度百科
兩個數的最大公約數是指能同時整除它們的最大正整數。 設兩數為a、b(a≥b)，求a和b最大公約數 的步驟如下：
(1)用a除以b(a≥b)，得 a / b = q…r1 。 (2)若 r1 = 0 ，則 (a, b) = b； (3)若 r1
不等于 0 ，則再用b除以 r1 ，得b / r1 = q…r2(此處q不是上方的q). (4)若 r2=0 ，則(a,b)=r1
；若 r2不等于0 ，則繼續用r1除以 r2 ，……，如此下去，直到能整除為止。 其最後一個餘數為0的除數即為 (a,b)
的最大公約數。
為什麼這樣進行遞歸除下去我也不懂，知道看到數論吧的以為大神發帖
假設有兩個數x和y，存在一個最大公約數z=(x,y)，即x和y都有公因數z，
那麼x一定能被z整除，y也一定能被z整除，所以x和y的線性組合mx±ny也一定能被z整除。（m和n可取任意整數）
對于輾轉相除法來說，思路就是：若x>y，設x/y=n餘c，則x能表示成x=ny c的形式，将ny移到左邊就是x-ny=c，由于一般形式的mx±ny能被z整除，所以等号左邊的x-ny（作為mx±ny的一個特例）就能被z整除，即x除y的餘數c也能被z整除。
由以上的推理可知 a / b的餘數 也能被 (a,b)的最大公約數整除，因此就将問題轉化為求 其中較小的數和餘數的最大公約數，最終将範圍不斷減小，從而求出答案。
,更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
