资源简介

(共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 语言程序设计能力。

展开更多......

收起↑