1.3算法案例
1.3 算法案例
1.3算法案例 1.3.1辗转相除法和更相减损术 1.3.2秦九韶算法 1.33K进制化十进制 1.34十进制化K进制
1.3.4 十进制化K进制 1.3.1 辗转相除法和更相减损术 1.3.2 秦九韶算法 1.3.3 K进制化十进制 1.3 算法案例
1.3.1辗转相除法 和更相减损术
1.3.1 辗转相除法 和更相减损术
复习 研究一个实际问题的算法,主要从哪几方面展开? 算法步骤、程序框图和编写程序三方面展开 2.在程序框图中算法的基本逻辑结构有哪几种? 顺序结构、条件结构、循环结构 3.在程序设计中基本的算法语句有哪几种? 输入语句、输出语句、赋值语句、条件语句、循豫包
复习 1.研究一个实际问题的算法，主要从哪几方面展开？ 2.在程序框图中算法的基本逻辑结构有哪几种？ 3.在程序设计中基本的算法语句有哪几种？ 算法步骤、程序框图和编写程序三方面展开. 顺序结构、条件结构、循环结构 输入语句、输出语句、赋值语句、条件语句、循环语句
·韩信是秦末汉初的著名军事家据说有一次汉高祖 刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什 么方法,不要逐个报数,就能知道场上的士兵的人数 韩信先令士兵排成3列纵队,结果有2人多余接着 下令排成5列纵队,结果又多出3人,随后他又下令 改为7列纵队,这次又剩下2人无法成整行在场的 人都哈哈大笑,以为韩信不能清点岀准确的人数,不 料笑声刚落,韩信高声报告共有士兵2333人.众人 听了一楞,不知道韩信用什么方法这么快就能得到 正确的结果的今天我们将以这些古典案例的思想 设计出适宜计算机的运行程序提高我们对基本复 法结构和算法语句在实际中的运用能力
情境创设 • 韩信是秦末汉初的著名军事家.据说有一次汉高祖 刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什 么方法,不要逐个报数,就能知道场上的士兵的人数, 韩信先令士兵排成3列纵队,结果有2人多余,接着 下令排成5列纵队,结果又多出3人,随后他又下令 改为7列纵队,这次又剩下2人无法成整行.在场的 人都哈哈大笑,以为韩信不能清点出准确的人数,不 料笑声刚落,韩信高声报告共有士兵2333人.众人 听了一楞,不知道韩信用什么方法这么快就能得到 正确的结果的.今天,我们将以这些古典案例的思想, 设计出适宜计算机的运行程序,提高我们对基本算 法结构和算法语句在实际中的运用能力
探究一,辗转相除法冖 思考1:在小学中我们是如何求出两个正整数 的最大公约数的呢? 算法案例之求最大公约数 例、求18与24的最大公约数: 解:2|1824用公有质因数2除, 3L12用公有质因数3除,短除法 343和4互质不除了 得:18和24最大公约数是:2×3=6 求以下几组正整数的最大公约数。 (注:若整数m和n满足n整除m,则(m,n)=n。用(m,n)来表示 m和n的最大公约数。 (1)(18,30)6 (2)(24,16)8 (3)(63,63)63 (4)(72,8)8 (5)(301,133)7; 想一想,如何求8251与6105的最大公约数?
探究一,辗转相除法 思考1:在小学中我们是如何求出两个正整数 的最大公约数的呢? 算法案例之求最大公约数 求以下几组正整数的最大公约数。 (注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示 m和n的最大公约数。) （1）（18，30） （2）（24，16） （3）（63，63） （4）（72，8） （5）（301，133 ） 解：2 1 8 2 4 用公有质因数2除， 3 9 1 2 用公有质因数3除， 3 4 3和4互质不除了。 得：18和24最大公约数是：2×3＝6 例、求18与24的最大公约数： 6； 8； 63； 8； 7； 短除法 想一想，如何求8251与6105的最大公约数？
思考2对于8251与6105这两个数,它们的最大 公约数是多少?你是怎样得到的? 由于它们公有的质因数较大,利用上述方法求 最大公约数就比较困难.有没有其它的方法可以较简 单的找出它们的最大公约数呢?
思考2:对于8251与6105这两个数，它们的最大 公约数是多少？你是怎样得到的？ 由于它们公有的质因数较大，利用上述方法求 最大公约数就比较困难.有没有其它的方法可以较简 单的找出它们的最大公约数呢？
思考3:注意到82516105×1+2146,那么8251 与6105这两个数的公约数和6105与2146的公约数有 什么关系? 我们发现6105=2146×2+1813,同理,6105与 2146的公约数和2146与1813的公约数相等 思考4:重复上述操作,你能得到8251与6105这 两个数的最大公约数吗? 8251-6105×1+2146,1813=333×5+148, 6105=21416×2+1813,33148×2+37, 2146=1813×1+333,148=37×4+0 定义:所谓的辗转相除法,就是对于给定的两个数, 用较大的数除以较小的数若余数不为零,则将余数 和较小的数构成新的数对继续上面的除法,直到数 被小数除尽则这是较小的数就是原来两个数的最公强
思考3：注意到8251=6105×1+2146，那么8251 与6105这两个数的公约数和6105与2146的公约数有 什么关系？ 我们发现6105=2146×2+1813，同理，6105与 2146的公约数和2146与1813的公约数相等. 思考4：重复上述操作，你能得到8251与6105这 两个数的最大公约数吗？ 2146=1813×1+333， 148=37×4+0. 333=148×2+37， 8251=6105×1+2146， 1813=333×5+148， 6105=2146×2+1813， 定义:所谓的辗转相除法,就是对于给定的两个数, 用较大的数除以较小的数,若余数不为零,则将余数 和较小的数构成新的数对,继续上面的除法, 直到大数 被小数除尽,则这是较小的数就是原来两个数的最大公约数
思考4:辗转相除直到何时结束? 主要运用的是哪种算法结构? 辗转相除法是一个反复执行直到余数等于0停止的步骤, 这实际上是一个循环结构 辗转相除法求两个数的最大公约数,其算法可以描述如下: ①输入两个正整数m和n; ②求余数r:计算m除以n,将所得余数存放到变量r中; ③更新被除数和余数:m=n,n=r ④判断余数r是否为0:若余数为0则输出结果,否则转 向第②步继续循环执行。 如此循环,直到得到结果
辗转相除法求两个数的最大公约数，其算法可以描述如下： 辗转相除法是一个反复执行直到余数等于0停止的步骤， 这实际上是一个循环结构 思考4：辗转相除直到何时结束？ 主要运用的是哪种算法结构？ 如此循环，直到得到结果。 ① 输入两个正整数m和n； ② 求余数r：计算m除以n，将所得余数存放到变量r中； ③更新被除数和余数：m=n，n=r。 ④判断余数r是否为0：若余数为0则输出结果，否则转 向第②步继续循环执行
思考5:你能把辗转相除法编成一个计算机程序吗? 第一步,给定两个正整数m,nm>n) 第二步,计算m除以n所得的余数r 第三步,m=n,n=r 第四步,若r=0,则m,n的最大公约数等于m 否则,返回第二步
第一步，给定两个正整数m，n(m>n). 第二步，计算m除以n所得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约数等于m； 否则，返回第二步. 思考5:你能把辗转相除法编成一个计算机程序吗？