[問題] 擴增歐幾里得演算法的遞迴版本

[trippy (哈哈)]

這個程式碼是用原本的歐幾里得演算法改的(為了記錄x和y)
用迴圈來寫我看得懂，可是用遞迴來寫我就有點看不懂了
我不懂的地方是 *x 和 *y 的傳遞為何是這樣?
可以麻煩解釋一下黃色那兩行的意義嗎?

int ex_gcd(int a, int b, int *x, int *y){
    int x1, y1, g;
    if(b>a)
        return ex_gcd(b, a, y, x);
    if(b==0){
         *x = 1;
         *y = 0;
         return a;
     }
     g = ex_gcd(b, a%b, &x1, &y1);
     *x = y1;
     *y = (x1-a/b*y1);
     return g;
}

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.135.199.129
→ yauhh:就是取商數取餘數而已
→ trippy:不懂意思耶...可以解釋的清楚一點嗎?
→ trippy:取誰的商數誰的餘數? 那兩數字不是a和b的係數嗎?
推 LPH66:你把 a%b 代入 a - b * (a/b) 去算一次就知道了
→ LPH66:這就是一樓所說的取商取餘的意思
→ trippy:請問a%b是代入哪一個數? a還是b?
推 LPH66:...我好像講反了  a - b * (a/b) 代入 a%b 才對
→ LPH66:代入的式子是 g = b * x1 + (a%b) * y1
→ LPH66:如果你問這條式子怎麼來的請再看一次程式
→ trippy:謝謝L大的說明! 代入式子後我就了解了!! 卡了兩天終於懂了~
→ yauhh:一個本來是那樣的東西,還要多講清楚真浪費時間, 基本上你知
→ yauhh:知道它是歐氏演算法,數學式拿出來對應就要抓得到線索.
→ trippy:我知道他是歐式演算法，但我就是不了解他的程式為何這樣寫
→ trippy:我知道一定有盲點我沒看出來，L大剛好點出我的盲點
→ trippy:我不像你那麼厲害一看就看出，很抱歉浪費你寶貴的時間
推 LPH66:其實既然你看得懂迴圈版  你可以試著從迴圈版裡抓線索
→ LPH66:我推的這條數學式即使是迴圈版也不會改變
→ LPH66:這才是 yauhh 說「你應該要抓得到線索」的原因
→ trippy:L你誤會了，那條式子我本來就知道，只是卡在我沒有把a%b和
→ trippy:他想在一起，所以沒有做代入的動作去驗證，早上我將之代入
→ trippy:整理過後就找到a和b的關係了! 另外迴圈版本其實沒寫出這式
→ trippy:子! 而且我覺得這好像不是商數餘數的問題，單純是代入求解
→ trippy:將b * x1 和 ( a - b * (a/b) ) * y1整理後得到的關係式
→ trippy:可能是我資質駑鈍無法把這和商數餘數做關聯吧~
推 LPH66:那就是你的數學問題了...a/b 是商  所以餘數就是 a-b*(a/b)
→ LPH66:這個是小學算術的樣子...這也是為什麼一開始是回你取商取餘
→ diabloevagto:被除數＝除數*商+餘數
→ diabloevagto:商＝被除數/除數
→ diabloevagto:被除數＝除數*（被除數/除數）+餘數
→ diabloevagto:餘數=被除數-除數*（被除數/除數）
→ diabloevagto:要取餘數，怎麼不直接用%就好？
→ trippy:商數和餘數怎麼算我很清楚... 我會來問是不懂兩著的關聯性
→ trippy:b * x1 和 ( a - b * (a/b) ) * y1 是推倒出來的，並不是
→ trippy:這並不是誰的商誰的餘阿... 反正懂就好了...我也不知道怎
→ trippy:麼解釋我弄不懂的地方...
→ trippy:diablo! 因為他其實不是要求餘數，他是要a和b的係數
→ diabloevagto:抱歉，可能我搞錯意思了…