一道課本例題的研究

一、課本例題的再研究

案例：寫出求兩個正整數ａ，ｂ（a ＞ b）的最大公約數的一個算法.

這是蘇教版高中數學必修３第２６頁上的一道案例，其算法的設計思想是利用歐幾里得輾轉相除法，找出ａ，ｂ的最大公約數. 具體算法步驟是：計算出ａ ｂ的余數ｒ，若ｒ ＝ ０，則為的最大公約數；若ｒ≠０，則把前面的除數作為新的被除數，把余數作為新的除數，繼續運算，直到余數為０，此時的除數即為正整數的最大公約數.

偽代碼如圖１：

我們知道同一問題如果考慮的角度不同，那么算法的設計思想可能不同，于是又可以有下面的算法設計：

算法１ 由于兩個正整數ａ，ｂ（a ＞ b）的最大公約數必小于等于ｂ，可以利用循環思想讓變量從１開始檢索到ｂ，直到能同時滿足能被ａ，ｂ整除的最大的那一個數為止.

算法２ 仿上，讓變量從ｂ開始檢索到第一個滿足同時能被ａ，ｂ整除的數即為ａ，ｂ的最大公約數. 偽代碼如圖３：

二、課本例題的拓展研究

拓展１ 寫出求三個正整數ａ，ｂ，ｃ（a ＞ b ＞ c）的最大公約數的一個算法.

算法１ 先用歐幾里得輾轉相除法找出ａ，ｂ的最大公約數，然后再用輾轉相除法求出剛才求出的最大公約數與ｃ的最大公約數.

偽代碼如圖４：

算法２ 由于三個正整數ａ，ｂ，ｃ（a＞b＞c）的最大公約數必小于等于ｃ，可以利用循環思想讓變量從１開始檢索到ｃ，直到能同時滿足能被ａ，ｂ整除的最大的那一個數為止.

偽代碼如圖５：

算法３ 仿上，讓變量從ｃ開始檢索到第一個滿足同時能被ａ，ｂ，ｃ整除的數即為ａ，ｂ，ｃ的最大公約數.

偽代碼如圖６：

點評 從實際效果來看，第二種算法比第一種算法更實用，更易理解一些. 同時仿上，我們可以寫出求個正整數ｎ的最大公約數的算法.

拓展２ 設計計算兩個正整數ａ，ｂ的最小公倍數的一個算法.

算法１ 求出ａ，ｂ的最大公約數，然后用ａ，ｂ之積除以ａ，ｂ的最大公約數，

偽代碼如圖７：

算法２ 由于兩個正整數ａ，ｂ的最小公倍數必小于等于ａｂ，可以利用循環思想讓變量從ａｂ開始檢索到１，直到能同時滿足整除ａ，ｂ的最小的那一個數為止.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”