資源簡介

(共43張PPT)
第8章 數學算法
分解質因數
最大公約數與最小公倍數
數字全排列
楊輝三角
進制轉換
尼科徹斯定理
分數計算器
勾股數組
分解質因數
最大公約數與最小公倍數
數字全排列
8.2
8.3
8.1
點擊查看本小節知識架構
點擊查看本小節知識架構
點擊查看本小節知識架構
楊輝三角
8.4
點擊查看本小節知識架構
進制轉換
尼科徹斯定理
分數計算器
8.6
8.7
8.5
點擊查看本小節知識架構
點擊查看本小節知識架構
點擊查看本小節知識架構
勾股數組
8.8
點擊查看本小節知識架構
學習目標
理解
掌握
掌握
理解各種數學算法的設計思想
1
2
掌握各種經典算法的操作原理
3
掌握算法的代碼編寫方法
本章將主要介紹一些數學算法的實例。學習數學算法有助于提升 C 語言程序設計能力。本章將選取一些常見的涉及數學領域的算法進行分析，并且通過代碼展示編程技巧，望讀者理解算法的設計思想，熟練編寫操作代碼。
8.1 分解質因數
8.1.1
算法概述
返回目錄
8.1.2
算法實現
8.1.1 算法概述
分解質因數指的是把一個合數用質因數相乘的形式表示出來。換句話說，每個合數都可以寫成幾個質數相乘的形式，其中每個質數都是這個合數的因數，例如，20=2×2×5。
分解質因數只針對合數進行分解，如果被分解的數為質數則分解無效。具體的分解思路為：假設一個被分解的合數為 n，則需要在 2～n－1 的范圍內（1 既不是質數也不是合數）順序查找 n 的因數，第一個找到的因數 i 一定是 n 的質因數；接下來繼續對 n/i 以相同的方式分解質因數，直到 n/i 為質數為止。因此，分解質因數可以采用遞歸的思想解決。
代碼實現的具體步驟如下。
（1）i 初始為 2，判斷 n%i==0 是否成立。
（2）如果成立，說明 i 是質因數，輸出 i。
（3）判斷 n/i 是否為質數，如果為質數則輸出 n/i。
（4）如果 n/i 不是質數，則繼續進行分解，重復步驟（1）～（3），直到 n/i 為質數，則本輪遞歸結束。
（5）如果 n%i==0 不成立，則執行 i++，繼續判斷，直到 i=n－1，分解質因數結束。
8.1.2 算法實現
在分解質因數的過程中，需要多次判斷一個數是否為質數，判斷一個數是否為質數的代碼如下。
由以上代碼可知，判斷一個數是否為質數，只需要判斷這個數是否能被大于 1 且小于本身的數整除，如果不能則說明該數為質數。
采用遞歸的思想分解質因數，具體代碼參考教材8.1.2節。
8.1.2 算法實現
例中，factorization()函數通過調用自身實現遞歸，通過遞歸操作，按順序得到一個合數所有的質因數。程序的運行結果如下所示。
由運行結果可知，輸入的合數 30 可以由質數 2、3、5 相乘得出。
8.2 最大公約數與最小公倍數
8.2.1
算法概述
返回目錄
8.2.2
算法實現
8.2.1 算法概述
最大公約數指的是兩個數的公共因數中最大的數。例如，12 與 6 的最大公約數為 6。最小公倍
數指的是兩個數的公共倍數中最小的數。例如，2 與 3 的最小公倍數為 6。
計算最大公約數的思路為：假設存在兩個數 m 與 n，則選取這兩個數中較小的數（設為 i），然
后判斷 i 能否同時成為 m 與 n 的因數，如果可以，則 i 就是 m 與 n 的最大公約數；如果不可以，則遞減 i，直到滿足條件為止。
計算最小公倍數的思路為：假設存在兩個數 m 與 n，則選取這兩個數中較大的數（設為 j），然
后判斷 j 能否同時被 m 與 n 整除（即取余等于 0），如果可以，則 j 就是 m 與 n 的最小公倍數；如果
不可以，則遞增 j，直到滿足條件為止。
8.2.2 算法實現
計算最大公約數與最小公倍數的具體代碼參考教材8.2.2節。
程序運行結果如下所示。
由運行結果可以看出，當輸入數字 12 與 16 時，計算得出二者的最大公約數為 4，最小公倍數為
48。
8.3 數字全排列
8.3.1
算法概述
返回目錄
8.3.2
算法實現
8.3.1 算法概述
數字全排列即根據一組數字，得到該數列的所有排列方式。例如，輸入數字 1、2、3，則該數列的排列方式有 6 種，即 1、2、3，1、3、2，2、1、3，2、3、1，3、1、2，3、2、1。
設計程序實現輸入數字序列的元素個數 n，并輸入 n 個元素，最終顯示這 n 個數字的所有排列方式。全排列中的每一個數字都不重復，可以考慮采用遞歸的思想解決這一問題。
以輸入數字 1、2、3 為例，計算全部排列方式的步驟如下。
（1）選定 1，排列 2、3。
（2）選定 2，排列 3。
（3）輸出排列 1、2、3。
（4）跳轉到步驟（2），選定 3。
（5）輸出排列 1、3、2。
8.3.1 算法概述
（6）跳轉到步驟（1），選定 2。
（7）重復步驟（2）～（6），得到排列 2、1、3 與 2、3、1。
（8）跳轉到步驟（1），選定 3。
（9）重復步驟（2）～（6），得到排列 3、1、2 與 3、2、1。
8.3.2 算法實現
采用遞歸的思想實現數字全排列，示例代碼參考教材8.3.2節。
例 中，Arrange()函數通過調用自身實現遞歸操作，函數操作的核心為從前向后依次固定數列中的數字，然后在回溯時，從后向前對數列中的數字進行交換，得到新的序列。程序運行結果如下所示。
由運行結果可知，輸入數列元素的個數為 3，元素為 6、7、8，總共輸出 6 種排列方式。
8.4 楊輝三角
8.4.1
算法概述
返回目錄
8.4.2
算法實現
8.4.1 算法概述
楊輝三角又可以稱為帕斯卡三角，是二項式系數在三角形中的一種幾何排列。本節將設計程序實現根據輸入的行數，輸出金字塔形的楊輝三角，如圖所示。
由圖可以看出楊輝三角具有以下一些特殊的性質。
（1）每行數字左右對稱，從 1 開始，從左至右，依次增大再減小到 1。
（2）第 n 行的數字個數為 n。
（3）每個數字等于上一行的左右兩個數字之和。
8.4.2 算法實現
根據輸入行數輸出楊輝三角，具體代碼如例所示。
8.4.2 算法實現
8.4.2 算法概述
例中，num()函數通過調用自身實現遞歸操作，遞歸的目的是得到某一具體位置上的數字。程序運行結果如下所示。
對比運行結果與圖可知，程序輸出正確。
8.5 進制轉換
8.5.1
算法概述
返回目錄
8.5.2
算法實現
8.5.1 算法概述
進制轉換即二進制數、八進制數、十進制數、十六進制數之間的轉換。本節將編程實現將二進制數、八進制數以及十六進制數轉換為十進制數，同時也可將十進制數轉換為二進制數、八進制數以及十六進制數。
關于進制轉換的具體分析如下。
（1）二進制數轉換為十進制數，只需將二進制數各位上的數字乘以 2 的相應次冪，最后求和即可。例如，二進制數 110010 對應的十進制數為 1×2 5 +1×2 4 +1×2 1 =50。
（2）八進制數轉換為十進制數，與二進制轉換類似。例如，八進制數 0333 對應的十進制數為 3×8 2 +3×8 1 +3×8 0 =219。
（3）十六進制數轉換為十進制數，與二進制、八進制轉換類似。例如，十六進制數 0x11 對應的十進制數為 1×16 1 +1×16 0 =17。
（4）十進制數轉換為二進制數，只需要將十進制數除以 2，每次取余從低位到高位排列。
（5）十進制數轉換為八進制數或十六進制數與二進制轉換類似。
8.5.2 算法實現
進制轉換的具體代碼參考教材8.5.2節。
例中，程序設置了菜單界面，用戶可以根據自己的轉換需求，選擇進制轉換。程序運行結果如下所示。
8.5.2 算法實現
由以上運行結果可知，選擇將十進制數轉換為二進制數，輸入的十進制數為 15，轉換為二進制數為 1111。
8.5.2 算法實現
由以上運行結果可知，選擇將十進制數轉換為八進制數，輸入的十進制數為 15，轉換為八進制數為 17。
8.5.2 算法實現
由以上運行結果可知，選擇將十進制數轉換為十六進制數，輸入的十進制數為 20，轉換為十六進制數為 14。
8.5.2 算法實現
由以上運行結果可知，選擇將二進制數轉換為十進制數，輸入的二進制數為 11001，轉換為十進制數為 25。
8.5.2 算法實現
由以上運行結果可知，選擇將八進制數轉換為十進制數，輸入的八進制數為 333，轉換為十進制數為 219。
8.5.2 算法實現
由以上運行結果可知，選擇將十六進制數轉換為十進制數，輸入的十六進制數為 1C，轉換為十進制數為 28。
由以上運行結果可知，輸入 0，程序退出。
8.6 尼科徹斯定理
8.6.1
算法概述
返回目錄
8.6.2
算法實現
8.6.1 算法概述
尼科徹斯定理指的是任何一個整數的立方都可以寫成 n 個連續奇數的和。例如，6×6×6=216=51+53+55+57。
證明尼科徹斯定理的具體過程如下。
（1）對于任意一個正整數 a，不論 a 是奇數還是偶數，可推理出整數(a×a－a+1)必然為奇數。因為(a×a－a+1)=[a×(a－1)+1]，偶數與奇數相乘必得偶數，所以 a×(a+1)必為偶數，再加 1 必為奇數。
（2）構造一個等差數列，數列的首項為(a×a－a+1)，等差數列的差值為 2（奇數數列），則前 a項的和為 a×[(a×a－a+1)+(a×a－a+2(a－1)+1)]/2（首項加末尾項乘以項數除以 2）。
（3）a×[(a×a－a+1)+(a×a－a+2(a－1)+1)]/2=a×(a×a－a+1+a×a－a+2a－2+1)/2=a×(a×a+a×a)/2=a×2(a×a)/2=a×a×a（任意數的立方）。
（4）由上述推理可知，任意一個整數的立方都可以由 n 個連續的奇數求和得到。設計程序證明上述定理，關鍵的步驟是確定這串連續奇數的最大值的范圍。假設任何數的立方的一半為 x，如果 x 為奇數，則這些連續奇數的最大值不會超過 x；如果 x 為偶數，則這些連續奇數的最大值不會超 x+1。基于這一規則，可以采用窮舉法證明尼科徹斯定理。
8.6.2 算法實現
證明尼科徹斯定理的代碼參考教材8.6.2節。
例中，算法的核心操作是得到整數立方值一半，即滿足條件的連續奇數的最大值，然后從該值依次減 2，找到滿足條件的連續奇數為止，同時可以得到滿足條件的所有連續奇數。程序運行結果如下所示。
由運行結果可以看出，6 的立方換算為連續奇數之和的情況一共有 4 種。
8.7 分數計算器
8.7.1
算法概述
返回目錄
8.7.2
算法實現
8.7.1 算法概述
分數形式的計算在數學中十分常見，使用分數可以表示不能整除的情況。本節將通過程序設計實現分數的加、減、乘、除四則運算。
實現分數計算器，需要了解分數四則運算的計算原理。
（1）加法。分數相加，首先需要將分母通分，即找出分母的最小公倍數；然后將分母轉換為最小公倍數的形式，得到對應的分子；最后將分子相加。如果需要約分，則找到分子分母的最大公約數，得到最后的分數結果。
（2）減法。與加法類似，首先需要通分，并將分子相減，最后約分。
（3）乘法。將分子與分子相乘，分母與分母相乘，然后對分子與分母進行約分。
（4）除法。分數相除可以轉換為第一個分數乘以第二個分數的倒數（即分子與分母調換），然后按照分數相乘的方式計算結果。
8.7.2 算法實現
分數計算器實現分數四則運算的具體代碼如例所示。
例中，程序根據輸入的四則運算符號執行對應的運算操作。程序運行結果如下所示。
由運行結果可知，計算分數 1/3 與分數 3/4 的和，輸出 13/12，測試結果正確。
8.7.2 算法實現
由運行結果可知，計算分數 1/3 與分數 3/4 的積，輸出 1/4，測試結果正確。
由運行結果可知，計算分數 1/3 與分數 1/4 的差，輸出 1/12，測試結果正確。
由運行結果可知，計算分數 1/3 與分數 3/4 的商，輸出 4/9，測試結果正確。
8.8 勾股數組
8.8.1
算法概述
返回目錄
8.8.2
算法實現
8.8.1 算法概述
我國數學家對二維勾股數組的研究由來已久。公元前十一世紀，周朝數學家商高就提出了“勾三股四弦五”的概念。在《周髀算經》中記錄著商高與周公的一段對話，商高說：“……故折矩，以為勾廣三，股修四，徑隅五。”意為：當直角三角形的兩條直角邊分別為 3（勾）和 4（股）時，徑隅（弦）則為 5。后來人們就簡單地將這個事實說成“勾三股四弦五”，根據該典故稱勾股定理為商高定理。
由上述描述可知，凡滿足方程 a 2 +b 2 =c 2 的正整數數組(a,b,c)就稱為一個二維勾股數組（注意，這里的二維數組與計算機中的二維數組非同一概念）。
8.8.2 算法實現
下面設計程序得到 100 以內的所有二維勾股數組示例代碼參考教材8.8.2節。
例中，主函數通過循環測試 1～100 的所有 a、b 的值，并且通過 Sqrt()函數計算所有 a 2 +b 2取平方根后的值，即 c 的值。特別需要注意的是，得到的 c 值為取整后的值。如果 c 經過取整，那么c 2 ＜a 2 +b 2 。例如， 17=4.123106，取整為 4，而 4 2 ＜1 2 +4 2 ，二者不相等，因此(1,4,4)非勾股數組。、Sqrt()函數使用探測的方式，使探測值無限接近于正確值。例如，計算 17 ，首先選擇 17 的最高位進行探測（即 x=10），顯然 10 2 ＞17，則下一次探測精度縮小為原來的110， 1 2 ＜ 17 ，x 加 1 繼續探測，判斷 2 2 ＜ 17 ，以此類推，直到 x 的值為 5 時， 5 2 ＜ 17 ，可知 17 的值介于 4 與 5 之間，再次縮小探測精度，繼續探測 4.1 、 4.2 ……。探測精度由 ss 控制。
8.8.2 算法實現
程序運行結果如下所示。
以上輸出結果為所有滿足條件的勾股數組。
本章小結
本章主要介紹了一些常見的涉及數學思維的算法操作，每一個算法的實現都涉及了 C 語言的一些編程技巧。望讀者理解這些算法的原理，并熟練操作，從中總結經驗，提高實際開發中的 C 語言程序設計能力。

展開更多......

收起↑