大学计算机基础大学计算机基础 (29).ppt

《大学计算机基础大学计算机基础 (29).ppt》由会员分享，可在线阅读，更多相关《大学计算机基础大学计算机基础 (29).ppt（21页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、算法概述问题导入过河河问题这页用二用二维动画替画替换问题：如何：如何设计一一个方案个方案，让这四个人以最短的四个人以最短的时间过桥。在漆黑的夜里，有四位旅行者来到一座桥边。这座桥非常狭窄，而且没有护栏。大家必须借助手电筒才能过桥。不幸的是，四个人只有一只手电筒，而桥窄得每次只能两个人通过。现在已知，如果单独过桥的话，四人分别需要的时间为1、2、5、8分钟；而如果两个人同时过桥，所需要的时间为走得较慢的那个人单独通过的时间。同学们，你能想到时间最短的方案吗？如果每人所需要的时间，改变为1、4、5、8分钟呢？过河河问题现在我在我们把把这个个问题推广：推广：如果有N（N大于等于4）个人，假设他们单独

2、过桥所需的时间各不相同。那么，在只有一只手电筒，并且每次最多两个人通过的情况下，怎样才能找到最快的过桥方案？现在我们假定，N个人单独过桥的时间分别是T1,T2,T3,Tn，且满足T1T2T3 Tn。过河河问题需要使用需要使用贪心策略的算法心策略的算法进行安排行安排01最快的两个人先过桥，以保证这两个人是能来回送手电筒的人02 让最快的人送手电筒的次数尽可能多03在某些方案中，次快的也可能会送手电筒04让过桥慢的人过桥次数尽可能少本章将介绍算法概念和描述、常用算法及编程基础。通过学习，同学们将具备利用计算机求解问题的基本能力。算法概述大象关冰箱大象关冰箱启启动汽汽车自制蛋糕自制蛋糕规划路划路线生

3、活中的算法生活中的算法在计算机科学中，算法是在有限的步算法是在有限的步骤内解决数内解决数学学问题的的过程程，是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，即算法是对计算机上执行的计算过程的具体描述。利用利用计算机求解算机求解问题的的过程程分析和抽象确定数据结构设计算法编程和调试得到结果一个有效的算法必一个有效的算法必须满足以下五个重要特性足以下五个重要特性01有穷性02确定性03输入04输出05可行性算法必须能在有限的时间内做完，即在任何情况下，算法必须能在执行有限个步骤之后终止，都不能陷入无穷循环中。01有穷性02确定性03输入04输出05可行性一个有效的算法必一个

4、有效的算法必须满足以下五个重要特性足以下五个重要特性算法中的每一个步骤，必须经过明确的定义，并且能够被计算机所理解和执行，而不能是抽象和模糊的概念，更不允许有二义性。01有穷性02确定性03输入04输出05可行性一个有效的算法必一个有效的算法必须满足以下五个重要特性足以下五个重要特性算法中要做的运算都是基本运算，能够被精确地进行。即算法中执行的任何计算都可以被分解为基本的运算步，每个基本的运算步都可以在有限的时间内完成。01有穷性02确定性03输入04输出05可行性一个有效的算法必一个有效的算法必须满足以下五个重要特性足以下五个重要特性算法至少有1个或多个输出值，反映对运算对象的处理结果，没有

5、输出的算法没有任何意义。01有穷性02确定性03输入04输出05可行性算法有0个或多个输入值一个有效的算法必一个有效的算法必须满足以下五个重要特性足以下五个重要特性算法中各个步骤的执行是有一定的顺序的，执行顺序是通过算法的控制结构决定的。算法的控制算法的控制结构包括构包括3种种选择结构顺序结构循环结构顺序序结构构最简单，是指各步骤按照先后顺序依次执行。选择结构构指执行到某一步骤时，根据条件判断的结果，选择不同的分支去执行。YN循循环结构构算法中需要反复执行的操作就可以利用循环结构来实现。当然循环结构的执行是有条件的，条件成立时，继续循环；条件不成立时，循环结束。一个计算机程序是算法的一个具体描述，同一个算法可以用不同语言编写的程序来描述。实现算法的程序应该具备如下特性：01 正确性02 可读性03 健壮性实现求解问题的功能，合法的输入对应正确的输出结果。程序代码易于理解，方便查错。输入非法数据时，程序给出相应处理。如报错返回等。