第3章 软件过程的组织管理.ppt

算法,第3章：数学问题,课程安排,1 有趣的整数 2 素数 3 阶乘 4 求的近似值 5 方程求解 6 矩阵的运算 7 一元多项式的运算,3.1 有趣的整数,如果一个数恰好等于其因子之和，这个数就称为完数。,3.1.1 完数,6=123 28=124714,求10000以内的所有完数的过程： （1）则用n去除以1n之间的所有整数，将能整除的被除数保存到一个数组中，作为n的一个因子。 （2）用数n减去该因子，以方便计算各因子之和是否正好等于n。 （3）继续重复步骤1和步骤2，直至将所有整数除完为止。 （4）最后判断各因子之和是否等于数n，若相等，则数n为完数，输出该数和各因子。,3.1 有趣的整数,假设有a、b两个数，若a的所有因子之和等于b的所有因子之和，并且a不等于b，则称a和b是一对亲密数。如284和220就是一对亲密数。 若要找出10000以内的亲密数，可使用以下算法： （1）对每一个数a，将其因子分解出来，并将因子保存到一个数组中，再将因子之和保存到变量b1。 （2）将因子之和b1再进行因子分解，并将因子保存到一个数组中，将因子之和保存到变量b2中。 （3）若b2等于a，并且b1不等于b2，则找到一对亲密数为a和b1，可将其输出。 （4）重复步骤（1）（3），即可找出指定范围的亲密数。,3.1.2 亲密数,3.1 有趣的整数,一个三位数，若数值等于各位数字的三次幂之和，就称为“水仙花数”。,3.1.3 水仙花数,3.1 有趣的整数,所谓自守数，是指一个数的平方的尾数等于该数自身的自然数。例如：6的平方等于36，尾数是6，所以6是自守数；25的平方等于625，尾数是25，所以25是自守数。,3.1.4 自守数,2,3.1 有趣的整数,欧几里德算法 欧几里德算法采用辗转相除的方法来求最大公约数，这是计算两个数最大公约数的传统算法 其算法思路为： （1）对于已知两数m、n，使mn； （2）m除以n得余数r； （3）若r=0，则n为求得的最大公约数，跳至第（5）求最小公倍数；否则执行第4步； （4）将n的值保存到m中，将r的值保存到n中，重复执行步骤（2）和（3）。 （5）有了两数的最大公约数，则最小公倍数就很简单了，将两数相乘的积除以最大公约数即可。,3.1.5 最大公约数最小公倍数,3.1 有趣的整数,Stein算法 Stein算法只有整数的移位和加减法，而不需要进行除法和取模运算，这将提高算法的执行效率。 Stein算法如下（求a、b两数的最大公约数）： （1）首先判断a或b是否为0，若a=0，b就是最大公约数；若b=0，a就是最大公约数，完成计算操作。 （2）设a1=a、b1=b和c1=1。 （3）判断an和bn是否为偶数，若都是偶数，则使an+1=an/2，bn+1=bn/2，cn+1=cn*2。 （4）若an是偶数，bn是奇数，则使an+1=an/2，bn+1=bn，cn+1=cn。 （5）若bn是偶数，an是奇数，则使bn+1=bn/2，an+1=an，cn+1=cn。 （6）若an和bn都是奇数，则使an+1=|an-bn|，bn+1=min(an,bn)，cn+1 =cn。 （7）n累加1，跳转到第3步进行下一轮运算。,3.1.5 最大公约数最小公倍数,3.2 素数,所谓素数，是指除了1和自身之外，没有别的因数的数。除了1和自身外，还有别的因数的数是合数。1既不是素数也不是合数。素数的分布是没有规律的。如：101、401、601、701都是素数，但上下面的301和901却是合数。 要求N是不是素数，可用N逐个除以2N-1之间的数，若某个数能被整除，则表示该数不是素数,3.2.1 求素数,3.2 素数,所谓回文数，是指一个多位数在按位读时，无论从左向右还是从右向左倒序读取，其结果都是一样的特征。例如：11、22、101、111、818、12321等。 回文数素数 平方回文数,3.2.2 回文素数,3.2 素数,所谓哥德巴赫猜想，是指哥德巴赫在教学中发现，每个不小于6的偶数都是两个素数之和。大家都相信这个猜想是正确的，但不能证明。 对于哥德巴赫猜想的验证，算法很简单，其基本思路是：设n为大于等于6的一个偶数，可将其分解为n1和n2两个数，分别检查n1和n2是否为素数，如都是，则在该数得到验证。若n1不是素数，就不必再检查n2是否素数。先从n1=2开始，检验n1和n2（n2=n-n1）是否素数。然后使n1+2再检验n1、n2是否素数，直到n1=n/2为止。,3.2.3 哥德巴赫猜想,3.3 阶乘,3.3.1 用递归计算阶乘 3.3.2 大数阶乘,3.4 求的近似值,3.4.1 概率法,3.4 求的近似值,3.4.2 割圆法,3.4 求的近似值,3.4.3 公式法,3.4 求的近似值,3.4.4 计算任意位数的,3.5 方程求解,3.5.1 高斯消元法解线性方程组,3.5 方程求解,3.5.2 二分法解非线性方程,二分法又称对分法，是最简单的求解一元非线性方程根的算法之一。其基本思想是：将含根区间I逐次分半缩小，得到一个区间长度以1/2的比例减小的含根区间序列I1、I2，在给定根的误差界时，利用Ik的长度趋于0的特点，可得到在某个区间I中求得满足要求的近似根。,3.5 方程求解,3.5.3 牛顿迭代法解非线性方程,牛顿迭代法是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。迭代法的基本思想就是构造一串收敛到解的序列，即建立一种从已有近似解来计算新的近似解的迭代式，然后选取方程的某个初始近似值x0代入迭代式，反复这个过程使得到的根逐渐逼近于真实根，直到满足精度为止。,导函数：,3.6 矩阵运算,3.3.1 矩阵加法和乘法运算,1. 矩阵加法运算,2. 矩阵乘法运算,3.6 矩阵运算,3.3.2 多维矩阵转一维矩阵,二维矩阵转一维矩阵下标公式（以行为主）： loc=row*每行元素数量+column 二维矩阵转一维矩阵下标公式（以列为主）： loc= column*每列元素数量+row,3.6 矩阵运算,3.3.3 逆矩阵,对于n阶方阵A，如果存在一个n阶方阵B，使得AB=BA=C（C为n阶单位矩阵），则把方阵B称为A的逆矩阵（简称逆阵）记作A-1，即B=A-1,3.6 矩阵运算,3.3.4 稀疏矩阵,将表示稀疏矩阵的非0元素的三元组按行优先（或列优先）的顺序排列，并依次存放在数组中，这种稀疏矩阵的顺序存储结构称为三元组表。,3.7 一元多项式的运算,3.7.1 多项式加法,一元多项式加法运算的规则非常简单，就是将具有相等幂项的系数相加即可得到合并后的多项式。若某个幂只存在于一个多项式中，则直接合并到结果中。,结果：,3.7 一元多项式的运算,3.7.2 多项式减法,与多项式加法类似，两个一元多项式相减也只是将具有相等幂项的系数相减即可，若某个幂只存在于被减项，则直接合并到结果中，若某个幂只存在于减项，则将其系数符号取反（乘以-1），再合并到结果中。,性格决定命运, 专注成就人生,