@Author：Runsen

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題代碼化。 ---- Runsen

先問你們一個小學(xué)問題：如何求兩個整數(shù)的最大公約數(shù)？

曾經(jīng)見過不少的算法題，發(fā)現(xiàn)有的并不在數(shù)據(jù)結(jié)構(gòu)和算法大綱中，而是來源于高中數(shù)學(xué)。

高中數(shù)學(xué)在必修三中，有一個非常重要的知識點(diǎn)，叫做碾轉(zhuǎn)相除法、更相減損術(shù)。

輾轉(zhuǎn)相除法， 又名歐幾里德算法（Euclidean algorithm）乃求兩個正整數(shù)之最大公因子的算法。它是已知最古老的算法， 其可追溯至公元前300年前。

在古代，有一個比較出名的數(shù)學(xué)家，叫做劉徽。而更相減損術(shù)是我國數(shù)學(xué)家劉徽的專著《九章算術(shù)》中記載的．

文章目錄

• 碾轉(zhuǎn)相除法
• 更相減損術(shù)

碾轉(zhuǎn)相除法

輾轉(zhuǎn)相除是求最大公約數(shù)的一種算法。給兩個數(shù),我們可以把它組成數(shù)對(a,b)

輾轉(zhuǎn)相除法基于如下原理：兩個整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)的相除余數(shù)的最大公約數(shù)。

求a和b的最大公約數(shù)，就用ab中較小的數(shù)去除另一

總結(jié)

以上是生活随笔為你收集整理的五十六、从高中碾转相除法、更相减损术算法谈起的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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