算法与算法的描述 完整版课件

1、1.2 算法及其描述“鸡兔同笼”问题一个笼子里有鸡和兔，现在只知道里面一共有a个头，b只脚，问鸡和兔各有多少只？人工求解设所求的鸡数是x，兔数是y，已知笼子里头是a，脚数是b。解方程组得：x=2a-b/2，y=b/2-ax+y=a2x+4y=b可得：分析问题人工求解过程对于任意整数a和偶数b做出回答：鸡有x只，兔有y只。求出x=2a-b/2，y=b/2-a。“鸡兔同笼”问题的算法什么是算法？Elements什么是算法？(解决问题的方法与步骤）算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，算法就是用计算机求解某一问题的方法，是能被机械地执行的动作或指令的有穷集合。算法的特征

2、确定性能行性输入输出有穷性算法是在有限步骤内求解某一问题所使用的一组定义明确的规则算法描述1自然语言描述法鸡兔同笼问题的算法用自然语言描述为：（1）输入任意整数a和偶数b（2）求出x=2a-b/2，y=b/2-a（3）输出：鸡有x只，兔有y只。 三个步骤依次进行，这是算法描述中的第一种结构：顺序结构实践1：时间转换输入一个以秒为单位的时间t，将其转换成x小时y分钟z秒形式。例如输入3800，则输出1小时3分20秒。用自然语言描述算法。求实根的算法用自然语言描述以下问题的算法：对于任意的实数a,b,c,求一元二次方程ax2bx+c的实根。求实根的算法（1）输入a,b,c（2）求DLTb2-4ac

3、（3）如果DLT0，则输出“无实根”，转（5）（4）否则，求两实根x1,x2，输出x1,x2（5）结束第三、四步选择进行，这是算法描述中的第一种结构：选择结构自然语言描述法的不足容易造成理解歧义描述算法太长，不够精练当算法中存在循环或分支较多时，不易清晰表示出来算法描述2.框图描述法常见框图有流程图和NS框图两种流程图描述法中使用的图形：起止框输入/出处理框判断框流程线连接点求实根的算法开始输入A、B和CDLT0?结束是否求两实根x1,x2输出”无实根”求DLTb2-4ac输出x1,x2顺序结构分支结构实践2：求三角形面积P11：实践(1)设计一个算法，实现如下功能：从键盘上输入三角形的三边长

4、a,b,c，如果能构成一个三角形，则输出其面积，否则输出“不能构成一个三角形！”的提示信息。试用流程图把算法描述出来。（计算三角形面积可用海伦公式）求所有水仙花数如果一个三位数，它的每位数字的立方和等于这个三位数，则称它为水仙花数。例如：15313 53 33，所以153是一个水仙花数。求所有水仙花数算法开始I1000?结束是否I100求出I的个位a,十位b和个位ca3+b3+c3=I?是输出III+1循环结构欧几里得算法-辗转相除法设给定的两个正整数为m和n，求它们的最大公约数的步骤为：(1)以m除以n,令所得余数为r。(2)若r=0,则输出结果n，算法结束；否则，继续步骤(3)。(3)令m

5、n，nr，并返回步骤(1)继续进行。将以上算法用流程图来描述实践3：韩信点兵中国有一本数学古书孙子算经也有类似的问题：今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？ 算法的伪代码描述 伪代码是采用一种类似于程序设计语言的代码来描述算法。基本指令： l 赋值指令：助记符 表达式； l 输出指令：输出 （表达式）； l 循环指令： while（条件表达式） 循环体l 条件指令： if （条件表达式） 指令序列1 else 指令序列2 求实根的伪代码输入a,b,cDLTb2-4acIf DLT0 then 输出“无实根”Else x1(-b+sqrt(DLT)/2a x2 (-b-sqrt(DLT)/2a 输出x1,x2Endif伪代码接近于程序，容易转化成程序，同时又使用自然语言，容易被理解。算法在解决问题中的地位与作用演示两种不同算法求最大公约数的程序运行效率算法是程序设计的核心，是灵魂。编程解题实际上是从人工解题用描述算法根