大学计算机——应用、计算与思维 课件 第3章 算法与程序设计.pptx

算法与程序设计第3章讲课人：*** 目录01中国古典数学02算法概述03算法策略04经典算法设计05程序设计 知识导图本章节主要为同学们介绍算法及程序设计的相关知识。程序员的主要任务是根据用户的需求为计算机设计算法。计算机的工作特点是可以快速地重复，因此，算法多是“重复”，表现为循环和递归。循环是有条件的重复。穷举与迭代最常见。嵌套的循环往往意味着“自顶向下，逐步求精”，多用于处理复杂的问题。递归算法是“规模上”的重复，可完美解决特定的问题。本章最后简要介绍了一些常见的查找与排序算法及程序设计语言。本章内容 中国古典数学第3章01 作为世界四大文明古国之一，中国从很早开始就发展出了自己的数学体系。商代的甲骨文上出现了完整的十进制，春秋时代严格的筹算已经成型并得到了广泛的应用，战国时代《考工记》中实用的几何知识流传到今天。《张丘建算经》：最小公倍数的应用、等差数列各元素互求、“百鸡术”。《周髀算经》：勾股术。《九章算术》：开平方和开立方的方法、一般一元二次方程(首项系数不是负)的数值解法。《海岛算经》：“割圆术”开创了中国古代圆周率计算方面的重要方法。 算法概述第3章02 3.2.1 算法的概念所谓算法，就是指完成某一特定任务所需要的具体方法和步骤的有序集合。“有序”说明算法中的步骤是有顺序关系的。同时，算法所描述的步骤也应该是“明确的”和“可执行的”，这样算法才可以实现。著名的计算机科学家尼古拉斯·沃斯（Niklaus Wirth）曾提出一个著名的公式： 程序=算法+数据结构 3.2.2 算法的特征 有穷性（Finiteness） 确切性（Definiteness） 输入项（Input） 输出项（Output） 可行性（Effectiveness） 3.2.3 算法的描述1. 自然语言表示法2. 伪代码表示法3. 流程图表示法4. N-S图表示法 算法策略第3章03 3.3.1 循环计算机的工作特点是可以高速地重复，因此在设计算法时常用循环（特定条件下的重复）解决问题。 1. 模拟重复以编程计算1+2+3+…+100的和为例来说明如用循环解决问题。先求1+2+3+4+5的和。1+2+3+4+5=3+3+4+5=6+4+5=10+5=15整个计算过程就是重复算加法。什么数在相加呢？前一次的和与新的加数。用存储单元sum存储和，存储单元i存储加数，计算过程就是把把sum中的数与i中的数相加，结果还存入sum中。这个过程可记为sum=sum+i;。 人工计算 1+2+3+4+5=3+3+4+5=6+4+5=10+5=15代码命令sum = 1,i = 2;sum = sum + i; i=i+1;sum = sum + i; i=i+1;sum = sum + i; i=i+1;sum = sum + i; i=i+1;计算过程的模拟 用循环计算sum = 1,i = 2;sum = sum + i;i=i+1;sum = sum + i;i=i+1;sum = sum + i;i=i+1;sum = sum + i;i=i+1;int sum = 1,i = 2;while(i <= 5){ sum = sum + i; i=i+1;} 1+2+3+4+5int sum = 1,i = 2;while(i <= 5){ sum = sum + i; i=i+1;}1+2+3+…+100int sum = 1,i = 2;while(i <= 100){ sum = sum + i; i=i+1;}用循环计算1+2+3+…+100 2. 穷举与迭代尝试所有可能的选项以找到正确答案的方法又称为穷举法。一百个僧人分一百个馒头，大僧每人分三个，小僧三人分一个，正好分完。问大小僧各几人？尝试所有的可能。大僧1人时，小僧（100-1）人，需要馒头3*1+(100-1)/3个，如果馒头的个数等于100，就找到了答案，输出大小僧的人数；否则，就不输出。大僧2人时，小僧（100-2）人，需要馒头3*2+(100-2)/3个，如果馒头的个数等于100，就找到了答案，输出大小僧的人数；否则，就不输出。……大僧33人时，小僧（100-33）人，需要馒头3*33+(100-33)/3个，如果馒头的个数等于100，就找到了答案，输出大小僧的人数；否则，就不输出。 穷举法整个过程可描述为。//大僧1人时当3 * 1 + (100 - 1) / 3 == 100时，输出大僧:1,小僧: 100 - 1;//大僧2人时当3 * 2 + (100 - 2) / 3 ==