c語言使用遞歸法求最大公約數?利用歐拉的輾轉相除法來求最大公約數可以很好地理解變量的叠代關系而對照一下遞歸算法，可以更好地理解兩個遞歸函數之間參數的叠代關系：，下面我們就來聊聊關于c語言使用遞歸法求最大公約數?接下來我們就一起去了解一下吧!

c語言使用遞歸法求最大公約數

利用歐拉的輾轉相除法來求最大公約數可以很好地理解變量的叠代關系。而對照一下遞歸算法，可以更好地理解兩個遞歸函數之間參數的叠代關系：

int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); //return b?gcd(b,a%b):a; } int gcd2(int a, int b) { while(b != 0) { int t = a % b; a = b; b = t; } return a; }

相對于非遞歸函數的寫法，為什麼遞歸函數不需要使用一個臨時變量？是因為遞歸函數的參數值位于各自的棧幀。參數傳值時沒有彼此的耦合關系。

《九章算術》中的輾轉相減法：

int gcd3(int a, int b) // 《九章》中的輾轉相減法 { int t = a; a = a>b?a:b; b = t<b?t:b; while(b != 0) { t = a - b; a = t>b?t:b; b = t<b?t:b; } return a; }

對照一下：

最大公約數也可以返回b，但要在b=0前提示返回，終止條件就是a%b!=0。

ibt gcd(int a, int b) { int r; if (a<b){r=a;a=b;b=r;} while(r=a%b) // 求a，b的最大公約數 { a=b; b=r; } return b; }

下面我們對上面的過程進行一個表形象地講解，實際上這也是教材裡面的講解方式，我隻是照搬過來，增加一下自己的理解罷了。我們來通過一個例子來講解：

假如我們有一塊 1680 米 * 640 米 的土地，我們希望将其分成若幹正方形的土地，且我們想讓正方形土地的邊長盡可能大，我們應該如何設計算法呢？

實際上這正是一個最大公約數的應用場景，我們的目标就是求解 1680 和 640 的最大公約數。

将 1680 米 * 640 米 的土地分割，相當于對将 400 米 * 640 米 的土地進行分割。 為什麼呢？ 假如 400 米 * 640 米分割的正方形邊長為 x，那麼有 640 % x == 0，那麼肯定也滿足剩下的兩塊 640 米 * 640 米的。

我們不斷進行上面的分割：

直到邊長為 80，沒有必要進行下去了。

－End－

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!