首先介紹一下輾轉(zhuǎn)相除法：
即m 和 n求最大公因數(shù)（假設(shè)m大于n），先用 m 除以 n ，如果余數(shù) r 為 0 ，則 n 就是最大公因數(shù)，否則，將 n 給了 m ，將 r 給了 n ，再用 m 除以 n ，如果余數(shù) r 為 0 ，則n為最大公因數(shù)，否則重復(fù)執(zhí)行上述操作，直至 r 為 0 ，此時(shí)的 n 就是 m 和 n 的最大公因數(shù)。
相信很多人包括我在內(nèi)都對(duì)這個(gè)算法不理解，我今天突然有了些想法，分享給大家。
我覺的輾轉(zhuǎn)相除法就是一個(gè)分塊的思想，為什么這么說呢，我們通過一個(gè)例子來說明：
假設(shè) m = 72 ，n = 48
先用 m 除以 n ，如果直接余數(shù) r 為0，那最大公因數(shù)自然就是 n 了，這個(gè)大家都能理解，問題是72/48余數(shù)為24，這時(shí)候，我們自然可以將72分塊，寫成：
72 = 48+24
這個(gè)時(shí)候，72 和 48 的最大公因數(shù)就可以寫成：
48+24 和 48
的最大公因數(shù)
這下是不是看起來有感覺了？
求最大公因數(shù)的中心思想就是找出兩個(gè)數(shù)公有的最大的最大的那一塊，那么我們就要對(duì)這兩個(gè)數(shù)進(jìn)行分塊，分成一塊一塊的，其方法就是用大的數(shù)除以小的數(shù)。
48+24 和 48的最大公因數(shù)就是48+24 和 48 的最大公有的那一塊，因?yàn)樽筮叺?48 和右邊的 48 相等，所以再看看從48中能否分出余數(shù) 24 那么大的“塊”，于是用 48 除以24 分塊，此時(shí)余數(shù)正好為0，分塊結(jié)束，此時(shí)的“塊”即是最大的公有“塊”，那么次“塊”就是最大的公因數(shù)。如果余數(shù)不為0，說明分塊還沒完成，需要繼續(xù)往小了分。
24+24+24 和24+24
上式即是最終的分塊結(jié)果。
有點(diǎn)啰嗦了，希望能幫到大家！

總結(jié)

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

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