算法部分 学习QQ群，172237221 11
学习QQ群：172237221 11 算法部分
1、算法的基本概念（汉诺塔的例子） 开始 2090-y N y=2000 Y不能被 4 y4的余数为0 Yes No N y/100的余数为0 Yes No Y不能被 N 打印y 100整除 “不是润年 y400的余数为0 输出y 输出y Y不能被 Yes No 不是闰年 打印y 40除 是闰年 “是国年 输出y 输出y 打y 是闰年 不是闰年 “不是闰华” y=y+1 y+l-y 直到y大于2500 3y>250阳 传统流程图 N-S结构化流程图 学习QQ群：172237221 12
学习QQ群：172237221 12 1、算法的基本概念（汉诺塔的例子） ◼ 算法是 对特定问题求解步骤的一种描述，它是指令的有 限序列，其中每一条指令表示一个或多个操作。它是一组 严谨地定义运算顺序的规则，并且每一个规则都是有效的， 且是明确的，此顺序将在有限的次数下终止。 ◼ 描述算法 的工具通常有传统流程图、N-S结构化流程图、 算法描述语言等； ◼ 算法５个重要特性 可行性、确定性、有穷性、输入和输出（拥有足够的情报） 传统流程图 N-S结构化流程图
2、算法的基本要素 (1)对数据对象的运算和操作： >算术运算 >逻辑运算 t=t米i >关系运算 >数据传输 (2)算法的控制结构： >算法中各操作之间的执行顺序： >一个算法一般可以用顺序、选择、循环三种基本结构组合 而成。 学习QQ群，172237221 14
学习QQ群：172237221 14 2、算法的基本要素 (1) 对数据对象的运算和操作： ➢ 算术运算 ➢ 逻辑运算 ➢ 关系运算 ➢ 数据传输 (2) 算法的控制结构： ➢ 算法中各操作之间的执行顺序； ➢ 一个算法一般可以用顺序、选择、循环三种基本结构组合 而成
3、算法设计的基本方法及例子 ■列举法（列出所有可能，再逐一检验，得到符合条件的结果）百钱买百鸡 ■归纳法（通过特殊情况，经过分析，最后找出一般关系） ■递推（从已知的初始条件出发，逐步推算，得到结果)猴子分食桃子 ·递归（将问题逐层分解，最后归结为一些最简单的问题）求年龄问题 ·减半递推（重复将问题的规模减半，而问题性质不变）二分法求方程实根 ■回溯法（以最优方式向前试探，如果失败，则后退再选）八皇后问题 学习QQ群：172237221 15
学习QQ群：172237221 15 3、算法设计的基本方法及例子 ◼ 列举法（列出所有可能，再逐一检验,得到符合条件的结果）百钱买百鸡 ◼ 归纳法（通过特殊情况，经过分析，最后找出一般关系） ◼ 递推（从已知的初始条件出发，逐步推算，得到结果）猴子分食桃子 ◼ 递归（将问题逐层分解，最后归结为一些最简单的问题）求年龄问题 ◼ 减半递推（重复将问题的规模减半,而问题性质不变）二分法求方程实根 ◼ 回溯法（以最优方式向前试探，如果失败，则后退再选）八皇后问题
3、算法的复杂度 for i=1 to n t=t*i endfor ■()时间复杂度 >依据算法编制的程序在计算机上运行时所消耗的时间来度 量。通常有事后统计法和事前分析估算法。 >一个算法是由控制结构（顺序、分支和循环)和原操作构 成的，算法时间取决于两者的综合效果。 >算法中基本操作重复执行次数和算法执行时间同步增长， 称作算法的时间复杂度。 ？为何研究的是“算法的时间复杂度”，而非“算法的执行时间 学习QQ群，172237221 16
学习QQ群：172237221 16 3、算法的复杂度 ◼ (1)时间复杂度 ➢ 依据算法编制的程序在计算机上运行时所消耗的时间来度 量。通常有事后统计法和事前分析估算法。 ➢ 一个算法是由控制结构（顺序、分支和循环）和原操作构 成的，算法时间取决于两者的综合效果。 ➢ 算法中基本操作重复执行次数n和算法执行时间同步增长， 称作算法的时间复杂度。 ? 为何研究的是 “算法的时间复杂度”，而非“算法的执行时间