(
课件网) 3.2算法及其描述 编制计算机程序解决问题的全过程 分析问题 设计算法 编写程序 调试运行 检测结果 编程能够训练思维，它体现了一种抽象交互关系，自动化执行的思维模式。 编程重要的是逻辑思路，确定解决问题的详细方法和步骤，即设计算法。算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则，是能够被机械执行的动作或者指令的有穷集合。 在《几何原本》中，欧几里得阐述了关于求两个正整数的最大最大公约数的过程，这就是著名的欧几里得算法--辗转相除法，其具体过程如下： 设给定的两个正整数为m和n，求它们的最大公约数的步骤为： ①以m除以n，令所得的余数为R。 ②若R=0，则输出结果n，算法结束；否则，继续步骤③ ③令m=n，n=R，并返回步骤①继续进行。 实践 设给定的两个正整数m=112和n=64，利用辗转相除法，求它们的最大公约数。 算法如下： （1）112除以64，余数为--； （2）--除以--余数为-- （3）--除以--余数为--。 答：112和64的最大公约数为-- 48 64 48 16 48 16 0 16 算法的特征 数据输入：一个算法有零个或多个输入； 确定性：算法执行的每一步必须有确切的定义，不可含混不清； 有穷性：一个算法在执行有穷步之后必须结束； 数据输出：一个算法有一个或多个输出，即最后的结果 可行性：算法中执行的任何计算步骤都可以被分解成基本的 可执行的操作步骤，即每个基本步骤都可以在有限时间内完成。 算法的描述 （1）用自然语言描述算法：比较容易理解，越详细越好，但如果算法中含有比较多的分支或者循环操作等时，使用自然语言比较难将其清晰表示出来；同时由于自然语言的歧义性会导致算法执行的不确定性。 如：咬死了猎人的狗 设给定的两个正整数为m和n，求它们的最大公约数的步骤为： ①以m除以n，令所得的余数为R。 ②若R=0，则输出结果n，算法结束；否则，继续步骤③ ③令m=n，n=R，并返回步骤①继续进行。 （2）用流程图描述算法：用程序框图来描述，使流程清晰、简洁。 用辗转相除法求两数的最大公约数 （1）输入m和n的值； （2）用m除以n，令所得的余数为r； （3）若r=0，则输出n,算法结束，否则继续（3）； （4）令m=n，n=r，并返回步骤（1）。 开始 输入m和n r=m % n r=0 输出n 结束 m=n n=r 否 是 牛刀小试： 利用流程图描述求一元二次方程ax2+ bx+c=0的根 1.输入a，b，c的值 2.令d=b b-4 a c 3.如果 d>=0 计算 x1= x2= 输出x1,x2 转步骤4 否则输出“方程无解”转步骤4 4.结束程序 算法的描述 （3）用伪代码描述算法：用介于自然语言和计算机语言之间的文字和符号来描述算法，易于理解，便于向计算机程序设计语言过渡。 m=input(“请输入m的值”) n=input(“请输入n的值”) R=m%n while R!=0: { m=n n=R R=m%n} 输出n 算法举例 有两个瓶子A和B ，A瓶装有雪碧，B瓶是可乐，问如何把雪碧和可乐互换。即A瓶原来雪碧，现改为盛可乐，B瓶则相反。 第一步：将A内溶液倒入C瓶中 第二步：将B内溶液瓶倒入A瓶中 第三步：将C内溶液瓶倒入B瓶中 程序的三种基本结构 前面的算法描述中我们用到了顺序结构、选择结构、循环结构这三种基本控制结构。任何复杂的算法都可以使用这三种基本控制结构组合来表示。 语句1 语句2 顺序结构表示程序中各个步骤按照出现的先后顺序依次执行。 程序的三种基本结构 选择结构表示程序的处理步骤出现了分支，需要按照某一个特定的条件选择其中一个分支执行，有单选择，双选择，多选择。 条件 语句1 语句2 Y N 程序的三种基本结构 循环结构表示反复执行某些操作直到判断条件为假或者为真时才结束循环。如辗转相除法求两数最大数 条件 条件 语句组 Y N Y N 语句组 开始 输入m和n r=m % n r=0 输出n 结束 ... ...
