3.4算法及其实现课件.ppt
3.4 算法及其实现算法及其实现什么是算法什么是算法v算法并不只是计算，它是解决问题的方法的精确描述。算法并不只是计算，它是解决问题的方法的精确描述。算法并不只是计算，它是解决问题的方法的精确描述。算法并不只是计算，它是解决问题的方法的精确描述。v算法是由有限个步骤组成的。算法是由有限个步骤组成的。算法是由有限个步骤组成的。算法是由有限个步骤组成的。v算法每一个步骤的含义必须明确没有二义性算法每一个步骤的含义必须明确没有二义性算法每一个步骤的含义必须明确没有二义性算法每一个步骤的含义必须明确没有二义性 。v同一问题算法可以有多种，但只取最优。同一问题算法可以有多种，但只取最优。同一问题算法可以有多种，但只取最优。同一问题算法可以有多种，但只取最优。算法的日常简单应用算法的日常简单应用v统筹方法平话及补充中统筹方法平话及补充中统筹方法平话及补充中统筹方法平话及补充中“泡茶泡茶泡茶泡茶”问题：问题：问题：问题：想要泡茶喝，情况是：开水没有，水壶要洗，茶想要泡茶喝，情况是：开水没有，水壶要洗，茶想要泡茶喝，情况是：开水没有，水壶要洗，茶想要泡茶喝，情况是：开水没有，水壶要洗，茶壶和茶杯要洗；火已生，茶叶有，怎么办？壶和茶杯要洗；火已生，茶叶有，怎么办？壶和茶杯要洗；火已生，茶叶有，怎么办？壶和茶杯要洗；火已生，茶叶有，怎么办？算法的日常简单应用算法的日常简单应用洗开 水壶洗茶壶洗茶杯拿茶叶灌凉水烧开水泡茶喝洗开 水壶灌凉水烧开水拿茶叶洗茶壶洗茶杯泡茶喝烧开水开水洗开洗开 水水壶灌凉水灌凉水洗茶洗茶壶洗茶洗茶杯杯拿茶拿茶叶叶泡茶喝泡茶喝 t算法的日常简单应用算法的日常简单应用v农夫过河问题：农夫过河问题：农夫过河问题：农夫过河问题：一个农夫带着一只狼，一只羊和一棵白菜过河。一个农夫带着一只狼，一只羊和一棵白菜过河。一个农夫带着一只狼，一只羊和一棵白菜过河。一个农夫带着一只狼，一只羊和一棵白菜过河。河边只有一条船河边只有一条船河边只有一条船河边只有一条船,由于船小由于船小由于船小由于船小,农夫一次只能带其中农夫一次只能带其中农夫一次只能带其中农夫一次只能带其中的一样过河。的一样过河。的一样过河。的一样过河。如无人看管如无人看管如无人看管如无人看管,狼要吃羊狼要吃羊狼要吃羊狼要吃羊,羊要吃菜。羊要吃菜。羊要吃菜。羊要吃菜。问农夫如何安排过河问农夫如何安排过河问农夫如何安排过河问农夫如何安排过河,才能使狼、羊、菜都安然无才能使狼、羊、菜都安然无才能使狼、羊、菜都安然无才能使狼、羊、菜都安然无恙。恙。恙。恙。农夫过河小游戏农夫过河小游戏渡河的方法与步骤渡河的方法与步骤vv第一步：农夫带着羊渡过河去；第一步：农夫带着羊渡过河去；vv第二步：农夫划船回来；第二步：农夫划船回来；vv第三步：农夫带着菜第三步：农夫带着菜(或狼或狼)渡过河去；渡过河去；vv第四步：农夫带着羊划船回来；第四步：农夫带着羊划船回来；vv第五步：农夫带着狼第五步：农夫带着狼(或菜或菜)渡过河去；渡过河去；vv第六步：农夫划船回来；第六步：农夫划船回来；vv第七步：农夫带着羊渡过河。第七步：农夫带着羊渡过河。如何用计算机解决问题如何用计算机解决问题vv当我们用计算机解决问题时，当我们用计算机解决问题时，当我们用计算机解决问题时，当我们用计算机解决问题时，首首首首先要分析问题先要分析问题先要分析问题先要分析问题，然后，然后，然后，然后根据根据根据根据问题的要求问题的要求问题的要求问题的要求选选选选择合适择合适择合适择合适的软件的软件的软件的软件。如。如。如。如果果果果现现现现有的软件能有的软件能有的软件能有的软件能满足满足满足满足我们我们我们我们的要求，我们会的要求，我们会的要求，我们会的要求，我们会直接直接直接直接用这用这用这用这些些些些软件来完成任务。例如：学校软件来完成任务。例如：学校软件来完成任务。例如：学校软件来完成任务。例如：学校财务处要制作一份工资表，工资表中许多数据，我们可以财务处要制作一份工资表，工资表中许多数据，我们可以财务处要制作一份工资表，工资表中许多数据，我们可以财务处要制作一份工资表，工资表中许多数据，我们可以用用用用ExcelExcelExcelExcel解决；学生要设计一个报刊设计，可以使用解决；学生要设计一个报刊设计，可以使用解决；学生要设计一个报刊设计，可以使用解决；学生要设计一个报刊设计，可以使用wordwordwordword；网络上的网页是使用网页制作工具完成的，记事本要输入网络上的网页是使用网页制作工具完成的，记事本要输入网络上的网页是使用网页制作工具完成的，记事本要输入网络上的网页是使用网页制作工具完成的，记事本要输入代码，代码，代码，代码，FrontpageFrontpageFrontpageFrontpage和和和和DreamweaverDreamweaverDreamweaverDreamweaver可以直接使用可视化工具。可以直接使用可视化工具。可以直接使用可视化工具。可以直接使用可视化工具。vv除除除除此此此此之之之之外外外外，现实生活现实生活现实生活现实生活中还有许多工作中还有许多工作中还有许多工作中还有许多工作往往比往往比往往比往往比较较较较特殊特殊特殊特殊，现现现现有有有有的软件不能很好的软件不能很好的软件不能很好的软件不能很好地地地地完成，完成，完成，完成，或者或者或者或者由由由由于于于于其他其他其他其他方面的方面的方面的方面的原原原原因无法使因无法使因无法使因无法使用，这就用，这就用，这就用，这就需需需需要我们要我们要我们要我们编写编写编写编写程序来解决问题。程序来解决问题。程序来解决问题。程序来解决问题。一个笼子里有鸡和兔，现在只知道里面一共有一个笼子里有鸡和兔，现在只知道里面一共有一个笼子里有鸡和兔，现在只知道里面一共有一个笼子里有鸡和兔，现在只知道里面一共有3535个头，个头，个头，个头，9494只脚，问鸡和兔各有多少只？只脚，问鸡和兔各有多少只？只脚，问鸡和兔各有多少只？只脚，问鸡和兔各有多少只？分析问题：设分析问题：设分析问题：设分析问题：设x x只鸡，只鸡，只鸡，只鸡，y y只兔，则只兔，则只兔，则只兔，则 X+Y=35 X+Y=35 2X+4Y=94 2X+4Y=94解方程组得：解方程组得：解方程组得：解方程组得：XX2323，Y Y1212鸡兔同笼问题鸡兔同笼问题鸡兔同笼问题鸡兔同笼问题一个笼子里有鸡和兔，现在只知道里面一共有一个笼子里有鸡和兔，现在只知道里面一共有一个笼子里有鸡和兔，现在只知道里面一共有一个笼子里有鸡和兔，现在只知道里面一共有3535个个个个头，头，头，头，9494只脚，问鸡和兔各有多少只？只脚，问鸡和兔各有多少只？只脚，问鸡和兔各有多少只？只脚，问鸡和兔各有多少只？编编程程程程时时，通常用，通常用，通常用，通常用变变量来表示可量来表示可量来表示可量来表示可变变化的已知量。化的已知量。化的已知量。化的已知量。用变量用变量用变量用变量a a表示头的总数，变量表示头的总数，变量表示头的总数，变量表示头的总数，变量b b表示脚的总数表示脚的总数表示脚的总数表示脚的总数方程组：方程组：方程组：方程组：X+Y=aX+Y=a 2X+4Y=b 2X+4Y=b解得方程组：解得方程组：解得方程组：解得方程组：X=2a-b/2，Y=b/2-a将变量将变量将变量将变量a a，b b视为容器，此程序将可以应用于不同已视为容器，此程序将可以应用于不同已视为容器，此程序将可以应用于不同已视为容器，此程序将可以应用于不同已知数的鸡兔同笼问题知数的鸡兔同笼问题知数的鸡兔同笼问题知数的鸡兔同笼问题设计算法设计算法v2.设计算法：设计算法：v输入输入a和和b的值的值v求求X=2a-b/2v求求Y=b/2-av输出输出X，Y的值的值v结束结束设计一个软件的步骤是：设计一个软件的步骤是：具体问题分析问题设计算法编写程序调试程序得到答案无无论论使用使用现现成的软件解决问题，还是自己成的软件解决问题，还是自己动动手编手编程解决问程解决问题，题，其实其实质质都是一样的：都是一样的：现现有的计算机软件同样也经有的计算机软件同样也经历历了这了这些些过程，过程，其差别其差别在于，用程序设计解决问题在于，用程序设计解决问题需需要我们要我们亲亲自自动动手手设计设计软件，软件，而而使用使用现现成的软件，是成的软件，是别人别人已经已经给给我们设计好了我们设计好了的。的。算法的描述算法的描述v自然语言自然语言v流程图流程图自然语言描述自然语言描述v输入输入a和和b的值的值v求求X=2a-b/2v求求Y=b/2-av输出输出X，Y的值的值v结束结束流程图描述流程图描述输入输入输入输入a a和和和和b b的值的值的值的值输出输出输出输出x,yx,y的值的值的值的值开始开始开始开始求求求求x=2a-b/2x=2a-b/2求求求求y=b/2-ay=b/2-a结束结束结束结束流程图也称程序框图，流程图也称程序框图，流程图也称程序框图，流程图也称程序框图，算法的一种图形化表算法的一种图形化表算法的一种图形化表算法的一种图形化表示方法。示方法。示方法。示方法。与自然语言相比，用与自然语言相比，用与自然语言相比，用与自然语言相比，用流程图描述算法形象、流程图描述算法形象、流程图描述算法形象、流程图描述算法形象、直观，更容易理解。直观，更容易理解。直观，更容易理解。直观，更容易理解。流程图流程图图形图形图形图形名称名称名称名称功能功能功能功能开始结束开始结束开始结束开始结束表示算法的开始或结束表示算法的开始或结束表示算法的开始或结束表示算法的开始或结束输入输出输入输出输入输出输入输出表示算法中变量的输入或输出表示算法中变量的输入或输出表示算法中变量的输入或输出表示算法中变量的输入或输出处理处理处理处理表示算法中变量的计算与赋值表示算法中变量的计算与赋值表示算法中变量的计算与赋值表示算法中变量的计算与赋值判断判断判断判断表示算法中的条件判断表示算法中的条件判断表示算法中的条件判断表示算法中的条件判断流程线流程线流程线流程线表示算法中的流向表示算法中的流向表示算法中的流向表示算法中的流向连接点连接点连接点连接点表示算法中的转接表示算法中的转接表示算法中的转接表示算法中的转接求和问题流程图求和问题流程图开始开始开始开始s=s+is=s+ii10i10输入输入输入输入i=1i=1，总和，总和，总和，总和s=0s=0结束结束结束结束输出输出输出输出s s的值的值的值的值i=i+1i=i+1是是是是否否否否计算：算：1+2+3+10分部演示：分部演示：i=1,s=0+1,i=1+1i=2,s=1+2,i=2+1i=3,s=3+3,i=3+1i=9,s=+9,i=9+1i=10,s=+10,i=10+1i=11,跳出循环，输出跳出循环，输出s的的值，值，s=55程序的基本结构程序的基本结构v顺序结构顺序结构v选择结构选择结构v循环结构循环结构课后思考后思考求和问题求和问题1+2+3+10的算法流程图是否唯一，的算法流程图是否唯一，如不是，请写出不同于例子中的算法流程图。如不是，请写出不同于例子中的算法流程图。
