第7章算法与程序设计

1、第第7 7章章 程序设计基础程序设计基础大学计算机基础大学计算机基础课用课件课用课件一一程序设计基础程序设计基础二二学习内容学习内容典型算法典型算法1.程序：程序：是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。程序是程序设计的最终产物。计算机程序设计又称编程（程序是程序设计的最终产物。计算机程序设计又称编程（Programming），是一门编写和设计计），是一门编写和设计计算机程序的科学和艺术。算机程序的科学和艺术。一一. .程序设计基础程序设计基础2.2. 计算机语言计算机语言高级语言高级语言机器语言机器语

2、言汇编语言汇编语言低级语言低级语言计算机语言计算机语言面向问题的语言面向问题的语言面向过程的语言面向过程的语言面向对象的语言面向对象的语言C C、PascalPascal、FortranFortranVisual FoxProVisual FoxProC+C+、 Java Java 机器语言机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。机器语言的所有指令都是由机器语言的所有指令都是由0 0、1 1组成的二进制。组成的二进制。操作码操作码操作数操作数例如，计算例如，计算A=15+10A=15+10的机器语言

3、程序如下：的机器语言程序如下：10110000 00001111 10110000 00001111 把把1515放到累加器放到累加器A A中中00101100 00001010 1000101100 00001010 10与累加器与累加器A A的值相加，结果仍放入的值相加，结果仍放入A A中中11110100 11110100 结束，停机结束，停机格式格式机器语言 汇编语言汇编语言用一些简洁的英文字母、符号串来替代一个特定的指令的二进制串，例如，用一些简洁的英文字母、符号串来替代一个特定的指令的二进制串，例如，用用“ADD”“ADD”代表加法，代表加法，“MOV”“MOV”代表数据传递等等。

4、代表数据传递等等。 例如，计算例如，计算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);

5、printf(“%d”,a); return 0; return 0; 高级语言lC程序由函数构成，有且有一个主函数程序由函数构成，有且有一个主函数l 程序执行时总是从程序执行时总是从main()函数开始函数开始l 语句必须以语句必须以“；”结束，书写格式自由结束，书写格式自由l “#”开头的为编译预处理命令开头的为编译预处理命令l 利用利用/* */作为注释作为注释机器语言机器语言高级语言高级语言书写书写翻译翻译执行执行编译编译是指事先编好的一个称为编译程序的机器语言程序，通过编译程序把高级语言书写的源是指事先编好的一个称为编译程序的机器语言程序，通过编译程序把高级语言书写的源程序整个地翻译

6、成用机器语言表示的与之等价的目标程序。程序整个地翻译成用机器语言表示的与之等价的目标程序。解释解释程序是在源程序进入计算机时，通过解释程序边扫描边解释，逐句输入，逐句翻译，计程序是在源程序进入计算机时，通过解释程序边扫描边解释，逐句输入，逐句翻译，计算机一句句执行，并不产生目标程序。算机一句句执行，并不产生目标程序。共用体共用体数据类型数据类型基本类型基本类型整整型型实型实型字符型字符型单精度单精度双精度双精度非基本类型非基本类型数组数组结构体结构体指针类型指针类型枚举型枚举型3.3.数据类型数据类型l整型整型 ：int(如如 0,67, -2)l实型：实型：float、double(如如 2

7、.3, 1.2e-5)l字符型：字符型：char(如如 z, 3, $, n ) 用用开头的字符为转义字符开头的字符为转义字符, 代表代表1个字符个字符l字符串：字符串：char a(如如 UKM, 1, 5a ) 数据类型数据类型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;i

8、5;i+) sum=sum+ai; l 结构化程序设计结构化程序设计l 面向对象的程序设计面向对象的程序设计4.4.程序设计方法程序设计方法l 自顶向下自顶向下l 逐步求精逐步求精l 模块化模块化l 限制使用限制使用goto语句语句结构化程序设计结构化程序设计ABBAPPA顺序结构顺序结构选择结构选择结构循环结构循环结构程序的三种主要结构程序的三种主要结构PA当型循环当型循环直到型循环直到型循环一.顺序结构#include /*使用标准函数库中的输入输出函数时需引用该头文件*/main() printf(Hello,World!n);程序员的第一个程序顺序结构v 输入整数输入整数a、b并求和并

9、求和#includemain() int a,b; printf(Please input a and b:n); scanf(%d,%d,&a,&b);/* 从键盘输入从键盘输入a、b的值（以空格或者回车分隔）的值（以空格或者回车分隔） */ printf(a+b=%dn,a+b);利用海伦公式可以求得三角形面积为：利用海伦公式可以求得三角形面积为： 其中，其中，s=(a+b+c)/2，a、b、c是三条边长是三条边长2. 已知三角形的三条边长，计算三角形的面积。已知三角形的三条边长，计算三角形的面积。开始开始对三边长赋值对三边长赋值计算计算s值值计算面积计算面积area结束结

10、束输出三角形面积输出三角形面积area顺序结构【示例示例7-4】输入三角形的三输入三角形的三 条边长，如果能构成三角形则计算三角形的面积，否则，输出条边长，如果能构成三角形则计算三角形的面积，否则，输出“不能构成三角形不能构成三角形”。开始开始输入三条边长输入三条边长计算计算s值值计算面积计算面积area结束结束输出三角形面积输出三角形面积area输出不能构成三角形的信输出不能构成三角形的信息信息息信息构成三角形？构成三角形？YN二.选择结构开始开始对三边长赋值对三边长赋值计算计算s值值计算面积计算面积area结束结束输出三角形面积输出三角形面积area选择结构引：输入一个小写字母，变成大写后

11、输出引：输入一个小写字母，变成大写后输出#include “stdio.h”main() char a；printf(“Input a lowercase letter：”)；a = getchar()；a = a-32；printf(“%c n”，a)；#include “stdio.h”main() char a； printf(“input a letter:”); a=getchar( ); if(a=a&a=z) a=a-32; printf(“%cn”,a);1.判断输入的一个字符，如果是小写字母，变成大写后输出判断输入的一个字符，如果是小写字母，变成大写后输出#inclu

12、demain() int a,b; printf(Please input 2 numbers:); scanf(%d%d,&a,&b); if(ab) printf(%d,%d,a,b); else printf(%d,%d,b,a);2.2.任意给定两个数任意给定两个数a a，b b，将它们按从大到小的次序进行排序。，将它们按从大到小的次序进行排序。#includemain() int a; printf(“Please input the day you want to date:”）; scanf(%d,&a); if(a=1|a=3|a=5)printf(NO

13、); else printf(YES); 3. 3.晶晶约会：周一、三、五均有课晶晶约会：周一、三、五均有课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);【例例】输入输入5组三角形的三组三角形的三 条边长，对每组

14、数据进行判断，如果能构成三角形则计条边长，对每组数据进行判断，如果能构成三角形则计算三角形的面积，否则，输出算三角形的面积，否则，输出“不能构成三角形不能构成三角形”。YNY开始开始输入三条边长输入三条边长计算面积并输出计算面积并输出结束结束输出相应信息输出相应信息构成三角形？构成三角形？循环变量循环变量i=1i5？i=i+1N三.控制结构循环控制#include main() int sum=0,n=1; for(n=1;n=10;n+) sum=sum+n; printf(sum=%dn,sum);循环控制#include “stdio.h”main() int score, sum=0,

15、 i; float average; for(i=1;i=10;i+) printf(“n Input No.%d score:”, i ); scanf(%d,&score); sum=sum+score; average=sum/10; printf(naverage=%fn,average);#include #include #include main() int i,g,j=1;long t; srand(time(NULL); i=rand()%100+1; printf(Please input your number（1-100）：）：);scanf(%d,&g

16、);t=time(NULL);while(g!=i) if(gi)printf(n The number is too big,please input again：); if(gi)printf(nThe number is too small,please input again：); scanf(%d,&g); j+;t=time(NULL)-t;printf(nCongratulations！You got the right answer with %d times，uesed %d second。n,j,t);lsrand（time（NULL）使得随机数种子随时间的变化而变

17、化。ltime函数可以获取当前的系统时间，返回从CUT（Coordinated Universal Time）时间1970年1月1日00:00:00到当前时刻的秒数。lrand()返回从0-32767的整数lsrand 和 rand 应该组和使用 算法（算法（Algorithm）是一组明确的、可以执行的步骤的有序集合。）是一组明确的、可以执行的步骤的有序集合。l 有穷性有穷性l 确切性确切性l 有有0个或多个输入个或多个输入l 有有1个或多个输出个或多个输出l 有效性有效性二二. .算法算法 算法评价算法评价l正确性正确性l时间复杂度时间复杂度（计算机上运行所花费的时间）*l空间复杂度空间复杂

18、度（算法运行过程中临时占用的存储空间的大小） 测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作计算对运行时间有消耗的基本操作（如（如“运算运算”、“条件比较条件比较”、“变量代入变量代入”）的执行次数）的执行次数，运行时间与该计数成正比。 算法的复杂度标记方法一般采用“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)。解决

19、方案1（普通求和）int sum = 0, n = 100; for (int i = 1; i sum；步骤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。流程图是通过箭头相互连接的几何图形来表达的方法。流程

20、图是通过箭头相互连接的几何图形来表达的方法。ANSI规定的一些常用流程图符号。起止框输入输出框判断框处理框流程线1.1.认识算法认识算法算法的算法的描述工具描述工具sum=0n=1n=10sum=sum+nn=n+1输出输出sumNY结束结束开始开始【示例示例7-1】求求1+2+3+10，即，即101nn流程图流程图sum=0，n=1sum=sum+nn=n+1输出输出sum的值的值当当i=10时，做时，做N-S图图用流程图用流程图/N-S/N-S图表示算法图表示算法【示例示例7-1】求求1+2+3+10，即，即101nn#include main() int sum=0,n=1; for(n

21、=1;n=10;n+) sum=sum+n; printf(sum=%dn,sum);用计算机语言表示算法用计算机语言表示算法【算法思想算法思想】l扫描整个序列，从中选出最小的元素，将它与序列的第一个元素交换；l然后再在余下的元素中找出最小数据的元素，与序列的第二个元素相互交换位置l然后对剩下的序列采用同样的方法，直到序列空为止。2.经典算法 排序算法：选择排序#include main() int i,index,k,n,temp,a5; printf(“Please input 5 numbers:n”); for(k=0;k5;k+) scanf(%d,&ak); for(k=0

22、;k4;k+) index=k;for(i=k+1;i5;i+) if(aiaindex) index=i;if(index!=k) temp=aindex; aindex=ak; ak=temp; 内循环内循环外循环外循环选择法排序选择法排序printf(n);for(k=0;k5;k+) printf(%d,ak); 【算法思想算法思想】 l在每一轮的排序过程中从第一个数开始，相邻两数依次比较，当发现前一个数据比后一个数据大时，即将这两个数据进行互换。l较小的数据就会逐个向前移动，大者往后移动，最后将序列中的最大值换到了序列的最后。经典排序算法：冒泡法经典排序算法：冒泡法排序#includ

23、emain()int i,j,n=5,temp,a5=18,6,3,15,2;printf(the old array isn);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(nthe new array isn);for(i=0;in;i+)printf(%d ,ai); 冒泡法排序冒泡法排序设数组为设数组为an：1. 初始时，a0自成1个有序区，无序区为a1.n-1。令i=12. 将ai并入当前的有序区a0i-1中形成a0i的有序区间。3. i

24、+并重复第二步直到i=n-1。排序完成。经典排序算法：插入法经典排序算法：插入法排序【算法思想算法思想】 每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。main() int i,j,n=7,temp,a7=12,15,9,20,6,31,24; for (i = 1; i n; i+) if (ai = 0 & aj temp; j-) aj + 1 = aj; aj + 1 = temp; 插入法排序插入法排序【算法思想算法思想】l逐一将数组的数据与输入数进行比较l如果相等，说明找到，宣布查找成功，记录数组下标，算法结束；l

25、如果不相等，说明没有找到，此时应判断是否还有剩余的数据，如果还有剩余的数据则继续和剩余的数据比较，如果没有剩余的数据，则宣布查找失败，算法结束输入：输入： 2 9 8 10 6查找：查找： 9输出：输出：2输入：输入：2 9 8 10 6查找：查找：7输出：输出：Not Found 经典查找算法：顺序查找经典查找算法：顺序查找-输入一组数据，再输入需要查找的数x，如果找到，输出相应的位置，否则，输出Not Found。 #includemain() int i,x,a5; printf(Please input 5 numbers:n); for(i=0;i5;i+) scanf(%d,&ai); printf(Please input the number you want to find:n); scanf(%d,&x);for(i=0;i=5) printf(There is no such number); 顺序查找顺序查找经典查找算法：折半查找经典查找算法：折半查找（数据已经排好序）（数据已经排好序）输入：10 17 20 22 31 44 51 55 68查找：20【算法思想算法思想】 数据存放在数组中，被查找数据放到x变量中，t表示查找范围的起点位置，b代表查找范围的末尾，m id表示查找范围的中间位置，mid=(t+b)/2。第