展開全部

自然語(yǔ)言描述

用輾轉(zhuǎn)相除法確定兩個(gè)正整數(shù)e69da5e6ba903231313335323631343130323136353331333339666665 a 和 b(a≥b) 的最大公因數(shù)gcd(a,b)：

當(dāng)a mod b=0 時(shí)gcd(a,b)=b,否則

gcd(a,b) = gcd(b,a mod b)

遞歸或循環(huán)運(yùn)算得出結(jié)果

偽代碼

這個(gè)算法可以用遞歸寫成如下：

function gcd(a,b) {

if b<>0

return gcd(b,a mod b);

else

return a；

}

gcd 簡(jiǎn)易函數(shù)

c語(yǔ)言輾轉(zhuǎn)相除代碼:

int GCD(int a,int b)

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

C++語(yǔ)言實(shí)現(xiàn)

#include

using namespace std;

int a , b , a1 , b2 , l;

int gcd(int x , int y)

{

if(!y)

return x;

else return gcd(y , x%y);

}

int main()

{

std::cout << "請(qǐng)輸入兩個(gè)正整數(shù)，計(jì)算它們的最大公約數(shù)" << endl ;

int a , b , ans;

std::cin >> a >> b;

if(a > b)

ans = gcd(a , b);

else ans = gcd(b , a);

cout << ans;

return 0;

}

C語(yǔ)言實(shí)現(xiàn)

/*題目：輸入兩個(gè)正整數(shù)，求其最大公約數(shù)。*/

#include

unsigned gcd ( unsigned,unsigned ) ;

int main( void )

{

unsigned m,n;

printf("請(qǐng)輸入兩個(gè)正整數(shù)：");

scanf("%u%u",&m,&n);

printf("%u與%u的最大公約數(shù)為：%u\n",m,n,gcd ( m,n ) );

return 0;

}

/* 功能：返回正整數(shù)m和n的最大公約數(shù)*/

unsigned gcd ( unsigned m,unsigned n )

{

unsigned temp;

if (m

{

temp=m;

m=n;

n=temp;

}

if ( m % n == 0)

{

return n;

}

else

{

return gcd ( n,m % n) ;

}

}

/*題目：輸入兩個(gè)非負(fù)整數(shù)u和v，求其最大公約數(shù)。*/

#include 　　main()　　{　　int u,v,r;　　printf("please input u and v:");　　scanf("%d,%d",&u,&v);　　while(v!=0)　　{　　r=u%v;　　u=v;　　v=r;　　}　　printf("%d\n",u);　　}

C#語(yǔ)言實(shí)現(xiàn)

static int sucDivison/*除法*/(int m, int n)　　{　　int remainder = 0;　　if (m % n == 0)　　{　　return n;　　}　　else　　{　　do　　{　　remainder = m % n;　　m = n;　　n = remainder;　　} while (remainder > 0);　　}　　if (n == 0)　　{　　return m;　　}　　return n;　　}

Basic實(shí)現(xiàn)

INPUT m,n

DO

r=m MOD n

m=n

n=r

LOOP UNTIL r=0

PRINT m

END

Pascal實(shí)現(xiàn)

function gcd(a,b:integer):integer;

begin

if b=0 then gcd:=a

else gcd:=gcd (b,a mod b);

end ;

Common Lisp實(shí)現(xiàn)

(defun my-gcd (number-a number-b)

(do ((r (mod number-a number-b) (mod ea eb))(eb number-b r) (ea number-a eb))

((= 0 r) eb)))

Java 實(shí)現(xiàn)

/**

*

* @return int

* @tags @param m

* @tags @param n

* @tags @return

* @todo 【方法二】利用輾除法

*/

public static int gcd(int m, int n) {

while (true) {

if ((m = m % n) == 0)

return n;

if ((n = n % m) == 0)

return m;

}

}

Python實(shí)現(xiàn)

#遞歸解決最大公約數(shù)問題

def gcd(x,y):

if y != 0:

return gcd(y,x%y)

else:

return x

x = int(input('請(qǐng)輸入第一個(gè)數(shù)字：'))

y = int(input('請(qǐng)輸入第二個(gè)數(shù)字：'))

print('%d 和 %d 的最大公約數(shù)為：' %(x,y),gcd(x,y))

數(shù)據(jù)舉例

其中“a mod b”是指取 a ÷ b 的余數(shù)。

例如，123456 和 7890 的最大公因子是 6，這可由下列步驟看出： a b a mod b 123456 7890 5106 7890 5106 2784 5106 2784 2322 2784 2322 462 2322 462 12 462 12 6 12 6 0 時(shí)間復(fù)雜度

輾轉(zhuǎn)相除法的運(yùn)算速度為 O(n)，其中 n 為輸入數(shù)值的位數(shù)。

輾轉(zhuǎn)相除法處理大數(shù)時(shí)非常高效，它需要的步驟不會(huì)超過較小數(shù)的位數(shù)(十進(jìn)制下)的五倍。加百利·拉梅(GabrielLamé)于1844年證明了這點(diǎn)，開創(chuàng)了計(jì)算復(fù)雜性理論。

總結(jié)

以上是生活随笔為你收集整理的python辗转相除法算法_辗转相除法的算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。