第7章算法与程序设计课件

第第7 7章章 程序设计基础程序设计基础大学计算机基础大学计算机基础课用课件课用课件第7章程序设计基础大学计算机基础课用课件一一程序设计基础程序设计基础二二学习内容学习内容典型算法典型算法一程序设计基础二学习内容典型算法1.程序：程序：是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。程序是程序设计的最终产物。计算机程序设计又称编程（程序是程序设计的最终产物。计算机程序设计又称编程（Programming），是一门编写和设计计），是一门编写和设计计算机程序的科学和艺术。算机程序的科学和艺术。一一.程序设计基础程序设计基础1.程序：是为实现特定目标或解决特定问题而用计算机语言编写的2.2.计算机语言计算机语言高级语言高级语言机器语言机器语言汇编语言汇编语言低级语言低级语言计算机语言计算机语言面向问题的语言面向问题的语言面向过程的语言面向过程的语言面向对象的语言面向对象的语言C C、PascalPascal、FortranFortranVisual FoxProVisual FoxProC+C+、Java Java2.计算机语言高级语言机器语言汇编语言低级语言计算机语言面 机器语言机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。机器语言的所有指令都是由机器语言的所有指令都是由0 0、1 1组成的二进制。组成的二进制。操作码操作码操作数操作数例如，计算例如，计算A=15+10A=15+10的机器语言程序如下：的机器语言程序如下：10110000 00001111 10110000 00001111 把把1515放到累加器放到累加器A A中中00101100 00001010 1000101100 00001010 10与累加器与累加器A A的值相加，结果仍放入的值相加，结果仍放入A A中中11110100 11110100 结束，停机结束，停机格式格式机器语言机器语言是用二进制代码表示的计算机能直接识别和执行的一 汇编语言汇编语言用一些简洁的英文字母、符号串来替代一个特定的指令的二进制串，例如，用一些简洁的英文字母、符号串来替代一个特定的指令的二进制串，例如，用用“ADD”“ADD”代表加法，代表加法，“MOV”“MOV”代表数据传递等等。代表数据传递等等。例如，计算例如，计算A=15+10A=15+10的汇编程序如下：的汇编程序如下：MOV A,15 MOV A,15 把把1515放到累加器放到累加器A A中中ADD A,10 10ADD A,10 10与累加器与累加器A A的值相加，结果仍放入的值相加，结果仍放入A A中中HLT HLT 结束，停机结束，停机汇编语言汇编语言用一些简洁的英文字母、符号串来替代一个特定的指 高级语言高级语言例如，计算例如，计算A=15+10A=15+10的的C C语言程序如下：语言程序如下：#include#include main()main()int int a;a;a=15+10;a=15+10;printf(“%d”,a);printf(“%d”,a);return 0;return 0;高级语言lC程序由函数构成，有且有一个主函数程序由函数构成，有且有一个主函数l程序执行时总是从程序执行时总是从main()函数开始函数开始l语句必须以语句必须以“；”结束，书写格式自由结束，书写格式自由l“#”开头的为编译预处理命令开头的为编译预处理命令l利用利用/*/作为注释作为注释高级语言例如，计算A=15+10的C语言程序如下：#i机器语言机器语言高级语言高级语言书写书写翻译翻译执行执行编译编译是指事先是指事先编好的一个称好的一个称为编译程序的机器程序的机器语言程序，通言程序，通过编译程序把高程序把高级语言言书写的写的源程序整个地翻源程序整个地翻译成用机器成用机器语言表示的与之等价的目言表示的与之等价的目标程序。程序。解释解释程序是在源程序程序是在源程序进入入计算机算机时，通，通过解解释程序程序边扫描描边解解释，逐句，逐句输入，逐句翻入，逐句翻译，计算机一句句算机一句句执行，并不行，并不产生目生目标程序。程序。机器语言高级语言书写翻译执行编译是指事先编好的一个称为编译程共用体共用体数据类型数据类型基本类型基本类型整整型型实型实型字符型字符型单精度单精度双精度双精度非基本类型非基本类型数组数组结构体结构体指针类型指针类型枚举型枚举型3.3.数据类型数据类型共用体数据类型基本类型整型实型字符型单精度双精度非基本类型数l整型整型：int(如如0,67,-2)l实型：实型：float、double(如如2.3,1.2e-5)l字符型：字符型：char(如如z,3,$,n)用用开头的字符为转义字符开头的字符为转义字符,代表代表1个字符个字符l字符串：字符串：chara(如如UKM,1,5a)数据类型数据类型整型：int(如0,67,-2)数据类型l变量必须先声明，后使用变量必须先声明，后使用 变量变量变量必须先声明，后使用变量l变量地址变量地址变量地址数组l数组的输入与输出数组的输入与输出int i,a5;for(i=0;i5;i+)scanf(“%d”,&ai);for(i=0;i5;i+)printf(“%d”,ai);l数组元素求和数组元素求和int i,sum=0,a5=1,2,3,4,5;for(i=0;i5;i+)sum=sum+ai;数组数组的输入与输出数组元素求和l结构化程序设计结构化程序设计l面向对象的程序设计面向对象的程序设计4.4.程序设计方法程序设计方法结构化程序设计4.程序设计方法l自顶向下自顶向下l逐步求精逐步求精l模块化模块化l限制使用限制使用goto语句语句结构化程序设计结构化程序设计自顶向下结构化程序设计ABBAPPA顺序结构顺序结构选择结构选择结构循环结构循环结构程序的三种主要结构程序的三种主要结构PA当型循环当型循环直到型循环直到型循环ABBAPPA顺序结构选择结构循环结构程序的三种主要结构PA一.顺序结构#include /*使用标准函数库中的输入输出函数时需引用该头文件*/main()printf(Hello,World!n);程序员的第一个程序一.顺序结构#include/*使用顺序结构1.输入整数输入整数a、b并求和并求和#includemain()int a,b;printf(Please input a and b:n);scanf(%d,%d,&a,&b);/*从键盘输入从键盘输入a、b的值（以空格或者回车分隔）的值（以空格或者回车分隔）*/printf(a+b=%dn,a+b);顺序结构输入整数a、b并求和#include=a&a=z)a=a-32;printf(“%cn”,a);1.判断输入的一个字符，如果是小写字母，变成大写后输出判断输入的一个字符，如果是小写字母，变成大写后输出#include“stdio.h”1.判断输入的一个#includemain()inta,b;printf(Pleaseinput2numbers:);scanf(%d%d,&a,&b);if(ab)printf(%d,%d,a,b);elseprintf(%d,%d,b,a);2.2.任意给定两个数任意给定两个数a a，b b，将它们按从大到小的次序进行排序。，将它们按从大到小的次序进行排序。#include2.任意给定两个数a，b，#includemain()inta;printf(“Pleaseinputthedayyouwanttodate:”）;scanf(%d,&a);if(a=1|a=3|a=5)printf(NO);elseprintf(YES);3.3.晶晶约会：周一、三、五均有课晶晶约会：周一、三、五均有课#include3.晶晶约会：周一、三4.4.判断输入的年份是否为闰年判断输入的年份是否为闰年main()int year;printf(Please input the year:);scanf(%d,&year);if(year%4=0&year%100!=0|year%400=0)printf(%d is a leap year.n,year);else printf(%d is not a leap year.n,year);main()【例例】输入输入5组三角形的三组三角形的三 条边长，对每组数据进行判断，如果能构成三角形则条边长，对每组数据进行判断，如果能构成三角形则计算三角形的面积，否则，输出计算三角形的面积，否则，输出“不能构成三角形不能构成三角形”。YNY开始开始输入三条入三条边长计算面算面积并并输出出结束束输出相出相应信息信息构成三角形？构成三角形？循循环变量量i=1i5？i=i+1N三.控制结构【例】输入5组三角形的三条边长，对每组数据进行判断，如果能循环控制#includemain()intsum=0,n=1;for(n=1;n=10;n+)sum=sum+n;printf(sum=%dn,sum);循环控制#include循环控制#include“stdio.h”main()intscore,sum=0,i;floataverage;for(i=1;i=10;i+)printf(“nInputNo.%dscore:”,i);scanf(%d,&score);sum=sum+score;average=sum/10;printf(naverage=%fn,average);循环控制#include“stdio.h”#include#include#includemain()inti,g,j=1;longt;srand(time(NULL);i=rand()%100+1;printf(Pleaseinputyournumber（1-100）：）：);scanf(%d,&g);t=time(NULL);while(g!=i)if(gi)printf(nThenumberistoobig,pleaseinputagain：);if(gi)printf(nThenumberistoosmall,pleaseinputagain：);scanf(%d,&g);j+;t=time(NULL)-t;printf(nCongratulations！Yougottherightanswerwith%dtimes，uesed%dsecond。n,j,t);lsrand（time（NULL）使得随机数种子随时间的变化而变化。ltime函数可以获取当前的系统时间，返回从CUT（Coordinated Universal Time）时间1970年1月1日00:00:00到当前时刻的秒数。lrand()返回从0-32767的整数lsrand 和 rand 应该组和使用#includesrand（ti算法（算法（Algorithm）是一组明确的、可以执行的步骤的有序集合。）是一组明确的、可以执行的步骤的有序集合。l有穷性有穷性l确切性确切性l有有0个或多个输入个或多个输入l有有1个或多个输出个或多个输出l有效性有效性二二.算法算法算法（Algorithm）是一组明确的、可以 算法评价算法评价l正确性正确性l时间复杂度时间复杂度（计算机上运行所花费的时间）*l空间复杂度空间复杂度（算法运行过程中临时占用的存储空间的大小）测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作计算对运行时间有消耗的基本操作（如（如“运算运算”、“条件比较条件比较”、“变量代入变量代入”）的执行次数）的执行次数，运行时间与该计数成正比。算法的复杂度标记方法一般采用“O记法记法”。在O记法中，算法的复杂度是以处理对象数据的数量n为基准来记述的。算法评价正确性测定运行时间最可靠的方法就是计算【例例】求求1+2+3+1001+2+3+100 普通求和中，数据量为n时，时间复杂度是1+1+(n+1)+n+n=3n+3，操作次数为3n+3。当n无限增大时，n的系数3和需要加的3均可忽略，因此记做时间复杂度时间复杂度为为O(n)。解决方案1（普通求和）intsum=0,n=100;for(inti=1;isum；步骤2：使i为1；步骤3：将sum与i相加，结果仍放到变量sum中，写成sum+i=sum；步骤4：使i的值加1，即i+1=i；步骤5：如果i的值不大于11（i10），返回重新执行第3步和其后的步骤4和步骤5；否则，算法结束，sum的值即为所求。方法一：方法一：步骤1：先求1与2的和，得到结果3；步骤2：将步骤1得到的和与3相加，得到结果6；步骤3：将步骤2得到的和与4相加，得到结果10；步骤9：将步骤8得到的和与10相加，得到结果55。用自然语言描述算法设变量sum为被加数，变量i为加数，用循流程图是通过箭头相互连接的几何图形来表达的方法。流程图是通过箭头相互连接的几何图形来表达的方法。ANSI规定的一些常用流程图符号。起止框输入输出框判断框处理框流程线1.1.认识算法认识算法算法的算法的描述工具描述工具流程图是通过箭头相互连接的几何图形来表达的方法。ANSI规定sum=0n=1n=10sum=sum+nn=n+1输出出sumNY结束束开始开始【示例示例7-1】求求1+2+3+10，即，即流程图流程图sum=0，n=1sum=sum+nn=n+1输出输出sum的值的值当当i=10时，做，做N-S图图用流程图用流程图/N-S/N-S图表示算法图表示算法sum=0n=10sum=sum+n输出sumNY结束开始【示例示例7-1】求求1+2+3+10，即，即#include main()int sum=0,n=1;for(n=1;n=10;n+)sum=sum+n;printf(sum=%dn,sum);用计算机语言表示算法用计算机语言表示算法【示例7-1】求1+2+3+10，即#include【算法思想算法思想】l扫描整个序列，从中选出最小的元素，将它与序列的第一个元素交换；l然后再在余下的元素中找出最小数据的元素，与序列的第二个元素相互交换位置l然后对剩下的序列采用同样的方法，直到序列空为止。2.经典算法 排序算法：选择排序【算法思想】2.经典算法排序算法：选择排序#includemain()inti,index,k,n,temp,a5;printf(“Pleaseinput5numbers:n”);for(k=0;k5;k+)scanf(%d,&ak);for(k=0;k4;k+)index=k;for(i=k+1;i5;i+)if(aiaindex)index=i;if(index!=k)temp=aindex;aindex=ak;ak=temp;内循环内循环外循环外循环选择法排序选择法排序#include内循环外循环选择法排序printf(n);for(k=0;k5;k+)printf(%d,ak);printf(n);【算法思想算法思想】l在每一轮的排序过程中从第一个数开始，相邻两数依次比较，当发现前一个数据比后一个数据大时，即将这两个数据进行互换。l较小的数据就会逐个向前移动，大者往后移动，最后将序列中的最大值换到了序列的最后。经典排序算法：冒泡法经典排序算法：冒泡法排序【算法思想】经典排序算法：冒泡法排序#includemain()inti,j,n=5,temp,a5=18,6,3,15,2;printf(theoldarrayisn);for(i=0;in;i+)printf(%d,ai);for(i=0;in-1;i+)for(j=0;jaj+1)temp=aj;aj=aj+1;aj+1=temp;printf(nthenewarrayisn);for(i=0;in;i+)printf(%d,ai);冒泡法排序冒泡法排序#include冒泡法排序设数组为设数组为an：1.初始时，a0自成1个有序区，无序区为a1.n-1。令i=12.将ai并入当前的有序区a0i-1中形成a0i的有序区间。3.i+并重复第二步直到i=n-1。排序完成。经典排序算法：插入法经典排序算法：插入法排序【算法思想算法思想】每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。设数组为an：经典排序算法：插入法排序【算法思想】main()inti,j,n=7,temp,a7=12,15,9,20,6,31,24;for(i=1;in;i+)if(ai=0&ajtemp;j-)aj+1=aj;aj+1=temp;插入法排序插入法排序插入法排序【算法思想算法思想】l逐一将数组的数据与输入数进行比较l如果相等，说明找到，宣布查找成功，记录数组下标，算法结束；l如果不相等，说明没有找到，此时应判断是否还有剩余的数据，如果还有剩余的数据则继续和剩余的数据比较，如果没有剩余的数据，则宣布查找失败，算法结束输入：入：2 9 8 10 6查找：找：9输出：出：2输入：入：2 9 8 10 6查找：找：7输出：出：Not Found 经典查找算法：顺序查找经典查找算法：顺序查找-输入一组数据，再输入需要查找的数x，如果找到，输出相应的位置，否则，输出Not Found。【算法思想】输入：298106输入：2#includemain()inti,x,a5;printf(Pleaseinput5numbers:n);for(i=0;i5;i+)scanf(%d,&ai);printf(Pleaseinputthenumberyouwanttofind:n);scanf(%d,&x);for(i=0;i=5)printf(Thereisnosuchnumber);顺序查找顺序查找#include顺序查找经典查找算法：折半查找经典查找算法：折半查找（数据已经排好序）（数据已经排好序）输入：10 17 20 22 31 44 51 55 68查找：20【算法思想算法思想】数据存放在数组中，被查找数据放到x变量中，t表示查找范围的起点位置，b代表查找范围的末尾，m id表示查找范围的中间位置，mid=(t+b)/2。第1次tmidb第2次tmidb第3次tmidb数据101720223144515568位置（下标）012345678经典查找算法：折半查找（数据已经排好序）输入：1017#includemain()inti,x,n,left=0,right=4,mid=0;inta5=-1,2,6,7,10;printf(Pleaseinputthenumberyouwanttofind:n);scanf(%d,&x);for(i=0;i5;i+)mid=(left+right)/2;if(amid=x)printf(Found%datposition%dn,x,mid+1);break;elseif(xright)printf(Nofoundn);折半查找折半查找#include折半查找递归算法问题：问题：有有5个人坐在一起，个人坐在一起，问第五个人多少岁？他说比第问第五个人多少岁？他说比第4个人大个人大2岁。岁。问第问第4个人岁数，他说比第个人岁数，他说比第3个人大个人大2岁。岁。问第三个人，又说比第问第三个人，又说比第2人大两岁。人大两岁。问第问第2个人，说比第一个人大两岁。个人，说比第一个人大两岁。最后问第一个人，他说是最后问第一个人，他说是10岁。请问第五个人多大？岁。请问第五个人多大？递归算法问题：有5个人坐在一起，程序分析：程序分析：利用递归的方法，递归分为回推和递推两个阶段。要想知道利用递归的方法，递归分为回推和递推两个阶段。要想知道第五个人第五个人岁数，需知道岁数，需知道第四人的岁数第四人的岁数，依次类推，推到，依次类推，推到第一人（第一人（10岁）岁），再往回推。，再往回推。程序分析：利用递归的方法，递归分为回推和递推两个阶段。要想知intage(intn)intc;if(n=1)c=10;elsec=age(n-1)+2;returnc;main()printf(%d,age(5);intage(intn)intc;思考：思考：n!问题思考：n!问题来源大学计算机基础大学计算机基础王移芝等，高等教育出版社王移芝等，高等教育出版社大学计算机基础大学计算机基础姜永玲等，清华大学出版社（新版）姜永玲等，清华大学出版社（新版）来源大学计算机基础王移芝等，高等教育出版社