C语言程序设计基础课件 03 算法初步

算法初步C语言程序设计基础目录算法的基本概念算法的描述常用算法010203contents01算法的基本概念导例：猜猜商品价格问题描述某电视节目要求选手竞猜某件商品价格（整数），价格范围为1-1000元，每次会提示猜测价格偏高或偏低，若猜中商品归选手所有，需思考较快猜到价格的方法。问题分析存在三种方法。一是从1元开始依次递增猜测；二是随机猜测；三是先猜500元，根据提示再猜价格区间中间值。算法描述第一种方法：确定价格区间，从区间最小值开始猜测，若未猜中则递增1继续猜。第三种方法：确定价格区间，取中间值猜测，根据与正确价格比较结果调整区间继续猜。算法分析假设价格为875元，第一种方法需猜875次，第二种方法最好1次、最坏875次，第三种方法3次即可猜中，可见第三种方法更优。导例：过河游戏问题描述有狼、羊和白菜在一河岸，农夫船小每次只能载一样东西，且农夫不在时狼吃羊、羊吃白菜，需找出农夫将它们安全渡河的方法。问题分析农夫先带狼或白菜过河均不可行，先带羊过河可行，通过将位置用0、1表示，把问题转化为状态变化问题，列举各种渡河状态转换情况。算法分析解决问题过程即确定算法过程，将位置用数字表示并结合规则，可轻松求解。第三次渡河有两种可行情形，可自行分析另一种方案状态变化。算法定义与基本特征算法定义算法是有穷规则集合，规定了解决特定类型问题的运算序列，规定了任务执行或问题求解步骤，可进行数值或非数值计算。基本特征具有有穷性、确定性、输入、输出和能行性。有穷性指算法执行若干步后结束；确定性指步骤确切定义无歧义；输入指算法开始前有初值；输出指有与输入特定关系的结果；能行性指运算精确且能在有限时间完成。算法设计的基本过程分析问题开发程序首要是定义和理解问题，明确问题输入、输出及解决条件，此为程序设计关键。设计方案要找到解决问题办法，程序由算法和数据结构组成，算法研究解决问题步骤，数据结构研究数据逻辑关系，通过两者设计把握数据组织和解决问题步骤。编码和调试阶段将算法写成程序，把步骤转化为编程语言语句，通过编译、运行和输入测试数据检测算法和程序准确性。算法的评价标准正确性算法正确性是重要评价标准，对每个输入实例都能输出正确结果并停止的算法为正确算法。时间复杂度指执行算法所需时间，是问题规模n的函数，问题规模越大，执行时间增长率与函数增长率正相关。空间复杂度指算法消耗的内存空间，计算和表示方法与时间复杂度类似。可读性指算法可供人们阅读的容易程度。健壮性指算法对不合理数据输入的反应和处理能力，即容错性。02算法的描述导例：生活中的流程问题描述需将早上起床到准备出门上班、选择上班交通工具、上班路上等123路公交车这几个生活场景步骤以框图形式描述。（1）早上起床到准备出门上班的流程。（2）选择上班交通工具的流程。（3）上班路上等123路公交车的流程。问题分析分析各场景步骤，按先后顺序用框图和箭头表示，如起床流程按起床、穿衣等顺序，选择交通工具根据起床时间选择，等公交车按是否为123路判断。（1）早上起床到准备出门上班的流程：一般早上起床的流程为：先起床，然后穿衣，再刷牙、洗脸，最后吃早饭。这个过程中几个步骤是按上述的先后顺序完成的。（2）选择上班交通工具的流程：假设早上8点上班，坐公交车上班需要50分钟，出租车上班需要30分钟。根据早上起床的时间，如果比较晚可能会迟到，可以选择出租车出行；如果比较早，可以选择坐公交车出行。（3）上班路上等123路公交车的流程：在公交车站等公交车时，如果等到一辆公交车，先看看是不是123路，如果是，就上车；如果不是继续等下一辆，直到等到123路为止。问题实现用框图和箭头表示各场景流程，有多种情况选择时用菱形块表示。导例：猜猜商品价格的流程图问题描述将猜商品价格第三种方法的解决步骤用流程图形式描述。问题分析以框图形式表示更直观易懂。问题实现用框图描述，带箭头线表示流程，矩形框表示处理方法，菱形框表示条件，圆角矩形表示开始和结束。流程图分析读流程图从“开始”按箭头方向到“结束”，理解各步骤和条件判断。导例：猜猜商品价格的流程图问题求解的过程确定操作对象确定处理流程确定问题中处理的数据及其类型和组织形式。计算机处理问题有顺序、选择、循环结构，选择结构关键是确定分支条件和操作，循环结构关键是确定循环条件和循环体。010203常用算法导例：古堡算式问题福尔摩斯遇到算式ABC*?=CBA，需找出ABC代表的数字。问题描述用0-9数字代入A、B、C，1-9数字代入“？”，采用穷举法依次尝试判断算式是否成立。问题分析定义变量，按一定顺序尝试各数字组合，判断算式是否相等，用流程图描述过程。算法描述穷举法算法有4层循环，需9*10*9*9次判断，效率较低，但适合简单问题。穷举法需9*10*9*9次判断，效率较低，但适合简单问题。算法分析穷举法基本思想从所有可能情况中尝试出正确答案，有顺序列举、排列列举、组合列举等方法，以鸡兔同笼问题为例说明。实现方法用循环和条件语句逐步验证，分析问题时应缩小穷举范围提高效率。特点穷举法简单直接，适合小规模问题，效率低但易实现。导例：神殿寻宝神殿有9个门，房间可能有宝箱或9个门，需找到宝箱。问题描述进入房间处理过程相同，查看是否有宝箱，无则继续进入房间。问题分析用“寻宝()”表示进入房间过程，用循环和条件判断描述流程。算法描述采用递归算法，自己调用自己，直到找到宝箱。穷举法需9*10*9*9次判断，效率较低，但适合简单问题。算法分析递归算法定义用函数自身定义该函数，将大问题转化为相似小问题求解，需确定边界条件。以Fibonacci数列为例说明。特点直接或间接调用自身，有明确递归结束条件，描述简洁但运行效率低，递归次数过多易造成栈溢出。导例：大臣的旅费T国城市间有铁路连接，大臣旅费与走过距离有关，需找出城市间最多花费的路费问题描述列出路线计算总距离，用状态表示城市到其他城市最大距离，通过递推计算。问题分析用二维矩阵表示城市间铁路距离，通过循环和条件判断计算最大距离。算法描述计算过程中会反复计算子问题，算法中计算最大距离语句执行5*5*5次。穷举法需9*10*9