有兩個自然數a和b,如果a能被b整除,那麼,b就叫做a的約數。
兩個或多個自然數的共有約數中最大的一個,叫做它們的最大公約數,也稱最大公因數、最大公因數。
求最大公約數有多種方法,常見的有質因數分解法、短除法、輾轉相除法、輾轉相減法、更相減損法等。
【問題】
輸入兩個正整數x和y,求它們的最大公約數。
【編程解題】
下面我們使用輾轉相除法求出兩個數的最大公約數。
輾轉相除法
輾轉相除法的算法步驟:給定兩個正整數x、y(x>y),用x除以y等到餘數z。如果餘數z不為0就将y和z構成新的一組數(x=y,y=z),繼續上的除法操作,直到餘數z為0,這時y就是原來兩個正整數的最大公約數。
由于這個算法需要反複執行除法運算,所以被形象地命名為“輾轉相除法”。
舉例說明,用輾轉相除法求255,75的最大公約數。
給定兩個數:255,75
第一次:用255除以75,餘數30;
第二次:用75除以30,餘數15;
第三次:用30除以15,餘數0;
這個時候我們得出255和75的最大公約數是15.
Scratch編程實現算法:
根據上面的算法步驟,我們編寫一個名為“輾轉相除法”的模塊,用來求兩個數的最大公約數。該模塊的完成代碼如下:
下面編寫調用“輾轉相除法”模塊的主程序,用來求255和75的最大公約數。主程序代碼如下:
點擊小綠旗運行程序,求得255和75的最大公約數是15。