• 問題說明
• 部分圖解
• 詳細代碼
• 測試結果

問題說明

求解兩個整數（不能是負數）的最大公約數（要求兩個數不能同時為0）

部分圖解

詳細代碼

#include <stdio.h> //求解兩個整數（不能是負數）的最大公約數（要求兩個數不能同時為0）unsigned long GCD_EM(unsigned long a, unsigned long b) //窮舉法_每次減去1效率不高 {if (a == 0) //如果a為0最大公約數為breturn b;else if (b == 0) //如果b為0最大公約數為areturn a;else if (a == b) //如果ab相等則直接返回其中一個return a;unsigned long gcd = a > b ? a : b; //得到ab中較小的數字while (gcd > 1) //讓較小數字不斷減1并且判斷能否能夠被ab整除{if ((a % gcd == 0) && (b % gcd == 0)){return gcd;}gcd--;}return gcd; }unsigned long GCD_SUB(unsigned long a, unsigned long b) //減法 {if (a == 0) //如果a為0最大公約數為breturn b;else if (b == 0) //如果b為0最大公約數為areturn a;else if (a == b) //如果ab相等則直接返回其中一個return a;unsigned long gcd = 0;while (a != b){gcd = a > b?(a -= b) :(b -= a);}return gcd; }//上面的減法在一定效率上提高就變成了除法unsigned long GCD_TAD(unsigned long a, unsigned long b) //歐幾里得輾轉相除法 {if (a == 0) //如果a為0最大公約數為breturn b;else if (b == 0) //如果b為0最大公約數為areturn a;else if (a == b) //如果ab相等則直接返回其中一個return a;unsigned long mod = a % b; while (mod != 0){a = b;b = mod;mod = a % b;}return b;}unsigned long GCD_TAD_REC(unsigned long a, unsigned long b) //歐幾里得輾轉相除法的遞歸實現 {if (a == 0) //如果a為0最大公約數為breturn b;else if (b == 0) //如果b為0最大公約數為areturn a;else if (a == b) //如果ab相等則直接返回其中一個return a;elsereturn GCD_TAD_REC(b, a % b); }int main() {unsigned long a;unsigned long b;printf("a and b cannot be zero the same time!!!\n");printf("input a and b :");do {scanf("%ld %ld", &a, &b);} while (a == 0 && b == 0);//unsigned long result = GCD_EM(a,b); //窮舉測試//unsigned long result = GCD_SUB(a, b); //減法測試// unsigned long result = GCD_TAD(a, b); //歐幾里得輾轉相除法的循環實現測試unsigned long result = GCD_TAD_REC(a, b); //歐幾里得輾轉相除法的遞歸實現測試printf("find %d and %d gcd = %d", a, b, result);return 0; }

測試結果

總結

以上是生活随笔為你收集整理的求解两个非负整数的最大公约数（C语言实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。