第一单元-算法.pptVIP

算法的基本概念 2、算法的基本要素 算法设计基本方法 列举法的运算量较大，但在有些实际问题 中很有效，如寻找路径、查找、有哪些信誉好的足球投注网站等问题。 列举法是计算机算法中的一个基础算法。 算法设计基本方法 2、归纳法 通过观察一些简单而特殊的情况，找出一般的关系，最后总结出有用的结论或解决问题的有效途径。 3、递推 从已知的初始条件出发，依次推出所要求的各中间结果和最后结果。本质上也属于归纳法。 算法设计基本方法 4、递归 将问题逐层分解，最后归结为一些简单的问题。解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合。 递归的基础也是归纳。 算法设计基本方法 例、编写一个过程，对于输入的参数n，依次打 印输出自然数1到n。 算法设计基本方法 5、减半递推技术 所谓“减半”是指将问题的规模减半，而问题的性质不变。所谓“递推”是指重复“减半”的过程。 6、回溯法 找出一个解决问题的线索，沿这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。 可处理复杂的数据结构。 算法的复杂度分析 算法的时间复杂度和空间复杂度（自学） 软件技术基础 算法 第一章 算法 算法的基本概念 算法设计基本方法 算法的复杂度分析 1、算法的概念及特点 算法是为解决某一特定类型问题规定的运算规则的有穷集合 有穷性 确定性 有效性 输入 输出 特 点 非无限执行，必须在有限步骤内结束 非二义，下一步必须是明确的 每一步是可执行的 外部输入零个或多个 至少一个 算法的基本概念 1）对数据对象的的运算和操作 算术运算 逻辑运算 关系运算 数据传输 2）算法的控制结构 即各操作之间的执行顺序 算法与程序 相似：都是解决问题的方法和步骤，是指令的集合 区别： 有穷性 描述方法 联系：程序用某种程序设计语言来实现算法 程序使用程序设计语言 算法可以使用框图及其他语言 算法的基本概念 类似： While(1){ …… } 的语句段，在程序中允许 但在算法中不允许 算法语言 算法应有严格的描述语言（确定性） 一般使用类PASCAL语言 在本课程中使用C++语言 要求描述一个算法时必须满足： 对输入和输出的描述 描述语句准确、无二义 保证算法的有穷性和有效性 算法的基本概念 算法设计基本方法 1、列举法 列举所有的可能情况，再检验哪些是需要的，哪些是不需要的。 常用于解决“是否存在”或“有多少种可能”等类型的问题。 例、设每只母鸡3元，每只公鸡2元，两只小鸡1元。 现要用100元钱买100只鸡，设计买鸡方案。 算法设计基本方法 #include iostream #include iomanip using namespace std; int main() { int i, j, k; for (i=0; i=33; i++) for (j=0; j=50-1.5*i; j++) { k=100-i-j; if (3*i+2*j+0.5*k==100.0) cout setw(5)i setw(5)j setw(5) k endl; } return 0; } #include iostream using namespace std; void wrt1(int n) { if (n!=0) {wrt1 (n-1); coutnendl;} return; } * * * * *