1、v程序设计基础从问题到程序（第3版）第 2 章 算法与计算思维本章主要内容计算思维程序的灵魂算法算法是计算机科学的重要基石，同时也是计算机科学研究的一项永恒主题。在计算机无处不在的现代社会，对于非计算机专业的学生，学会读懂算法，掌握计算思维，应该是一项必备的基本技能，对于计算机相关专业的学生，学会读懂并设计算法，掌握并运用计算思维，应该是一项最基本的要求。什么是算法？算法：对特定问题求解步骤的一种描述，是指令的有限序列。此外，构成算法的求解步骤必须满足以下条件：1.有穷性;2.确定性;3.可行性。算算 法（法（y=f(x)）有穷性：在合理时间内结束；有穷性：在合理时间内结束；确定性：不存在二义
2、性；确定性：不存在二义性；可行性：计算机可实现；可行性：计算机可实现；输入输入输出输出2.1 程序的灵魂算法算法不是问题的答案，而是解决问题的操作步骤，执行这个操作步骤就能获得问题的答案。如何描述算法?描述算法：算法设计者在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来。使用算法：算法使用者知道如何调用算法。例：欧几里德算法辗转相除法求两个自然数的最大公约数mnr 欧几里德算法欧几里德算法2.1 程序的灵魂算法描述算法的方法自然语言步骤1：将m除以n得到余数r；步骤2：若r等于0，则n为最大公约数，算法结束；否则执行步骤3步骤3：将n的值放在m中，将r的值放在n中；步骤4：
3、重新执行步骤1；优点：容易理解，缺点：冗长、二义性使用方法：粗线条描述算法思想 注意事项：避免写成自然段2.1 程序的灵魂算法图形符号名 称含 义起止框表示算法的开始或结束处理框表示处理或运算等功能输入/输出框表示进行输入/输出操作判断框根据条件是否满足决定执行两条路径中的某一条路径控制流表示算法执行的路径，箭头代表方向N开始开始输入输入m和和n r=m%nr=0m=n；n=r 输出输出n结束结束Y描述算法的方法程序流程图2.1 程序的灵魂算法伪代码：介于自然语言和程序设计语言之间。处理和条件处理和条件 结构、语句和控制成分结构、语句和控制成分 描述算法的方法伪代码step1 r=m%n;st
4、ep2 循环直到r=0 step2.1 m=n;step2.2 n=r;step2.3 r=m%n;step3 输出n;优点：表达能力强，抽象性强，容易理解，被称为算法语言 使用方法：7 22.1 程序的灵魂算法例2.1 用伪代码描述求解下列问题的算法：（1）两个瓶子A和B分别盛放酱油和醋，要求将A瓶和B瓶的液体互换，即A瓶盛放醋B瓶盛放酱油。step1:将将A瓶的酱油倒入瓶的酱油倒入C瓶，即瓶，即C A；step2:将将B瓶的醋倒入瓶的醋倒入A瓶，即瓶，即A B；step3:将将C瓶暂存的酱油倒入瓶暂存的酱油倒入B瓶，即瓶，即B C；（2）将三个数由小到大排序。step1:如果如果xy，则将
5、，则将x和和y交换；交换；step2:如果如果zx，则，则temp z；z y；y x；x temp；否则，如果否则，如果zy，则将，则将y和和z交换；交换；step3:依次输出依次输出x,y,z；2.1 程序的灵魂算法（3）在一个含有n个元素的集合中查找最大值元素。step1:max 第第1个元素；个元素；step2:初始化被比较元素的序号初始化被比较元素的序号i 2；step3:当当i小于等于小于等于n时重复执行下述操作：时重复执行下述操作：step3.1:如果第如果第i个元素大于个元素大于max，则，则max 第第i个元素；个元素；step3.2:i i+1；step4:输出输出max；
6、例2.1 用伪代码描述求解下列问题的算法：2.1 程序的灵魂算法如何评价算法？时间和空间效率：一个好算法应该具有较短的执行时间并占用较少的辅助存储空间。算法的复杂性：对算法所需时空资源的一种度量，所需资源越多，算法的复杂性就越高；反之，算法的复杂性就越低。对于给定的实际问题，设计出复杂性尽可能低的算法是算法设计者需要考虑的一个重要目标。当给定的问题有多种算法时，选择复杂性最低的算法，是选择算法时应遵循的一个重要准则。2.1 程序的灵魂算法如何评价算法？定义2-1 若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n)（或称算法在O(f(n)中）。2.1
7、程序的灵魂算法算法的重要性例2.3 用短除法和欧几里得算法求两个自然数的最大公约数，请通过一个具体实例比较两个算法的效率。2.1 程序的灵魂算法对于两个自然数48和36，短除法须进行12次求余操作（对于12和9，试除2和3得到公因子3；对于4和3，试除2和3后结束），而欧几里得算法只进行2次求余操作，程序设计的一般过程2.2 计算思维问 题算 法程 序想 法抽象模型基本思路数据表示数据处理程序语言编程环境人（设计方案）计算机(执行方案)程序设计实例鸡兔同笼问题【问题】笼子里共有 M 只头 N 只脚，问鸡和兔子各有多少只？【算法】设变量chicken表示鸡的个数，rabbit表示兔子的个数，算法
8、如下：step1:chicken从从0M重复执行下述操作：重复执行下述操作：step1.1:rabbit=M chicken;step1.2:如果如果(2*chicken+4*rabbit等于等于N)，则跳出循环，则跳出循环;step1.3:chicken+;step2:如果是提前跳出循环，则输出如果是提前跳出循环，则输出chicken和和rabbit的值的值;否则输出否则输出“无解无解”;x+y=M2x+4y=N且满足0 x,y M【想法】设鸡有 x 只兔子有 y 只，则有如下方程组成立：#include /*使用库函数printf和scanf*/*空行，下面是主函数*/int main()
9、int M,N;/*M存储头的个数，N存储脚的个数*/int chicken,rabbit;/*chicken存储鸡的个数，rabbit存储兔子的个数*/printf(“请输入头的个数和脚的个数:”);/*输出提示信息*/scanf(%d%d,&M,&N);/*从键盘接收两个整数*/for(chicken=0;chicken=M;chicken+)/*依次进行试探*/rabbit=M chicken;if(2*chicken+4*rabbit=N)break;/*方程组已解，跳出循环*/if(chicken=M)/*如果是提前跳出循环*/printf(鸡有%d只，兔子有%d只n,chicken
10、,rabbit);else printf(输入数据不合理，无解n);return 0;/*将0返回操作系统，表明程序正常结束*/【程序】以chicken作为循环变量，依次试探变量chicken和rabbit的取值是否满足方程组，程序如下：程序设计实例鸡兔同笼问题程序设计与计算思维2.2 计算思维计算思维：计算思维：基于计算机科学的概念体系进行问题求解、系统设计，以及理解人类行为等涵盖计算机科学之广度的一系列思维活动。程序的基本框架2.2 计算思维IPO框架：程序一般由三部分组成：输入（Input）、处理（Process）和输出（Output）。所谓输入/输出是以计算机主机为主体而言的，从计算机向外部输出设备（如显示器、打印机、磁盘等）输出数据称为输出，从外部输入设备（如键盘、鼠标、扫描仪、磁盘等）向计算机输入数据称为输入。程序的基本框架2.2 计算思维输入部分处理部分输出部分#include int main()int m,n,r;printf(请输入两个正整数：);scanf(%d%d,&m,&n);r=m%n;while(r!=0)m=n;n=r;r=m%n;printf(最大公约数是：%dn,n);return 0;
