用java編寫(xiě)一個(gè)程序段，輸入兩個(gè)正整數(shù)m和n，求其最大公約數(shù)和最小公倍數(shù)？遞歸分治法口訣？1.1遞歸自上而下分析，然后回溯：從n->的情況下到1（特殊情況）->，然后反算->，最后得到n

用java編寫(xiě)一個(gè)程序段，輸入兩個(gè)正整數(shù)m和n，求其最大公約數(shù)和最小公倍數(shù)？

遞歸分治法口訣？

1.1遞歸

自上而下分析，然后回溯：從n->的情況下到1（特殊情況）->，然后反算->，最后得到n的情況

必須滿足以下要求：

每次你叫自己，在某種意義上你必須更接近解（每一次運(yùn)算都是收斂的）：?jiǎn)栴}的規(guī)模越來(lái)越小

必須有一個(gè)終止處理或計(jì)算的準(zhǔn)則必須有一個(gè)退出

1.2分治法

用分治法來(lái)解決子問(wèn)題，子問(wèn)題的類(lèi)型往往與原問(wèn)題相同，所以自然采用遞歸解法

自然語(yǔ)言描述計(jì)算兩個(gè)非負(fù)整數(shù)P和Q的最大公約數(shù)：如果Q為0，則最大公約數(shù)為P。否則，將P除以Q得到余數(shù)R。P和Q的最大公約數(shù)是Q和R的最大公約數(shù)。Java代碼公約數(shù)

public static int GCD（int P，int Q）{如果（Q==0）返回P int R=P%Q返回GCD（Q，R）}]公倍數(shù)是兩個(gè)數(shù)除以最大公約數(shù)的乘積。公共靜態(tài)int g（int p，int q）{返回p*q/gcd（q，r）}