《计算机应用基础》 第9章 程序设计基础（一）.

Presentation on theme: "《计算机应用基础》 第9章 程序设计基础（一）."— Presentation transcript:

1 《计算机应用基础》 第9章 程序设计基础（一）

2 教学内容 程序设计相关概念 日常生活中的程序 计算机程序 程序设计过程 算法的概念 什么是算法 算法的表示 信息管理学院

3 1.日常生活中的程序 例如: 这些程序: 有目标, 有明确步骤, 有开始, 有结束 完成某项活动的一种既定方式和过程. 食谱——做菜的程序
选举全国人大代表程序 图书馆借书的程序 这些程序: 有目标, 有明确步骤, 有开始, 有结束 信息管理学院

4 红烧肉菜谱 准备： 烧热油，放两勺白糖和二两姜片（鲜姜一块切成）进去翻炒片刻 放入块状五花肉一道翻炒，直至颜色变黄，油也煸出不少
上好五花肉，沸水焯去污物，切麻将块大小 调料：白糖、姜片、油盐醋、丁香、胡萝卜 烧热油，放两勺白糖和二两姜片（鲜姜一块切成）进去翻炒片刻 放入块状五花肉一道翻炒，直至颜色变黄，油也煸出不少 加水至漫过肉块，加酱油少许、盐、二两中国醋、丁香四、五枚 起锅前十分钟加胡萝卜块 水收干后起锅 信息管理学院

5 2.计算机程序 计算机程序是为完成某个计算任务而设计的指令序列。 程序包含了任务中要处理的对象和处理规则。
计算任务: 指以计算机为处理工具的任务 数值计算 非数值计算（…） 程序包含了任务中要处理的对象和处理规则。 处理对象: 各类数据 —— (数据结构) 处理规则: 如何操作和加工数据 —— (算法) 算法的描述 程序的实现：计算机语言（即编程） 信息管理学院

6 3.程序设计 程序设计是以问题为目标，设计解决问题的方法与步骤，并通过某种语言，将机器指令组合在一起解决问题的过程。 分析问题
解决问题——设计 数据结构 算法 程序实现——编码与调试 信息管理学院

7 程序设计的基本步骤 否 是 有错误？ 分析问题 编码 设计 调试 语言错误? 结束 修改 数据结构 算法 计算机语言 信息管理学院

8 确定x(i)使，x(i)≥x(j),j=1,2,…,N
在N个正整数：x(1),x(2),…,x(N)中 确定x(i)使，x(i)≥x(j),j=1,2,…,N 分析问题 将这N个数顺序存储 设计求最大值的算法 解决问题 编码 用C语言实现算法得到源程序 用C语言编译器编译和调试源程序 得到可执行文件 调试 信息管理学院

9 算法 4.什么是算法 算法特征 算法评价 5.算法的表示 自然语言表示 伪代码表示 流程图表示(ANSI流程图) 信息管理学院

10 简单说：计算机程序中为解决问题而采取的方法和步骤 ——称为“算法”
4.什么是算法(1) 程序的设计过程，核心问题是设计一个合理、有效的算法。 算法  程序的质量 一般认为，算法就是根据明确规定的运算规则，在在有限的时间内就可得出确切结果的有效运算步骤。 简单说：计算机程序中为解决问题而采取的方法和步骤 ——称为“算法” 信息管理学院

11 算法示例：求最大值 问题描述: 给定一正整数序列，求值最大者 12 8 13 9 11 ——表示存储空间 L 设计运算步骤如下 12 8
S2 S3 S4 S5 S1 Si表示第i步 L代表一个存储空间 被称为变量 信息管理学院

12 算法示例：求最大值 求最大值的过程—用语言描述 S2:设L=第一个数 S3:若第二个数比L大, 则设L=第二个数
信息管理学院

13 S1: 输入5个正整数，并按序编号为：1,2,3,4,5；准备变量L和P
算法示例：求最大值 求最大值过程—改进 S2:设L =0,P=1（P的值表示当前数的编号） S3:若当前数比L大, 则令L等于当前数 S4:如果P≤5则令P的值增大1，返回执行S3 ，否则继续执行下一步S5 S5: 输出L，程序结束。 S1: 输入5个正整数，并按序编号为：1,2,3,4,5；准备变量L和P 初始值比5个数都小 信息管理学院

14 算法示例：求最大值 求最大值过程—改进 12 8 13 9 11 P= 1 L= S2 3 S4 S4 4 5 S4 2 S4 12 L=
… 5 12 8 13 9 11 P= 1 L= S2 3 S4 S4 4 5 S4 2 S4 12 L= S3 12 L= S3 13 L= S3 13 L= S3 13 L= S3 P<5 不成立 S4 输出L S5 信息管理学院

15 求最大值算法 从N个正整数中求最大值的算法: S1: 输入N个正整数，并按序编号：1,2,…,N S2:设L =0, 当前数位置P=1
S3:若当前数比L大, 则设L=当前数 S4:若p <N, 则P 值增大1, 返回执行S3；否则输出L，程序结束。 P指示了当前数在列表中的序号 信息管理学院

16 4.什么是算法(2) 算法的5个特性： (1)有穷性(finiteness)，即解题步骤是有限的，无穷的步骤意味问题无解。
(2)确定性(definiteness)，每一解题步骤都是明确的，无二义性。 (3)有效性(effectiveness)，每一步骤都是可行的,可实现的。 (4)有输入(input)。有明确的输入。但输入有多种形式 (5)有输出(output)。有明确的输出结果。输出有多种形式 信息管理学院

17 4.什么是算法 .vs. 算法的评价 首要是正确性 时间效率 空间效率 时间复杂度 空间复杂度 指运算消耗的时间（时间复杂度）
运行过程中占用的存储空间（空间复杂度） .vs. 时间复杂度 空间复杂度 信息管理学院

18 5.算法的表示： 自然语言 伪代码 流程图： ANSI流程图 N-S图 为便于理解算法, 需要有效的算法描述手段 信息管理学院

19 算法描述示例——自然语言 自然语言就是用人们日常生活中使用的文字符号和语言习惯来描述算法 从N个正整数中求最大值的算法:
S1: 输入N个正整数x(1),x(2),…,x(N) S2:设L =0, 当前数序号P=1 S3:若x(P)比L大, 则设L=x(P) S4:若p <N, 则P 值增大1, 返回执行S3；否则输出L，程序结束。 信息管理学院

20 算法描述示例——从N个正整数中寻找最大值的算法
类C伪代码 input N postive integer to x(1),x(2),…,x(N) L =0 p =1 if x(p)>L then L=x(p) if p<N, then p=p+1, goto 4 else print L 伪代码：介于自然语言和编程语言之间的算法描述语言，目的是用以编程语言的风格描述算法。但伪代码与具体编程语言无关，也没有统一标准。 信息管理学院

21 算法描述示例——从N个正整数中寻找最大值的算法
F S1 S2 P<N PP+1 Print L S3 T start stop 以特定的图形符号加上说明，表示算法的图，称为程序流程图 程序 流程图 S1: 输入N个正整数，并按序编号：1,2,…,N S2:设L =0, 当前数位置P=1 S3:若当前数比L大, 则设L=当前数 S4:若p <N, 则P 值增大1, 返回执行S3；否则输出L，程序结束。 信息管理学院

22 N个正整数中求最大值的通用算法 完整的程序流程图 开始 L=0, P=1 L<X(P)? 是 否 L=X(P) P<N 是
输入x(1),x(2), …,x(N) L=0, P=1 完整的程序流程图 L<X(P)? 是 否 L=X(P) P<N 是 P=P+1 否 输出L 信息管理学院 结束

23 算法的表示—ANSI流程图 流程图是人们对解决问题的方法、思路或算法的一种描述。 程序流程图的优点： （a）采用简单规范的符号，画法简单；
（b）结构清晰，逻辑性强； （c）便于描述，容易理解。 信息管理学院

24 ANSI流程图-基本构件 起止框：表示程序的开始或结束 处理框：表示对数据进行赋值或加工 输入/输出框：表示数据输入、输出操作
判断框 起止框：表示程序的开始或结束 处理框：表示对数据进行赋值或加工 输入/输出框：表示数据输入、输出操作 过程：表示该部分是一个过程 判断框：表示根据条件决定程序走向 连接点：表示图标之间相互连接关系 箭头：表示程序流向 信息管理学院

25 ANSI流程图：流程控制基本结构 结构化程序设计观点： 三种基本结构： 自顶向下、逐步求精 使用三种基本控制结构可以构造任意程序 顺序结构
分支结构 单分支、多重分支 循环结构 当型循环结构、直到型循环结构 信息管理学院

26 ANSI流程图：流程控制基本结构 顺序结构 顺序结构是程序设计中最基本的结构。 顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的。
B C 信息管理学院

27 ANSI流程图：流程控制基本结构 分支结构 分支结构又称作选择结构
按给定的选择条件成立与否来确定程序的走向。分支结构可分为双重分支选择和多重分支选择。在任何条件下，无论分支多少，只能也只会选择其一执行。 双分支 三分支 F T 条件 A B F T 条件1 A B 条件2 C 信息管理学院

28 ANSI流程图：流程控制基本结构 循环结构表示程序反复执行某个或某些操作，直到某条件为假（或为真）时才可终止循环。
循环结构的基本形式有两种：当型循环和直到型循环。 F T 条件 循环体 当型循环结构 当型循环：先判断条件，当条件满足时执行循环体，循环体执行后再返回到循环结构入口；如果条件不满足，则退出循环结构。先判断后执行。 F—表式条件不满足 T—表示条件满足 信息管理学院

29 ANSI流程图：流程控制基本结构 在循环结构中最主要的是： 什么情况下执行循环？ (即循环条件） 哪些操作需要循环执行？(即循环体)
什么情况下执行循环？ (即循环条件） 哪些操作需要循环执行？(即循环体) 循环体本身可以是另一个基本控制结构 循环结构= 循环体+循环条件 条件 F T 循环体 直到型循环结构 直到型循环：先执行循环体，循环体执行后判断条件，如果条件不满足，返回入口继续执行循环体，直到条件为真时退出循环。先执行后判断 信息管理学院

30 求1+2+…+100的和。算法描述 S1：将1存入变量x。 S2：将2存入变量y。 S3：将x和y相加，结果存入x。
S4：将y加1，结果存入y。 S5：若y不超过100，转到S3执行，否则输出结果x，运算结束。 自然语言描述 S1: x1 S2: y2 S3: xx+y S4: yy+1 S5: If y<=100, then go to S3; else print x. 伪代码 信息管理学院

31 ANSI流程图示例1 求1+2+…+100的和。算法描述 S2: x1 S3: y2 S3: xx+y S4: yy+1
start stop X1, y2 Xx+y Y<=100 yy+1 F T Print x 求1+2+…+100的和。算法描述 S2: x1 S3: y2 S3: xx+y S4: yy+1 S5: If y<=100, then go to S3; else print x 伪代码 信息管理学院

32 练习：用ANSI流程图描述算法 求两个正整数m,n（假设m>=n）的最大公因子 方法一 方法二,用辗转相除法 朴素解法——逐个测试
gcd(m,n)=gcd(n,m%n) %表示求余数运算 见例9.2 信息管理学院

33 例9.2-算法 start Input m, n rm/n的余数 mn, nr r=0 F T Print n stop 信息管理学院

34 练习：用ANSI流程图描述判断闰年算法 判断闰年算法,闰年是指 被4整除且不能被100整除的年份; 或 能被400整除的年份 信息管理学院

35 判断闰年算法 start input Y 400整除Y？ F 4整除Y？ T 100整除Y？ F T F T Y是闰年 Y不是闰年 Y是闰年
end 信息管理学院

36 了解N-S图 顺序结构 条件分支结构 A B C A B 条件 T F 注：这里P表示条件, T表 示真，F表示假 信息管理学院

37 了解N-S图 循环结构 当P满足时 循环体 循环体 直到P不满足 当型循环结构 直到型循环结构 信息管理学院

38 N-S图表示算法 求1+2+…+100的和。算法描述 S1: x1,y2 S2: xx+y S3: yy+1
start S1: x1,y2 S2: xx+y S3: yy+1 S4: If y<=100, then go to S2; else go to S5 S5: print x X1, y2 X1, y2 Xx+y Y<=100 Xx+y yy+1 yy+1 T Y<=100 Print x F 自然语言描述 Print x 信息管理学院 stop

39 求最大值算法—C语言实现 #include <stdio.h> #include <stdlib.h> #define N 10 main() { unsigned int x[N]; int L,k,p; for(k=0;k<10;k++) scanf(“%d”,&x[k]); L=0; p=0; do{ if(L<x[p]) L=x[p]; p++; } while(p<N); printf(“Maximum = %d \n”, L); getch(); } 信息管理学院

40 求最大值算法—编译调试(基于Win-TC)
信息管理学院