C語言求兩個正整數的最大公約數示例代碼
前言
兩個正整數的最大公約數(Greatest Common Divisor, GCD)是能夠整除這兩個整數的最大整數。兩個正整數的最大公約數的求法有多種解答,本文就三種方法做詳細介紹:窮舉法、歐幾裡得算法(輾轉相除法)、遞歸方法。
我們從一道問題來引入:編寫計算最大公約數的函數Gcd(),在主函數中調用該函數計算並輸出從鍵盤任意輸入的最大公約數。
1.窮舉法
根據最大公約數的定義,我們可以采用一種最簡單的方法——窮舉法來編寫代碼。由於a和b的最大公約數不可能比a和b中的較小者還大,否則一定不能整除它,因此,先找到a和b中的較小者t,然後從t開始逐次減1嘗試每種可能,即檢驗t到1之間的所有整數,第一個滿足公約數條件的t,就是a和b的最大公約數。據此我們可編寫函數Gcd()如下:
//函數功能:計算a和b的最大公約數,輸入負數時返回-1 int Gcd(int a, int b) { int i, t; if (a <=0 || b <= 0) return -1; t = a < b ? a : b; for (i=t; i>0; i--) { if (a%i==0 && b%i==0) return i; } return 1; }
這種方法簡單暴力,思維量小,但效率較低,且當兩個正整數都較大,且最大公約數為1時,循環的次數為較小數的值,可想而知所需時間會很長。
2.歐幾裡得算法(輾轉相除法)
下面介紹一種求最大公約數較常用的辦法:歐幾裡得算法(輾轉相除法)。
忽略數學原理,我們有如下算法:對正整數a和b,連續進行求餘運算,直到餘數為0為止,此時非0的除數就是最大公約數。設 r=a mod b 表示a除以b的餘數,若 r≠0 ,則將b作為新的a,r作為新的b,重復 a mod b 運算,直到 r=0 為止,此時b為所求的最大公約數。例如,50和15的最大公約數的求解過程可表示為:Gcd(50, 15)=Gcd(15, 5)=Gcd(5, 0)=5。
用這種算法可編寫函數Gcd()如下:
//函數功能:計算a和b的最大公約數,輸入負數時返回-1 int Gcd(int a, int b) { int r; if (a <= 0 || b <= 0) return -1; do{ r = a % b; a = b; b = r; } while (r != 0); return a; }
我們也可以考慮使用遞歸實現如下:
//函數功能:計算a和b的最大公約數,輸入負數時返回-1 int Gcd(int a, int b) { if (a <= 0 || b <= 0) return -1; if (a % b == 0) return b; else return Gcd(b, a % b); }
3.遞歸方法
對於最大公約數,還有3條性質:
性質1 如果 a>b,則a和b與a-b和b的最大公約數相同;
性質2 如果 b>a,則a和b與a和b-a的最大公約數相同;
性質3 如果 a=b,則a和b的最大公約數與a值和b值相同。
對正整數a和b,當 a>b 時,若a中含有與b相同的公約數,則a中去掉b後剩餘的部分a-b中也應含有與b相同的公約數,對a-b和b計算公約數就相當於對a和b計算公約數。反復使用最大公約數的3條性質,直到a和b相等為止,這時,a或b就是它們的最大公約數。
這就是所謂的第三種方法:遞歸方法。雖然此法被稱為遞歸方法,但隻是思想方法運用瞭遞歸的方法,並不代表隻能使用遞歸實現。我們同樣可以通過非遞歸和遞歸兩種手段編寫函數Gcd()。非遞歸實現如下:
//函數功能:計算a和b的最大公約數,輸入負數時返回-1 int Gcd(int a, int b) { if (a <= 0 || b <= 0) return -1; while (a != b) { if (a > b) a = a - b; else if (b > a) b = b - a; } return a; }
編寫遞歸函數如下:
//函數功能:計算a和b的最大公約數,輸入負數時返回-1 int Gcd(int a, int b) { if (a <= 0 || b <= 0) return -1; if (a == b) return a; else if (a > b) return Gcd(a-b, b); else return Gcd(a, b-a); }
以上就是三種計算最大公約數的算法,可使用如下主函數來調用函數Gcd(),計算最大公約數:
#include <stdio.h> int Gcd(int a, int b); int main(void) { int a, b, c; printf("Input a,b:"); scanf("%d,%d", &a, &b); c = Gcd(a,b); if (c != -1) printf("Greatest Common Divisor of %d and %d is %d\n", a, b, c); else printf("Input number should be positive!\n"); return 0; }
求兩個正整數的最大公約數的過程,實質上是使用最大公約數的定義及性質求解的過程,對此感興趣的夥伴們可以自己研究相關數學原理與證明。
附:相減法
這種方法比較易於理解,原理是先判斷兩個正整數大小,並將較大數與較小數的差值賦給較大數,循環此步驟直到兩數相等,此時得出最大公約數。
代碼如下:
#include<stdio.h> int main() { int m,n; printf("請輸入兩個正整數:"); scanf("%d %d",&m,&n); printf("%d%和%d的最大公約數是",m,n); while(m!=n) { if(m>n) { m=m-n; }else { n=n-m; } } printf("%d",n); return 0; }
參考文獻:
蘇小紅 王甜甜 趙玲玲 范江波 車萬翔 等編著 王宇穎 主審,C語言程序設計學習指導(第4版),高等教育出版社,P57-60.
總結
到此這篇關於C語言求兩個正整數的最大公約數的文章就介紹到這瞭,更多相關C語言兩正整數最大公約數內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!