算法案例2

算法案例2高一数学备课组35915在小学，我们学过求两个正整数的最大公约数的方法，先用两个数公有的质因数连续去除，一直到所得的商是互质数为止，然后把所以的除数乘起来，例如，求18与30的最大共约数：183023所以，18与30的最大共约数是：2×3=6.问题：如何求最大公约数？利用找公约数的方法来求最大公约数，如果公约数比较大（如6105与2146），而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？尝试转化：求6105与2146最大共约数求2146与1813最大共约数转化因为6105＝2146×2＋18132146＝1813×1＋333;1813＝333×5＋148;333＝148×2＋37;148＝37×4＋0.148与37的最大共约数是372146与1813的最大共约数是37问题：如何求6105与2146的最大公约数？以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.练习:用辗转相除法求204与85的最大公约数．你能把辗转相除法求最大共约数的过程，写成算法吗？该算法中，要用到什么主要的算法结构？每一次循环中所进行的是什么样的运算？循环何时结束？下一次循环的输入整数应该是什么？循环结构r←mod(a，b)r=0a←bb←r[r1←mod(b，r)…]请用自然语言、流程图、伪代码三种语言描述该算法!S1输入两个正整数a,b（a＞b）；S2若Mod（a,b）≠0，则转S3,否则转S6；S3rMod（a,b）；S4ab；S5br，转S2；S6输出b．(最大公约数)（法一）先判断，再执行Y开始Mod(a,b)≠0r←Mod(a，b)输出b结束Na←bb←r输入a,bReada,bWhileMod(a,b)≠0rmod(a,b)abbrEndWhilePrintbS1输入两个正整数a，b（a＞b）；S2rMod（a,b）；S3ab；S4br；S5若r不等于0，转S2；S6输出a．(最大公约数).练习：用（法二）先执行，再判断，写出自然语言、流程图和伪代码。N开始r＝0r←Mod(a，b)输出a结束Ya←bb←r输入a,bReada,bDormod(a,b)abbrUntilr=0PrintaY开始Mod(a,b)≠0r←Mod(a，b)输出b结束Na←bb←r输入a,bN开始r＝0r←Mod(a，b)输出a结束Ya←bb←r输入a,b对比——两种循环语句的流程图对比——两种循环语句的伪代码!Reada,bWhileMod(a,b)≠0rmod(a,b)abbrEndWhilePrintbReada,bDormod(a,b)abbrUntilr=0Printa布置作业：金榜直通：第11课时(去第6、7、10题，第8题删除最小公倍数）