算法案例

【习目标】

1.理解辗转相除法与更相减损术中蕴含的数原理，并能根据这些原理进行算法分析；

2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序；

3.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质；

4.了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换.

【要点梳理】

要点一：辗转相除法

也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下：

第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；

第二步：若r0=0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；

第三步：若r1=0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；

......

依次计算直至rn=0，此时所得到的rn－1即为所求的最大公约数.

用辗转相除法求最大公约数的程序框图为：

程序：