3.2算法及其描述课件-2024-2025学年粤教版（2019）高中信息技术必修一

3.2算法及其描述 掌握算法描述的三种方法 理解算法的概念 掌握算法的特征 01 02 03 学习目标 学习目标 2 算法的概念 【更相减损术】 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。 好，同学们，对于这段关于更相减损术的描述，你们能不能看懂，有没有同学能够帮我们翻译一下呀？好，那我们不花太多的时间去翻译这段对于更相减损术的文言文描述了，我们直接看把它翻译成白话文的描述。 3 算法的概念 更相减损术求最大公约数的求解过程 第一步：对于任意给定的两个正整数；判断它们是否都是偶数。若是则用2约简直到其中一个不为偶数；若不都是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，如果不相等，则以大数减小数。继续这个操作，当所得的差和较小的数相等时执行第三步。 第三步：用第一步中约简的若干个2乘以第二步中的等数就是所求的最大公约数。 4 算法的概念 应用更相减损求196和126的最大公约数 第一步：对于任意给定两个正整数；判断它们是否都是偶数。若是则用2约简直到其中一个不为偶数；若不都是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，如果不相等，则以大数减小数。继续这个操作，当所得的差和较小的数相等时执行第三步。 第三步：用第一步中约简的若干个2乘以第二步中的等数就是所求的最大公约数。 第一步：判断196和126都是偶数，则用2约简，得到98和63，此时98、63不都是偶数，则执行第二步； 第二步：用较大的98减去较小的63得到的差为35 第三步：接着判断较小的数63和35是否相等，不相等则用较大的63减去较小的数35得到的差为28； 第四步：再判断较小的数35和得到差28是否相等，不相等则用较大的35减去较小的28得到的差7； 第五步：再判断较小的28和得到的差7是否相等，不相等则用较大的28减去较小的7得到的差为21； 第六步：再判断较小的7和得到的差21是否相等，不相等则用较大的21减去较小的7得到的差为14； 第七步：再判断较小的7和得到的差14是否相等，不相等则用较大的14减去较小的7得到的差为7； 第八步： 再判断较小的7和得到的差7是否相等，此时相等，则执行第九步； 第九步：用第一步中约简的一个2乘以第八步中得到的等数7得到的14就是196和126的最大公约数； 好，同学们，我们左侧描述的是求任意两个正整数的最大公约数的步骤，右侧描述的是求解196和126的最大公约数的步骤，我们把求解某一类问题或者某一个问题的步骤就叫做算法，那算法到底是什么呢，我们一起来看一下。 5 算法的概念 第一步：判断196和126都是偶数，则用2约简，得到98和63，此时98、63不都是偶数，则执行第二步； 第二步：用较大的98减去较小的63得到的差为35 第三步：接着判断较小的数63和35是否相等，不相等则用较大的63减去较小的数35得到的差为28； 第四步：再判断较小的数35和得到差28是否相等，不相等则用较大的35减去较小的28得到的差7； 第五步：再判断较小的28和得到的差7是否相等，不相等则用较大的28减去较小的7得到的差为21； 第六步：再判断较小的7和得到的差21是否相等，不相等则用较大的21减去较小的7得到的差为14； 第七步：再判断较小的7和得到的差14是否相等，不相等则用较大的14减去较小的7得到的差为7； 第八步： 再判断较小的7和得到的差7是否相等，此时相等，则执行第九步； 第九步：用第一步中约简的一个2乘以第八步中得到的等数7得到的14就是196和126的最大公约数； 广义的算法是指在有限步骤内求解某一问题时所使用的一组定义明确的规则或步骤。 计算机领域的算法就是用计算机求解某一问题时能被计算机执行的有穷指令的集合。 设计算法的最终目的是为了让计算机根据我们设计的算法解决实际问题！ 1.好，同学们，我们知道了算法其实就是求解问题的步骤或者说规则，那你们知道我们设计算法的目的是什么吗？我们设计算法的目的是为了让计算机根据我们设计的算法解决同一类问题，从而把人类从大量的重复性工作中解放出来，既然我们设计算法的目的是为了让计算机帮我们解决问题，那我们看一下计算机中的算法又是什么？ 2.计算机领域的算法指的是用计算机解决问题时能被计算机执行的指令集，那同学们想想，我们是不是得有一个东西能够将广义算法中我们设计的解决问题的步骤转化为计算机能够执行的指令，那同学们知道这个转化的东西是什么吗？其实这个东西就是我们的编程语言。 2.像右侧把解决问题的过程写成一步一步的步骤的方式只是我们描述算法的其中一种方法，那我们还有哪些描述算法的方式呢？我们一起来看一下。 6 算法的描述方法 自然语言描述算法 1 流程图描述算法 2 伪代码描述算法 3 1.自然语言描述算法说白了就是用人话来描述算法。 算法描述的方法 自然语言描述算法 自然语言描述算法指的是用人们日常所说的语言来描述算法，比如汉语、英语等。 第一步：判断196和126都是偶数，则用2约简，得到98和63，此时98、63不都是偶数，则执行第二步； 第二步：用较大的98减去较小的63得到的差为35 第三步：接着判断较小的数63和35是否相等，不相等则用较大的63减去较小的数35得到的差为28； 第四步：再判断较小的数35和得到差28是否相等，不相等则用较大的35减去较小的28得到的差7； 第五步：再判断较小的28和得到的差7是否相等，不相等则用较大的28减去较小的7得到的差为21； 第六步：再判断较小的7和得到的差21是否相等，不相等则用较大的21减去较小的7得到的差为14； 第七步：再判断较小的7和得到的差14是否相等，不相等则用较大的14减去较小的7得到的差为7； 第八步： 再判断较小的7和得到的差7是否相等，此时相等，则执行第九步； 第九步：用第一步中约掉的一个2乘以第八步中得到的等数7得到的14就是196和126的最大公约数； 8 算法描述的方法 流程图描述算法 流程图描述算法就是用程序框图来描述算法。 流程图的基本图形及功能 图形 名称 功能 开始/结束 表示算法的开始或结束 处理 表示算法中数据的处理和计算 输入/输出 表示算法中数据的输入或输出 判断 表示算法中的条件判断 流程线 表示算法的执行方向 9 算法描述的方法 流程图的基本图形及功能 图形 名称 功能 开始/结束 表示算法的开始或结束 处理 表示算法中变量的计算或赋值 输入/输出 表示算法中数据的输入或输出 判断 表示算法中判断条件判断 流程线 表示算法的执行方向 第一步：判断196和126都是偶数，则用2约简，得到98和63，此时98、63不都是偶数，则执行第二步； 第二步：用较大的98减去较小的63得到的差为35 第三步：接着判断较小的数63和35是否相等，不相等则用较大的63减去较小的数35得到的差为28； 第四步：再判断较小的数35和得到差28是否相等，不相等则用较大的35减去较小的28得到的差7； 第五步：再判断较小的28和得到的差7是否相等，不相等则用较大的28减去较小的7得到的差为21； 第六步：再判断较小的7和得到的差21是否相等，不相等则用较大的21减去较小的7得到的差为14； 第七步：再判断较小的7和得到的差14是否相等，不相等则用较大的14减去较小的7得到的差为7； 第八步： 再判断较小的7和得到的差7是否相等，此时相等，则执行第九步； 第九步：用第一步中约掉的一个2乘以第八步中得到的等数7得到的14就是196和126的最大公约数； 10 算法描述的方法 开始 a=196,b=126 a%2==0 且b%2==0 ,t=0 t=t+1 a=a/2,b=b/2 Yes a=max(a,b) b=min(a,b) c=a-b b==c? Yes 输出2t*c No a=c No 11 算法描述的方法 开始 用流程图描述求任意给定的两个正整数a和b的最大公约数的算法 输入a和b的值 t=0 a%2==0 且b%2==0 t=t+1 a=a/2,b=b/2 Yes a=max(a,b) b=min(a,b) c=a-b b==c? Yes 输出2t*c No a=c No 12 算法描述的方法 伪代码描述算法 伪代码描述算法就是用介于自然语言和编程语言之间的文字和符号来描述算法 输入a和b的值 t=0; while(a%2==0 && b%2==0): a=a/2; b=b/2; t=t+1; while(a!=b): a=max(a,b); b=min(a,b); c=a-b; a=c; 输出2t*c 用伪代码描述求任意给定的两个正整数a和b的最大公约数的算法 13 算法的特征 1. 输入：一个算法一般要求有0个或者多个数据输入；【输入指的是算法执行时需要从外部获取的数据】 2. 输出：一个算法要有一个或多个数据输出，没有输出的算法是没有意义的； 【输出指的是算法计算的结果】 3.有穷性：一个算法在执行了有穷步之后必须结束，不能永远执行下去； 4.可行性：算法的每一步都必须具有可操作性，并且能在有限时间内完成； 5.确定性：算法执行的每一步都必须有明确的定义，并且能够得到一个确定的结果； 第一步：判断196和126都是偶数，则用2约简，得到98和63，此时98、63不都是偶数，则执行第二步； 第二步：用较大的98减去较小的63得到的差为35 第三步：接着判断较小的数63和35是否相等，不相等则用较大的63减去较小的数35得到的差为28； 第四步：再判断较小的数35和得到差28是否相等，不相等则用较大的35减去较小的28得到的差7； 第五步：再判断较小的28和得到的差7是否相等，不相等则用较大的28减去较小的7得到的差为21； 第六步：再判断较小的7和得到的差21是否相等，不相等则用较大的21减去较小的7得到的差为14； 第七步：再判断较小的7和得到的差14是否相等，不相等则用较大的14减去较小的7得到的差为7； 第八步： 再判断较小的7和得到的差7是否相等，此时相等，则执行第九步； 第九步：用第一步中约掉的一个2乘以第七步中得到的等数7得到的14就是196和126的最大公约数； 1.输入：如果我们把刚才的问题改为求任意两个正整数的最大公约数，那么我们设计的算法应该在第一步的前面输入两个正整数。 2.输出：其实我们可以这样去理解算法，算法就类似于一个工厂，输入就是这个工厂加工所需要的原料，输出就是这个工厂对输入的原料加工后得到的产品。 3.有穷性：就像刚才说的，如果说我们的工厂一直在运转，但是永远都得不到一个产品，那这样的工厂是没有任何意义的。 4.可行性：算法中的每一步都必须具有可操作性。 5.确定性：算法中的执行的每一步都必须有明确的定义并得到同一个确定的结果，例如有这样一个问题，一支中性笔4元钱，一支铅笔3元钱，小明要用50块钱买这两种笔，并且总共买10支，请问，钢笔和铅笔各买多少支？ 现请你设计一个算法帮小明设计一个算法求出钢笔和铅笔各买多少支？ 14 算法的概念 给定任意两个正整数m和n，求他们的最大公约数的步骤为： ①：以m除以n，令所得的余数为r； ②：若r等于0，则输出结果n，算法结束，否则执行步骤③ ③：令m=n,n=r,并返回步骤①继续执行。 辗转相除法求最大公约数 请用流程图将上述算法表示出来。 15 算法描述的方法 用流程图描述辗转相除法求两个数的最大公约数 开始 输入m和n的值 r=m%n r==0 n=r m=n No 输出n的值 Yes r=m%n 16 $$