c語言中的輾轉相除法,c語言輾轉相除法代碼

本文目錄一覽：

• 1、C語言輾轉相除法
• 2、C語言輾轉相除法問題
• 3、c語言編程,利用輾轉相除法求公約數
• 4、c語言輾轉相除法
• 5、c語言中，用輾轉相除法計算兩個數的最大公約數的具體方法是怎樣的？
• 6、輾轉相除法c語言代碼

C語言輾轉相除法

例如用輾轉相除法求a b 最大公約數（a b誰大誰小無所謂）：

int GCD( int a , int b )

{

int n=a%b;

whie(n != 0) //即： while(n)

{

a = b;

b = n;

n = a % b;

}

return b; //注意這裡返回的是b 不是n

}

C語言輾轉相除法問題

#include stdio.h

int fun(int a,int b) /* 2個數的公約數 */

{

int t;

while(b)

{

t = a%b;

a = b;

b = t;

}

return a;

}

int main()

{

int a[100];

int n;

int i;

int res;

scanf(“%d”,n); /* 先輸入數的總數n */

if(n 2)

{

printf(“n不能小於2\n”);

return 0;

}

for(i=0;in;i++) /* 輸入n個數  */

scanf(“%d”,a[i]);

res = fun(a[0],a[1]);

for(i=2;in;i++)

res = fun(res,a[i]);

printf(“%d\n”,res);

return 0;

}

歐幾里德演算法又稱輾轉相除法，用於計算兩個正整數a，b的最大公約數。

其計算原理依賴於下面的定理：

定理：gcd(a,b) = gcd(b,a mod b) (ab 且a mod b 不為0)

證明：a可以表示成a = kb + r，則r = a mod b

輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的：

⒈ 若 r 是 a ÷ b 的餘數，且r不為0， 則

gcd(a,b) = gcd(b,r)

⒉ a 和其倍數之最大公因子為 a。

另一種寫法是：

⒈ 令r為a/b所得餘數（0≤r

若 r= 0，演算法結束；b 即為答案。

⒉ 互換：置 a←b，b←r，並返回第一步。

c語言編程,利用輾轉相除法求公約數

輾轉相除法， 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。

其原理如下：

設兩數為a、b(ba)，用gcd(a,b)表示a，b的最大公約數，r=a (mod b) 為a除以b以後的餘數，k為a除以b的商，即a÷b=k…….r。輾轉相除法即是要證明gcd(a,b)=gcd(b,r）。

第一步：令c=gcd(a,b），則設a=mc，b=nc

第二步：根據前提可知r =a-kb=mc-knc=(m-kn)c

第三步：根據第二步結果可知c也是r的因數

第四步：可以斷定m-kn與n互質【否則，可設m-kn=xd，n=yd (d1)，則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)dc，b=nc=ycd，故a與b最大公約數成為cd，而非c，與前面結論矛盾】

從而可知gcd(b,r)=c，繼而gcd(a,b)=gcd(b,r)。

證畢。

以上步驟的操作是建立在剛開始時r!=0的基礎之上的。即m與n亦互質。

按照其規則，C語言實現如下：

int GCD(int a,int b)

{return b==0？a:GCD(b,a%b)；}

c語言輾轉相除法

按照你的改了一下

#include stdio.h

int gcd(int x,int y)

{

int i;

int max,min;

(xy)?(max=x,min=y):(max=y,min=x);

if(i=max%min!=0)

do{

i=min;

            min=max%min;

max=i;

}while(min!=0);

return max;

}

int main()

{

int a,b;

scanf(“%d%d”,a,b);

printf(“%d\n”,gcd(a,b));

return 0;

}

再給你一個精簡版，二者實質是一樣的

#include stdio.h

int gcd(int x,int y)

{

if(y==0) return x;

return gcd(y,x%y);

}

int main()

{

int a,b;

scanf(“%d%d”,a,b);

printf(“%d\n”,gcd(a,b));

return 0;

}

c語言中，用輾轉相除法計算兩個數的最大公約數的具體方法是怎樣的？

#include stdio.h

int gcd(int a, int b) {

int r;

do {

r = a % b;

a = b;

b = r;

} while (r);

return a;

}

int main(void) {

int a, b;

printf(“Input two integers: \n”);

scanf(“%d%d”, a, b);

printf(“The greatest common divisor is: %d\n”, gcd(a, b));

return 0;

}

原理：

輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的：

1. 若 r 是 a ÷ b 的餘數，則

gcd(a,b) = gcd(b,r)

2. a 和其倍數之最大公因子為 a。

另一種寫法是：

1. a ÷ b，令r為所得餘數（0≤rb）

若 r = 0，演算法結束；b 即為答案。

2. 互換：置 a←b，b←r，並返回第一步

輾轉相除法c語言代碼

輾轉相除法用來求兩個數的最大公約數，代碼如下：

#include stdio.h

#include stdlib.h

int main()

{

int a, b,r;

scanf(“%d %d”, a, b);

while(b!=0)//當其中一個數為0，另一個數就是兩數的最大公約數

{

r = a%b;

a = b;

b = r;

}

printf(“Greatest Common Divisor: %d\n”, a);

system(“pause”);

}

運行結果：