知识点 算法案例
知识点—— 算法案例
【常见三大算法】 (1)求最大公约数 (2)秦九韶算法 (3)进位制
算法案例 【常见三大算法】 （1）求最大公约数 （2）秦九韶算法 （3）进位制
【求最大公约数】 (1)短除法 求两个正整数的最大公约数的步骤:先用两个数 公有的质因数连续去除,一直除到所得的商是两 个互质数为止,然后把所有的除数连乘起来 (2)穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤: 从两个数中较小数开始由大到小列举,直到找到 公约数立即中断列举,得到的公约数便是最大公 约数
算法案例 【求最大公约数】 （1）短除法 求两个正整数的最大公约数的步骤：先用两个数 公有的质因数连续去除，一直除到所得的商是两 个互质数为止，然后把所有的除数连乘起来. （2）穷举法（也叫枚举法） 穷举法求两个正整数的最大公约数的解题步骤： 从两个数中较小数开始由大到小列举，直到找到 公约数立即中断列举，得到的公约数便是最大公 约数
求最大公约数】 (3)辗转相除法 辗转相除法求两个数的最大公约数,其算法可以 描述如下 ①输入两个正整数m和m(m>n); ②求余数r:计算m除以n,将所得余数存放到变 量r中; ③更新被除数和余数:m=n,n=r; ④判断余数r是否为0若r=0,则m,n的最大公约 数等于m;否则转向第②步继续循环执行. 如此循环,直到得到结果为止
算法案例 【求最大公约数】 （3）辗转相除法 辗转相除法求两个数的最大公约数，其算法可以 描述如下： ①输入两个正整数m和n(m>n)； ② 求余数r：计算m除以n，将所得余数存放到变 量r中； ③更新被除数和余数：m=n，n=r； ④判断余数r是否为0.若r=0，则m，n的最大公约 数等于m；否则转向第②步继续循环执行. 如此循环，直到得到结果为止
【求最大公约数】 (4)更相减损术 我国早期也有解决求最大公约数问题的算法,就是更 相减损术,在《九章算术》中记载了更相减损术求最大 公约数的步骤:可半者半之,不可半者,副置分母·子 之数,以少减多,更相减损,求其等也,以等数约之 步骤: I.任意给出两个正数;判断它们是否都是偶数 若是,用2约简;若不是,执行第二步. Ⅱ.以较大的数减去较小的数,接着把较小的数与所 得的差比较,并以大数减小数继续这操作,直到所得 的数相等为止,则这个数(等数)就是所求的最大公 约数
算法案例 【求最大公约数】 （4）更相减损术 我国早期也有解决求最大公约数问题的算法，就是更 相减损术.在《九章算术》中记载了更相减损术求最大 公约数的步骤：可半者半之，不可半者，副置分母•子 之数，以少减多，更相减损，求其等也，以等数约之. 步骤： Ⅰ．任意给出两个正数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步. Ⅱ．以较大的数减去较小的数，接着把较小的数与所 得的差比较，并以大数减小数.继续这操作，直到所得 的数相等为止，则这个数（等数）就是所求的最大公 约数
秦九韶算法 秦九韶算法的一般规则: 秦九韶算法适用一般的多项式 的是 的求值问题. 用秦九韶算法求一般多项式 是是 ●。●
算法案例 【秦九韶算法】 秦九韶算法的一般规则： 秦九韶算法适用一般的多项式 的求值问题. 1 2 () .. 1 2 1 0 n n n fxaxaxax axa n n n − − =+ + +++ − − 用秦九韶算法求一般多项式 1 2 () .. 1 2 1 0 n n n fxaxaxax axa n n n − − =+ + +++ − − 1 2 ( .. ) 1 1 0 n n axax axa n n − − = + +++ − 2 3 ( .. ) ) 1 2 1 0 n n axax axaxa n n − − = + ++++ − = ... = +++++ (..( ) )..) axaxaxaxa n n n − − 1 2 1 0
秦九韶算法】 当x=x0时的函数值,可把n次多项式的求值问题转化成求n 个一次多项式的值的问题,即求 Vo-a 1=2nx+an-1 v2Ⅴ1X+an-2 Ⅴ3Ⅴ2X+a vn=Vn-=+ao 观察秦九韶算法的数学模型,计算v时要用到v-1的值, 若令v。=an 我们可以得到下面的递推公式: n 这是一个在秦九韶算法中反复执行的步骤,可以用循环结 构来实现
算法案例 【秦九韶算法】 当x=x0时的函数值，可把n次多项式的求值问题转化成求n 个一次多项式的值的问题，即求 v0=an v1=anx+an－1 v2=v1x+an－2 v3=v2x+an－3 …… vn=vn－1x+a0 观察秦九韶算法的数学模型，计算vk时要用到vk－1的值， 若令v0=an . 我们可以得到下面的递推公式： v0=an vk=vk－1+an－k (k=1,2,…n) 这是一个在秦九韶算法中反复执行的步骤，可以用循环结 构来实现
进位制】 1)概念 进位制是为了计数和运算方便而约定的记数系统,约定 “满几进一”就是几进制,几进制的基数(大于1的整 数)就是几 对于任何一个数,我们可以用不同的进位制来表示。比 如:十进数57,可以用二进制表示为11001,也可以用 八进制表示为71、用十六进制表示为39,它们所代表的 数值都是一样的 般地,若k是一个大于一的整数,那么以k为基数的k 进制可以表示为 anan1…,a1a0(k) (0≤an<k,0≤an1…a1,a0<k), 而表示各种进位制数一般在数字右下脚加注来表示,如 11101示二进制数,34表示5进制数
算法案例 【进位制】 (1)概念 进位制是为了计数和运算方便而约定的记数系统，约定 “满几进一”就是几进制，几进制的基数（大于1的整 数）就是几. 对于任何一个数，我们可以用不同的进位制来表示。比 如：十进数57，可以用二进制表示为111001，也可以用 八进制表示为71、用十六进制表示为39，它们所代表的 数值都是一样的. 一般地，若k是一个大于一的整数，那么以k为基数的k 进制可以表示为： anan-1…a1a0 (k) (0<an<k，0 ≤an-1…a1 ,a0<k), 而表示各种进位制数一般在数字右下脚加注来表示,如 111001(2)表示二进制数,34(5)表示5进制数
【进位制】 (2)进位制间的转换 关于进位制的转换,教科书上以十进制和二进制 之间的转换为例讲解,并推广到十进制和其它进 制之间的转换这样做的原因是,计算机是以二进 制的形式进行存储和计算数据的,而一般我们传 输给计算机的数据是十进制数据,因此计算机必 须先将十进制数转换为二进制数,再处理,显然 运算后首次得到的结果为二进制数,同时计算机 又把运算结果由二进制数转换成十进制数输出
算法案例 【进位制】 (2)进位制间的转换 关于进位制的转换，教科书上以十进制和二进制 之间的转换为例讲解，并推广到十进制和其它进 制之间的转换.这样做的原因是，计算机是以二进 制的形式进行存储和计算数据的，而一般我们传 输给计算机的数据是十进制数据，因此计算机必 须先将十进制数转换为二进制数，再处理，显然 运算后首次得到的结果为二进制数，同时计算机 又把运算结果由二进制数转换成十进制数输出
进位制】 非十进制数转换为十进制数比较简单,只要计算下面 的式子值即可: anan1,a12(k)=an×k+an1×k1+…a1×k+a0 第一步:从左到右依次取出k进制数anan1 a1a 各位上的数字,乘以相应的k的幂,k的幂从n开始取 值,每次递减1,递减到0,即an×k;an1×k-1,… a1×ka0×k0; 第二步:把所得到的乘积加起来,所得的结果就是相 应的十进制数
算法案例 【进位制】 非十进制数转换为十进制数比较简单，只要计算下面 的式子值即可：; anan-1…a1a0 (k)=an×k n+an-1×k n-1+ … a1×k+a0 第一步：从左到右依次取出k进制数anan1……a1a0 (k) 各位上的数字，乘以相应的k的幂，k的幂从n开始取 值，每次递减1，递减到0，即an×k n ,an-1×k n-1 , … ,a1×k, a0×k 0 ; 第二步：把所得到的乘积加起来，所得的结果就是相 应的十进制数