1.3.1算法案例(第一课时)ppt.ppt

1、算法案例(第一课时)，案例1涉及除法和更多的减损。1.复习算法的三种表达方式：自然语言、程序框图、程序语言、(三种逻辑结构)、(五个基本句子)。2.想想：小学时学的求两个数的最大公约数的方法？首先，连续去除两个公共的质因数，直到获得的商是质数。然后所有的因子相乘。1.找出两个正整数的最大公约数，(1)找出25和35的最大公约数，(2)找出49和63的最大公约数。因此，25和35的最大公约数是5。因此，49和63的最大公约数是7。2.除了这个方法，还有其他方法吗？计算8256和6105的最大公约数，按圈除(欧几里德算法)，观察按圈除找到8251和6105的最大公约数的过程。在第一步中，用两个数中

2、较大的一个除以较小的一个，得到商和余数8251=61051 2146。结论：8251和6105的公约数是6105和2146的公约数，只有找到6105和2146的公约数，才能找到8251和6105的最大公约数。在第二步中，对6105和2146 6105=21462 1813重复第一步。类似地，最大公约数6105和2146也是最大公约数2146和1813。为什么？思考：你从上述过程中意识到了什么？完成过程，8251=61051 2146，6105=21462 1813，2146=18131 333，1813=3335 148，333=1482 37，148=374 0，例2通过辗转反侧除法求出最大

3、公约数225和135，225=1351 90，135=901 45，95S1:用十进制数除大数，S2:除数变成被除数，余数变成除数，S3:重复S1直到余数是0，迭代除法是重复的步骤，直到余数等于0，这实际上是一个循环结构。m=NQ r，用程序框图显示右边的过程，r=mMODn，m=n，n=r，r=0？哪个逻辑结构是划分的关键步骤？(1)欧几里德算法(1)数学原理：所谓的“辗转反侧除法”是指将给定的两个数除以一个更大的数。如果余数不为零，余数和较小的数形成一对新的数，并继续上述除法，直到大的数被十进制数除，那么较小的数就是原始两个数的最大公约数。(2)算法步骤，步骤1:输入两个正整数m，n(mn

4、)。步骤2:计算m除以n得到的余数r。步骤3: m=n，n=r。步骤4:如果r=0，m，n的最大公约数等于m；否则，转到步骤2。步骤5:输出最大公约数m(3)程序框图，(4)程序，输入 m，n=；M，NDR=MMODNM=NN=RLOOPOUNTILR=0PRINTMEND，01030130更贬义，其计算原理是：对于那些可以是一半、一半而不是一半的，分母和sub的数目被设置为用更少减少更多，用更少减少更多，并找出相等的数目，从而减少相等的数目。第一步：任意给定两个正整数；判断它们是否都是偶数。如果是，用2表示减少；如果没有，执行第二步。第二步：用较大的数字减少较小的数字，然后比较与较小数字的差

5、异，用较大的数字减少数字。继续此操作，直到获得的子减数之间的差值相等，那么这个相等的数就是最大公约数。(2)更多的相位损失(1)数学上的：所谓更多的相位损失是指对于给定的两个数字，从较大的数字中减去较小的数字，然后形成具有差值和较小数字的新数字对，从较大的数字中减去较小的数字，并重复该步骤，直到差值和较小的数字相等。此时，相等的两个数是原始两个数的最大公约数。(2)算法步骤，步骤1:输入两个正整数a、b(ab)；步骤2:如果a不等于b，则执行步骤3；否则，转到步骤5；第三步：将a和b之间的差异分配给r；步骤4:如果是br，将B分配给A，将R分配给B；否则，将R分配给A并执行第二步；步骤5:输出

6、最大公约数B，(3)程序框图，(4)程序，输入 A，B=；例3使用更多的相位减法来寻找98和63的最大公约数。解决方法：由于63不是偶数，请大量减少98和63。然后相减，98-63=3563-35=2835-28=728-7=2121-7=2114-7=7，因此，98和63的最大公约数等于7，首先减少，然后找到21和18的最大公约数，然后乘以2的质因数减少4，例3，找到324、243和135的最大公约数。思路分析：要找到三个数的最大公约数，可以先找到两个数的最大公约数，而第三个数的最大公约数和前两个数的最大公约数是需求。(1)两者都是求最大公约数的方法。除法是主要的计算方法，减法是主要的计算方