Java求解兩個(gè)非負(fù)整數(shù)最大公約數(shù)算法【循環(huán)法與遞歸法】
本文實(shí)例講述了Java求解兩個(gè)非負(fù)整數(shù)最大公約數(shù)算法。分享給大家供大家參考，具體如下：
代碼功能：
1.Java實(shí)現(xiàn)（完整源碼附測(cè)試用例）；
2.求解兩個(gè)非負(fù)整數(shù)p，q（p>=q)的最大公約數(shù)；
3.循環(huán)法 以及 遞歸法兩種求解思路；
完整源碼：
/* GCD:Greateast Common Divisor */
public class GCD{
public static void main(String args[]){
/* Test Case */
int p = 32;
int q = 24;
System.out.println("The greatest divisior of "+p+" and "+q+" is \n"+
"[ gcd1 ] : "+gcd1(p,q)+"\n"+"[ gcd2 ] : "+ gcd2(p,q));
}
// (q % gcd ==0 AND p% gcd ==0 [gcd from q to 1])
public static int gcd1(int p,int q){
int gcd=1;
int d=q;
while(d>0){
d--;
if(q%d==0 && p%d==0){
gcd = d;
break;
}
}
return gcd;
}
// gcd(p,q)=gcd(q,p%q)[if q=0,gcd=p]
public static int gcd2(int p,int q){
if(q==0) return p;
int r = p%q;
//System.out.println("("+q+","+r+")");
return gcd2(q,r);
}
}
運(yùn)行截圖：
代碼解釋?zhuān)?/strong>
循環(huán)法 gcd1(p,q)
自然語(yǔ)言描述 ：循環(huán)法求解兩個(gè)非負(fù)整數(shù)p，q（p>=q）的最大公約數(shù)，即求解q的公約數(shù)中為p的公約數(shù)的最大值。令d（被除數(shù)）從p開(kāi)始遞減（遞減step = 1）d始終為“即將滿(mǎn)足條件的最大值”，當(dāng)d滿(mǎn)足條件（既可以被p整除又可以被p整除時(shí)），d即p與q的公約數(shù)，d即為p、q的最大公約數(shù)；
遞歸法 gcd2(p,q)
自然語(yǔ)言描述： 遞歸法求解兩個(gè)非負(fù)整數(shù)p，q（p>=q）的最大公約數(shù) ，當(dāng)q等于0時(shí)，最大公約數(shù)為p；否則，對(duì)p、q取余得r=p%q，p、q的最大公約數(shù)即為q、r的最大公約數(shù)；
代碼心得：
關(guān)于循環(huán)法，一開(kāi)始我想到的是，寫(xiě)一個(gè)求解公約數(shù)的方法、用整型數(shù)組存儲(chǔ)一個(gè)非負(fù)整數(shù)的全部公約數(shù)，然后比較找出p、q中共同的那個(gè)最大的公約數(shù)也就是兩個(gè)數(shù)的最大公約數(shù)了，后來(lái)想想，既然是求最大，那么就直接從后往前遞減豈不是更省事兒，從后往前遞減就可以保證這個(gè)數(shù)一直是當(dāng)前最大，因?yàn)楸人蟮募一锒疾环蠗l件（能同時(shí)被p、q整除）被淘汰掉了啦，就免去了最初需要的找最大這個(gè)麻煩，雖然求最大值方法多多，但是如果自己已經(jīng)或者原本就是就不需要去證明和尋找了哈哈，怎么感覺(jué)有點(diǎn)在說(shuō)哲學(xué) ；
關(guān)于遞歸法，我能依靠我的直覺(jué)完全理解的還只有那句p、q的最大公約數(shù)就是q、r（r=p%q）的最大公約數(shù)這個(gè)環(huán)的開(kāi)始，但是還是不太理解環(huán)的結(jié)束條件 q為0，返回p;
雖然是很簡(jiǎn)單的求解最大公約數(shù)算法，但是非要用兩種思路來(lái)寫(xiě)一下，主要還是為了再感受一下我不是很熟悉的遞歸法，以前看求解漢諾塔和斐波那契數(shù)的遞歸算法那明白白的公式亮在那里，就在感慨，這完全就是數(shù)學(xué)??！今天學(xué)習(xí)到的這個(gè)，感觸居然比那時(shí)候還要震撼，不知道發(fā)生了什么問(wèn)題奇妙地就解決了。我到時(shí)沒(méi)太在意什么內(nèi)存啊、效率之類(lèi)的指標(biāo)，只是覺(jué)得能想到這個(gè)的家伙真的太聰明，對(duì)他們而言計(jì)算機(jī)也好、編程語(yǔ)言也好，真正做到了只是解決問(wèn)題的工具。有人說(shuō)，遞歸是讓人腦去思考讓計(jì)算機(jī)去計(jì)算的算法，感覺(jué)真的是很貼切的說(shuō)法呢。
參考資料
圖靈程序設(shè)計(jì)叢書(shū):算法(第4版) 塞奇威克 (Robert Sedgewick) (作者), 韋恩 (Kevin Wayne) (作者), 謝路云 (譯者)
更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。
相關(guān)文章
SpringBoot2.動(dòng)態(tài)@Value的實(shí)現(xiàn)方式
這篇文章主要介紹了SpringBoot2.動(dòng)態(tài)@Value的實(shí)現(xiàn)方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07
SpringBoot中通過(guò)AOP整合日志文件的實(shí)現(xiàn)
本文主要介紹了SpringBoot中通過(guò)AOP整合日志文件的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
Java詳解實(shí)現(xiàn)多線(xiàn)程的四種方式總結(jié)
哈哈！經(jīng)過(guò)一個(gè)階段的學(xué)習(xí)，Java基礎(chǔ)知識(shí)學(xué)習(xí)終于到多線(xiàn)程了！Java多線(xiàn)程以及后面互斥鎖的概念都是Java基礎(chǔ)學(xué)習(xí)的難點(diǎn)，所以我做了一個(gè)總結(jié)，希望對(duì)大家也有幫助2022-07-07
JAVA爬蟲(chóng)實(shí)現(xiàn)自動(dòng)登錄淘寶
給大家分享一個(gè)關(guān)于JAVA爬蟲(chóng)的相關(guān)知識(shí)點(diǎn)，通過(guò)代碼實(shí)現(xiàn)自動(dòng)登錄淘寶網(wǎng)，有興趣的朋友測(cè)試下。2018-04-04
這篇文章主要介紹了java?spring?mvc處理器映射器，文章圍繞equestMapping解析映射介紹展開(kāi)源碼內(nèi)容，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-03-03
這篇文章主要給大家介紹了關(guān)于Java中反射機(jī)制和作用的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
Java各種比較對(duì)象的方式的對(duì)比總結(jié)
比較對(duì)象是面向?qū)ο缶幊陶Z(yǔ)言的一個(gè)基本特征.在本教程中,我們將介紹Java語(yǔ)言的一些特性,這些特性允許我們比較對(duì)象.此外,我們還將研究外部庫(kù)中的這些特性,需要的朋友可以參考下2021-06-06
解析Java的Hibernate框架中的持久化類(lèi)和映射文件
這篇文章主要介紹了Java的Hibernate框架中的持久化類(lèi)和映射文件,Hibernate是Java的SSH三大web開(kāi)發(fā)框架之一,需要的朋友可以參考下2015-12-12
Sentinel核心類(lèi)之Entry類(lèi)解讀
這篇文章主要介紹了Sentinel核心類(lèi)之Entry類(lèi)解讀,Sentinel中Entry可以理解為每次進(jìn)入資源的一個(gè)憑證,如果調(diào)用SphO.entry()或者SphU.entry()能獲取Entry對(duì)象,代表獲取了憑證,沒(méi)有被限流,否則拋出一個(gè)BlockException,需要的朋友可以參考下2023-12-12
Redis使用RedisTemplate模板類(lèi)的常用操作方式
這篇文章主要介紹了Redis使用RedisTemplate模板類(lèi)的常用操作方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09