算法和算法的表示.ppt

算法与程序设计,计算机解决问题的过程,走进编程,有一种较巧妙的方法，古代孙子就提出“砍脚算法”：如果将鸡和兔的脚都砍去一半，则1鸡对应1脚，1兔对应2脚，那么脚数减去鸡兔总数即为兔的数量。可得兔有94/2-35=12只,鸡有351223只。,假如鸡兔共有a只头,b只脚,由此可知,鸡+兔=a,2鸡+4兔=b,计算得知,鸡=a-(b-2a)/2只,兔=(b-2a)/a只,直接公式计算可以得出 自然语言描述的算法如下: 1 (初始化鸡兔总头数与总脚数)初始总头数a=35,总脚数b=94 2 (计算鸡的数目)输出鸡的数目为a-(b-2a)/2 3 (计算兔的数目)输出兔的数目为(b-2a)/2 4 (结束)计算完成,结束,使用计算机解决问题的一般过程,1、分析问题确定要用计算机做什么？ 2、寻找解决问题的途径和方法。 3、用计算机进行处理。,人工解题与计算机解题,人工解题过程： 理解和分析所面临的问题； 寻找解题的途径和方法； 用笔、纸、计数器等工具进行计算； 验证计算结果。,计算机解题过程： 理解和分析所要求的问题； 寻找解题的途径和方法； 生成解题算法； 选用一种算法语言根据算法编写程序； 通过编辑、编译、连接产生计算机能够识别的指令序列； 在计算机上执行该指令序列; 检测结果。,用计算机程序解决问题的基本过程,设计算法,分析问题,编写程序,调试程序,检测结果,人工解题与计算机解题的异同点,1.2 确定解决问题的方法,例1 使用一根长度为L厘米的铁丝，制作一个面积为S平方厘米的矩形框，要求计算该矩形框应有的高h和宽w.这里，铁丝的长度L和矩形框面积S是根据需要预先指定的，如图1.2.1所示。,面积S,宽 w,高 h,长度为L厘米的铁丝,高h,则宽W=L/2-h,面积 h(L/2-h)=s,h2-Lh/2+S=0,h1,h2=？,d=L2-16S,d0 h= w= d0 无实数解 d=0 h=w=L/4,1 显示文字“请输入长度：” 2 接受输入数据（铁丝的长度）送到变量L 3 显示文字“请输入面积：” 4 接受输入数据（矩形框的面积）送到变量S 5 计算L2-16S，结果送到变量d 6 若d=0转到12 7 若d0转到15 8 输出文字“两条不同的边长” 9 输出：（L+d）/4 10 输出（L- d）/4 11 结束 12 输出文字“两条相同的边长” 13 输出：L/4 14结束 15 输出文字“ 无解“ 16结束,指令区,变量L中的数值 变量S中的数值 变量d中的数值,数据区,1.指令部分：指令是对计算机操作类型和操作数地址做出规定的一组符号。指令部分由一系列的指令构成，每条指令指定了计算机应执行的一个动作。 2.数据部分：计算的原始数据，中间结果或最终结果。,计算机所执行的指令所组成的指令输入指令序列构成了一个程序。 一台计算机所使用的指令是有限的，经典指令类型有： 输入指令：通过输入设备，向程序输入数据，并存储到 指定的变量中。 输出指令：把计算结果通过输出设备输出 算术运算指令：进行加减乘除等运算 逻辑判断指令：判断真假 控制转移指令：用来改变程序中指令执行的顺序。,什么是算法？,广义地说为了解决某一问题而采取的方法和步骤，就称之为算法。 乐谱是乐队演奏和指挥的算法；菜谱是厨师烧菜的算法。 在计算机中，算法通常是指可以用计算机来解决某一类问题的程序或步骤，这些程序或步骤必须是明确的和有效的，而且能够在有限步之内完成。,1.4 算法的概念和表示方法,算法：解决问题的方法 算法的特征 有穷性 确定性 能行性 有0个或多个输入 有一个或多个输出 我们可通过一个算法的特征来判定一个算法是否正确，是否合理,计算1+2+3+4+5的值，无论手算、心算或者用算盘，计算器计算，都要经过有限的事先设计好的步骤。 太极拳动作图解就是一个“太极拳的算法”。 一个工作计划、生产流程、乐谱、珠算口诀等都可称为是“算法”。 对同一个问题往往有不同的解题方法。 例：1-1/2+1/3-1/4+1/99-1/100 方法：自左向右追项顺序相加或减。 方法：先计算1+1/3+1/5+1/99,再计算1/2+1/4+1/100,然后再做减法运算。 不仅数值计算的问题要研究算法，做任何事情都要有一定的步骤。,算法的表示,一个算法可以用多种不同的方法来描述。 常用的表示方法有： 流程图 自然语言 伪代码 计算机语言,流程图“5框1线”,处理框,输入输出框,判断框,连接框,开始结束符,流程线,用流程图描述例一的算法,变量和变量的用途,变量的作用：存储数据 变量的实质：内存中的存储单元（变量时存储数据的容器，而不是数据本身） 不同的变量有不同的名称，我们可以通过变量名引用变量中的数据 变量的操作 读（取）操作：从存储单元中复制数据； 写（存）操作：将数据覆盖到存储单元中。,变量和变量的用途,专门用途的变量： 计数器：用于记录某种指定的事件所发生的次数。 累加器：用于记录若干个数据的累加结果。 特殊的变量：如数组。（将在第四章中学习）,算法的执行流程,算法的执行流程是指算法中各个处理步骤的执行次序和模式。 算法执行流程的三种基本模式： 顺序模式 选择模式 循环模式