当前位置：文档之家 › 第二章程序的灵魂——算法

第二章程序的灵魂——算法

  • 格式：ppt
  • 大小：688.50 KB
  • 文档页数：41

下载文档原格式

  / 41

合集下载

第二章 程序的灵魂——算法1

第二章 程序的灵魂——算法1


算法举例：求两个整数之和。 算法举例：求两个整数之和。
解题的基本思路： 解题的基本思路： (1)准备两个整数； (1)准备两个整数； 准备两个整数 (2)作加法运算；并存放起来 作加法运算； 作加法运算 (3)输出和。 输出和。 输出和
main( ) { int i,j,sum; i=2;j=i=2;j=-3; sum=i+j;
•流程图：用一些约定的几何图形来描述算法。 流程图：用一些约定的几何图形来描述算法。
起止框 流程线 输入输出框 连接点 判断选择框
用某种图框表示某种操作， 用某种图框表示某种操作，用箭头表示算法流程
……
处理框
注释框
例： 求5！
开始 p=1 i=2 p=p*i i=i+1 N i>5
Y
结束
结构化程序设计
A
a块 块 b块 块
B
(2)判别选择结构程序设计
• 举例，求a、b两个 满足条件否 数中的最大值； 满足 不满足
Max = a； ；
执行a块 执行 块 N
成立
执行b块 执行 块
Y
max = b； ；
b >max？ ？
不成立
条件成立？ 条件成立？ 执行a块 执行 块 执行b块 执行 块
k k=k1 k=k2 A2 ... k=kn k=ki Ai ... An
求1×2×3×4×5
上述算法太繁琐，我们找一种通用 的表示方法。 S1:设变量p，被乘数，p=1; s2: s2:设变量i,代表乘数，i=2; i, i=2; s3:使p×i,乘积放在被乘数变量p中， 可表示为：p× i p; s4:使i的值加1，即i+1 i; s5:如果i不大于5，返回重新执行步骤 s3以及其后的s4、s5;否则，算法结 束。最后得到的p就是5!的值。
第2章 算法---程序的灵魂

第2章 算法---程序的灵魂


2.1 什么是算法
广义地说，为解决一个问题而采取的方法和步骤， 广义地说，为解决一个问题而采取的方法和步骤， 方法和步骤 就称为“算法” 就称为“算法” 对同一个问题，可以有不同的解题方法和步骤 对同一个问题，可以有不同的解题方法和步骤 不同的 应考虑算法的质量，选择合适的算法 考虑算法的质量， 算法的质量
将例2.3判定闰年的算法用 判定闰年的算法用N-S图表示 例2.13 将例 判定闰年的算法用 图表示
2000⇒year ⇒ year%4为0 为 否 year%100不为 不为0 不为 是 year%400为 year%400为0 输出 year 闰年 是 输出year 输出 闰年 否 输出year 输出 非闰年 否 输出 year 非闰年
(1)对数据的描述 对数据的描述----数据结构 数据结构(data structure) 对数据的描述
数据的类型和数据的组织形式 数据的类型和数据的组织形式 类型和数据的
(2) 对操作的描述 对操作的描述-----算法 算法(algorithm) 。 算法
即要求计算机进行操作的步骤 即要求计算机进行操作的步骤
是
year+1⇒year ⇒ 直到year>2500 直到
2.4.5用伪代码表示算法 2.4.5用伪代码表示算法
伪代码是用介于自然语言和计算机语言之 间的文字和符号来描述算法 用伪代码写算法并无固定的、严格的语法 用伪代码写算法并无固定的、 规则，可以用英文， 规则，可以用英文，也可以中英文混用
例2.16 求ห้องสมุดไป่ตู้!。 。
例2.3 判定2000—2500年中的每一年是 判定 年中的每一年是 否闰年，并将结果输出。 否闰年，并将结果输出。 闰年的条件： 闰年的条件：
第2章 算法---程序的灵魂

第2章 算法---程序的灵魂

S1：使p=1，或写成1p
S2：使i=2 3 ，或写成2 3i S3：使p与i相乘，乘积仍放在变量p中，可表 相当于i ≤11 示为：p*ip S4：使i的值加1 2 i 2，即i+1
S5：如果i不大于5 ，返回重新执行S3；否则 11 ，算法结束
算法的特性
一个有效算法应该具有以下特点：
0 x x<5 Y x+1x 输出x的值
N
输出1,2,3,4,5
(3) 循环结构
② 直到型循环结构
0 x x+1x
A N p2 Y
输出x的值
N
X≥5
Y
以上三种基本结构，有以下共同特点：
(1) 只有一个入口 (2) 只有一个出口 一个判断框有两个出口 一个选择结构只有一个出口 (3) 结构内的每一部分都有机会被执行到。也 就是说，对每一个框来说，都应当有一条从入 口到出口的路径通过它 (4) 结构内不存在“死循环”
(算法结束)
结构化程序设计方法
结构化程序设计强调程序设计风格和程序 结构的规范化，提倡清晰的结构。
结构化程序设计方法的基本思路是：把一 个复杂问题的求解过程分阶段进行，每个 阶段处理的问题都控制在人们容易理解和 处理的范围内。
结构化程序设计方法
采取以下方法保证得到结构化的程序：
（1） 自顶向下；
简单的算法举例
例求1×2×3×4×5× …×1000
可以用最原始的方法进行：
太繁琐 步骤1：先求1*2 ，得到结果2。
步骤2：将步骤1得到的乘积2再乘以3，得 到结果6。 步骤3：将6再乘以4，得24。 步骤4：将24再乘以5，得120。这就是最 后的结果。
改进的算法：
c程序设计 第二章 程序的灵魂-算法

c程序设计 第二章 程序的灵魂-算法


2.2 简单算法举例 例2.5 对一个大于或等于3的正整数，判断 它是不是一个素数 素数的含义：是指除了1和该数本身之外， 不能被其他任何整数整除的数。 判断一个数n（n≥3）是否是素数的方法： 将n作为被除数，将2到（n-1)各个整数先 后作为除数，如果都不能被整除，则n为素 数。
2.2 简单算法举例
算法可以表示如下： S1：输入n的值 S2：i=2(i作为除数） S3：n被i除，得余数r S4：如果r=0，表示n能被i整除，则输出n “不是素数”，算法结束；否则执行S5 S5：i+1→i S6：如果i≤n-1，返回S3；否则输出n “是素数”， 然后结束
2.2 简单算法举例
注：实际上，n不必被2到（n-1)的整数除，只需被2 到n/2间整数除即可，甚至只需被2到 n 之间的整数 除即可。例如，判断13是否素数，只需将13被2、3 除即可，如都除不尽，n必为素数。 这样，S6步骤可改为： S6：如果i≤ n ，返回S3；否则算法结束。
2.4.4 用N－S流程图表示算法
1、N-S流程图所用的 流程图符号 （1）顺序结构
A B
图2－24 （2）选择结构
成立 A P 不成立 B
图2－25
（3）循环结构
① 当型循环结构
当P1成立 A
图2－26 ② 直到型循环结构
A 直到P1成立
图2－27
说明： （1）可以用以上3种N-S流程图的基本框 组成复杂的流程框，以表示算法。 （2）从图2－24到2－27中的A框或B框， 可以是一个简单的操作，也可以是3 个基本结构
这样的方法虽然是正确的，但太繁琐。 将算法改写如下： S1：使p＝1 S2：使i＝2 S3：使p*i，乘积仍放在变量p中，可表示 为：p*i→p S4：使i的值加1，即i+1→i S5：如果i不大于5，返回重新执行步骤S3以 及其后的步骤S4和S5；否则，算法结束。 最后得到p的值就是5！的值。 显然，这个算法比前面列出的算法要简练。
第2章 算法---程序的灵魂

第2章 算法---程序的灵魂


给出一个大于或等于3的正整数 的正整数， 例2.5 给出一个大于或等于 的正整数，判 断它是不是一个素数。 断它是不是一个素数。 所谓素数(prime)，是指除了1和该数本 ，是指除了 和该数本 所谓素数 身之外，不能被其他任何整数整除的数 身之外， 例如， 是素数 因为它不能被2， ， 是素数， 例如，13是素数，因为它不能被 ，3，4 整除。 ，…，12整除。 ， 整除
例2.1 求1×2×3×4×5× …×1000 × × × ×5× × 可以用最原始的方法进行： 可以用最原始的方法进行：
步骤1：先求1*2，得到结果 。 步骤 ：先求 太繁琐 ，得到结果2。 步骤2：将步骤 得到的乘积 再乘以3， 得到的乘积2再乘以 步骤 ：将步骤1得到的乘积 再乘以 ，得 到结果6。 到结果 。 步骤3： 再乘以4， 步骤 ：将6再乘以 ，得24。 再乘以 。 步骤4： 再乘以5， 步骤 ：将24再乘以 ，得120。这就是最 再乘以 。 后的结果。 后的结果。
year不能 不能 被4整除 整除 非闰年 闰年 year被 year被100 整除， 整除，又能 被400整除 整除 year被4整 被 整 除，但不能 被100整除 整除 闰年 其他 非闰年 逐渐缩小判 断的范围
1 1 1 1 1 例2.4 求 1 + + L + 2 3 4 99 100
算法是解决“做什么” 算法是解决“做什么”和“怎么做”的 怎么做” 问题 程序中的操作语句， 程序中的操作语句，是算法的体现 不了解算法就谈不上程序设计
2.1 什么是算法 2.2 简单的算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法
2.1 什么是算法
广义地说，为解决一个问题而采取的方 广义地说， 法和步骤，就称为“算法” 法和步骤，就称为“算法” 对同一个问题，可以有不同的解题方法 对同一个问题， 和步骤 为了有效地进行解题， 为了有效地进行解题，不仅需要保证算 法正确，还要考虑算法的质量， 法正确，还要考虑算法的质量，选择合 适的算法
第二章 程序的灵魂---算法

第二章 程序的灵魂---算法

(4) 适当使用注释。注释是帮助程序员理解程 序，提高程序可读性的重要手段，对某段程序或某 行程序可适当加上注释；
(5) 标识符贴近实际。
谢谢观看
• 三种基本结构
❖ 顺序结构 ❖ 选择结构 ❖ 循环结构
• 三种基本结构的特点
❖只有一个入口 ❖只有一个出口 ❖结构内每一部分都能执行到 ❖结构内无死循环
• 结构化程序设计特征
（1）以三种基本结构的组合来描述程序； (2) 整个程序采用模块化结构； (3) 有限制地使用转移语句，在非用不可的情况下，也要 十分谨慎，并且只限于在一个结构内部跳转，不允许从一个结 构跳到另一个结构，这样可缩小程序的静态结构与动态执行过 程之间的差异，使人们能正确理解程序的功能； (4) 以控制结构为单位，每个结构只有一个入口，一个出 口，各单位之间接口简单，逻辑清晰； (5) 采用结构化程序设计语言书写程序，并采用一定的书 写格式使程序结构清晰，易于阅读； (6) 注意程序设计风格。
换。 算法分析：这是一个非数值运算问题。因为两个瓶 子的墨水不能直接交换，所以，解决这一问题的关 键是需要引入第三个墨水瓶。设第三个墨水瓶为白 色，其交换步骤如下：
① 将黑瓶中的黑墨水装入白瓶中； ② 将蓝瓶中的蓝墨水装入黑瓶中； ③ 将白瓶中的黑墨水装入蓝瓶中； ④ 交换结束。
2.5 结构化程序设计的方法
算法的表示： ① 将黑瓶中的黑墨水装入白瓶中；
有些特殊算法也可以没有输入。 ② 将蓝瓶中的蓝墨水装入黑瓶中；
✓自然语言表示 (4) 以控制结构为单位，每个结构只有一个入口，一个出口，各单位之间接口简单，逻辑清晰；
(6) 注意程序设计风格。 试想，如果例1-3中没有 "输出n的当前值"这一步，这个算法将毫无意义。 (1) 语句形式化。
第2章+算法——程序的灵魂

第2章+算法——程序的灵魂


《 C 程序设计》，主讲：丁智勇（dzy_sys@） 程序设计》 主讲：丁智勇（dzy_sys@）
• 数据是操作的对象 • 操作的目的是对数据进行加工处理，以得到期 操作的目的是对数据进行加工处理， 望的结果 • 著名计算机科学家沃思(Nikiklaus Wirth)提出 著名计算机科学家沃思(Nikiklaus Wirth)提出 一个公式： 一个公式： 算法 + 数据结构 = 程序
《 C 程序设计》，主讲：丁智勇（dzy_sys@） 程序设计》 主讲：丁 不能 被4整除 整除 非闰年 闰年 year被 year被100 整除， 整除，又能 被400整除 整除 year被4整 被 整 除，但不能 被100整除 整除 闰年 其他 非闰年 逐渐缩小判 断的范围
2.1 什么是算法
• 广义地说，为解决一个问题而采取的方法和步骤， 广义地说，为解决一个问题而采取的方法和步骤， 方法和步骤 就称为“算法” 就称为“算法” • 对同一个问题，可以有不同的解题方法和步骤 对同一个问题， • 为了有效地进行解题，不仅需要保证算法正确， 为了有效地进行解题，不仅需要保证算法正确， 还要考虑算法的质量，选择合适的算法 还要考虑算法的质量，
n
S5： S5：i+1 ⇒ i S6：如果i S6：如果i ≤ n-1，返回 S3 ；否则输出 n “是素数”，然 是素数” 后结束。 后结束。
《 C 程序设计》，主讲：丁智勇（dzy_sys@） 程序设计》 主讲：丁智勇（dzy_sys@）
2.3算法的特性 2.3算法的特性
《 C 程序设计》，主讲：丁智勇（dzy_sys@） 程序设计》 主讲：丁智勇（dzy_sys@）
2.2简单的算法举例 2.2简单的算法举例
例2.1 求1×2×3×4×5× …×1000
第2章-算法---程序的灵魂-2

第2章-算法---程序的灵魂-2

第2章 算法---程序旳灵魂
➢一种程序主要涉及下列两方面旳信息： (1) 对数据旳描述。在程序中要指定用到哪些数据以及 这些数据旳类型和数据旳组织形式 这就是数据构造(data structure) (2) 对操作旳描述。即要求计算机进行操作旳环节 也就是算法(algorithm) ➢著名计算机科学家沃思(Nikiklaus Wirth)提出一种 公式：
2.4.4 用N-S流程图表达算法
➢N-S流程图用下列旳流程图符号：
A B 顺序构造
p
Y
N
AB
选择构造
当p1成立
A
循环构造 （当型）
A
直到p2成立
循环构造 （直到型）
例2.11 将例2.1旳求5!算法用N-S图表达 。
1t 2i t*it i+1i 直到i>5 输出t
例2.13 将例2.3鉴定闰年旳算法用N-S图表达
算法 + 数据构造 = 程序 ➢算法、数据构造、程序设计措施和语言工具是一种程序 设计人员应具有旳知识
2.1 什么是算法 2.2 简朴旳算法举例 2.3 算法旳特征 2.4 怎样表达一种算法 2.5 构造化程序设计措施
2.1 什么是算法
➢自学
2.2简朴旳算法举例
例2.1 求1×2×3×4×5 ➢能够用最原始旳措施进行： 环节1：先求1 × 2，得到成果2。 环节2：将环节1得到旳乘积2再乘以3，得到成果6。 环节3：将6再乘以4，得24。 环节4：将24再乘以5，得120。这就是最终旳成果。 ➢改善旳算法： 设变量p为被乘数 变量i为乘数 用循环算法求成果
p1 N Y
A
0x
x<5 N Y
输出x旳值
x+1x
第2章 算法---程序的灵魂

第2章 算法---程序的灵魂

home back first prev next last
8
2.2简单的算法举例
• 改进的算法：
– 设变量 p 为被乘数 – 变量 I 为乘数 – 用循环算法求结果
home back first prev next last
9
2.2简单的算法举例
• S1：使p=1，或写成1 p • S2：使i=2，或写成2 i • S3：使p与i相乘，乘积仍放在变量p中，可 若是1000，求什么？ 表示为：p*i p • S4：使i的值加1，即i+1 i • S5：如果i不大于5，返回重新执行S3；否则， 算法结束 • 最后得到p的值就是 5!的值
例2.4 求
1 1 1 1 1 1 2 3 4 99 100
• 规律：
①第1项的分子分母都是1 ② 第2项的分母是2，以后每一项的分母都是前 一项的分母加1 ③ 笫2项前的运算符为“-”，后一项前面的运算 符都与前一项前的运算符相反
home back first prev next last
③
位置不够
① 起止框 输入输出框 ②
判断框 防止交叉 处理框
流程线
连接点
注释框
home back first prev next last
29
开始
例2.6 将例2.1的算法用 流程图表示。 求1×2×3×4×5 • 如果需要将最后结果 输出:
N
1t
2i t*it i+1i
i>5
Y
结束
home back first prev next last
home back first prev next last
26
ቤተ መጻሕፍቲ ባይዱ
C语言程序课件ppt-第二章程序的灵魂—算法

C语言程序课件ppt-第二章程序的灵魂—算法


输出y
闰年的条件是（1）能被4整除，但不能被100 整除；（2）能被100整除，又能被400整 除。
y=2000—2500
如果y是闰年 则输出y
y=2000
当y<2500
T
是闰年
F
输出y
y=y+1
mod(y,4)=0
and
mod(y,100) ≠0
T
F
输出y
mod(y,100)=0
and
T
mod(y,400) =0 F
其后的步骤S4和S5；否则，算法结束。最后得 到p的值就时5！的值。
流程图
起止框 处理框 流程线
输入输出框
判断框
连接点
开始
1=>t
2==&g
N
i>5
Y
结束
N-S流程图
1=>t 2==>i
t*i==>t
i+1==>i 直到i>5 输出t
伪代码表示
Begin 1=>t 2=>I While i<=5 {t*i==>t i+1==>i } printf t end
① 确定算法：分析问题（建立数学模型，选 择公式，写出算法描述）
② 编写程序 ③ 上机调试：输入程序，编译，连接，执行
程序，输出结果。
例2.1 求1×2×3×4×5.
用最原始的方法进行 步骤1：先求1*2，得到结果2. 步骤2：将步骤1得到的结果2再乘以3，得到
结果6； 步骤3：将6乘以4得到24； 步骤4：24乘以5得到结果120，得到最终结
第2章 程序的灵魂——算法
李淑敬
内容提要
第2章 程序的灵魂-算法(第1次课)

第2章 程序的灵魂-算法(第1次课)

些很简单的问题外，一般不用自然语言描述算法。
C语言程序设计
5
2.2 算法的表示方法
一、算法及其表示
（1） 自然语言描述
例1 有两个存储单元a和b，要求将它们的值互换。 分析：按存储器的性质，如果将单元a的值直接送到单元
b中，那么就会覆盖掉b原来的内容，因此，需要借助一 个临时单元c来交换。 具体算法如下： 步骤1： 将单元a的值送给单元c； 步骤2： 将单元b的值送给单元a； 步骤3： 将单元c的值送给单元b。
结束
是
C语言程序设计
9
2.2 算法的表示方法
一、算法及其表示
（3） N-S图（盒图）
针对流程图存在的缺点，I. Nassi和B. Shneiderman提出 了结构化程序设计的流程图，称为N-S图，更能体现结
构化程序设计的思想。推荐使用N-S图。 N-S图完全去掉了流程线，算法的所有处理步骤都写在 一个大矩形框内（表示简单、符合结构化思想）（象堆 积木）
输入a、b、c 是 a>b 否 amax bmax 是 c>max 否 cmax 空 输出max （g）
S2 S2.2
C语言程序设计
18
C语言程序设计
10
2.2 算法的表示方法
一、算法及其表示
（3） N-S图（盒图）
C语言程序设计
11
2.3 简单算法举例
Eg: 求1+2+3+4+…+10 ，写出其算法。 流程图描述: 自然语言描述： 步骤1： 将0送到 0 => s S中； 步骤2： 将1送到 1 => n n中； 步骤3： 把n的值 s+n => s 加到S中； 步骤4： n增1； n+1 => 步骤5： 若n≤10 n 则转回步骤3，否 n ≤ 10 则执行步骤6； 否 步骤6： 输出S的 输出 值。 s

C语言第2章 程序的灵魂——算法


则算法可表示如下： S1: 1→i S2: 如果gi≥80，则打印ni和gi，否则不打印 S3: i+1→i S4:若i≤50, 返回S2，否则，结束。
【例2.3】判定2000 — 2500年中的每一年是否闰年，将结果输出。 润年的条件： 能被4整除，但不能被100整除的年份； 能被100整除，又能被400整除的年份； 设y为被检测的年份，则算法可表示如下： S1: 2000→y S2:若y不能被4整除，则输出y“不是闰年”，然后转到S6 S3:若y能被4整除，不能被100整除，则输出y“是闰年”，然后转到S6 S4:若y能被100整除，又能被400整除，输出y“是闰年” 否则输出y“不是闰 年”，然后转到S6 S5:输出y“不是闰年”。 S6:y+1→y S7:当y≤2500时, 返回S2继续执行，否则，结束。
2.1 算法的概念
做任何事情都有一定的步骤。为解决一个问题而采取的方法和步骤，就称为算法。 计算机算法：计算机能够执行的算法。
计算机算法可分为两大类： 数值运算算法：求解数值； 非数值运算算法：事务管理领域。
2.2 简单算法举例
【例2.1】求1×2×3×4×5。 算法： S1: 使t=1 S2: 使i=2 S3: 使t×i, 乘积仍然放在在变量t中，可表示为t×i→t S4: 使i的值+1，即i+1→i S5: 如果i≤5, 返回重新执行步骤S3以及其后的S4和S5；否则，算法结束。 如果计算100！只需将S5:若i≤5改成i≤100即可。
2.4.3 三种基本结构和改进的流程图 顺序结构：
选择结构：
循环结构：
三种基本结构的共同特点： 只有一个入口； 只有一个出口； 结构内的每一部分都有机会被执行到； 结构内不存在“死循环”。

第2章 算法---程序的灵魂

2.2节介绍的算法是用自然语言表示的 用自然语言表示通俗易懂，但文字冗长，容易出现歧义性 用自然语言描述包含分支和循环的算法，不很方便 除了很简单的问题外，一般不用自然语言
一个入口 Y 2.4.2用流程图表示算法 N
流程图是用一些图框来表示各种操作 两个出口 …… 用图形表示算法，直观形象，易于理解
S1：输入n的值 S2：i=2 （i作为除数） S3：n被i除，得余数r S4：如果r=0，表示n能被i整除，则输出n“不是素数”，算法 结束；否则执行S5 S5：i+1i S6：如果i≤n-1，返回S3；否则输出n “是素数”，然后结束。
可改为n/2
n
2.3算法的特性
一个有效算法应该具有以下特点：
1 1 1 1
S1：sign=1 99次循环后sum的值 S2：sum=1 就是所要求的结果 S3：deno=2 S4：sign=(-1)*sign S5：term=sign*(1/deno) S6：sum=sum+term S7：deno=deno+1 S8：若deno≤100返回S4；否则算法结束
year不能 被4整除 非闰年 闰年
year被100 整除，又能 被400整除
year被4整 除，但不能 被100整除 闰年 逐渐缩小判 断的范围
其他 非闰年
例2.4 求 规律：
1 1 1 1 1 1 2 3 4 99 100
①第1项的分子分母都是1 ② 第2项的分母是2，以后每一项的分母子都是前一项的分母加 1 ③ 笫2项前的运算符为“-”，后一项前面的运算符都与前一项 前的运算符相反
(1)能被4整除，但不能被100整除的年份都是闰年，如2008、 2012、2048年 (2)能被400整除的年份是闰年，如2000年 不符合这两个条件的年份不是闰年 例如2009、2100年

第2章 算法---程序的灵魂


学习方法－熟练掌握基本知识，重在动手实践学习
2.4.1 用自然语言表示算法
2.2节介绍的算法是用自然语言表示的
用自然语言表示通俗易懂，但文字冗长，容 易出现歧义性 用自然语言描述包含分支和循环的算法，不 很方便 除了很简单的问题外，一般不用自然语言
学习方法－熟练掌握基本知识，重在动手实践学习 一个入口
学习方法－熟练掌握基本知识，重在动手实践学习
2.3算法的特性
一个有效算法应该具有以下特点：
(3) 有零个或多个输入。所谓输入是指在执 行算法时需要从外界取得必要的信息。 (4) 有一个或多个输出。算法的目的是为了 求解，“解” 就是输出。
没有输出的算法是没有意义的。
(5) 有效性。算法中的每一个步骤都应当能 有效地执行，并得到确定的结果。
不了解算法就谈不上程序设计
学习方法－熟练掌握基本知识，重在动手实践学习
2.1 什么是算法
2.2 简单的算法举例
2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法
学习方法－熟练掌握基本知识，重在动手实践学习
2.1 什么是算法
广义地说，为解决一个问题而采取的方 法和步骤，就称为“算法” 对同一个问题，可以有不同的解题方法 和步骤 为了有效地进行解题，不仅需要保证算 法正确，还要考虑算法的质量，选择合 适的算法
用图形表示算法，直观形象，易于理解
位置不够
① 起止框 输入输出框 ② 判断框 防止交叉 处理框
流程线
连接点
注释框
学习方法－熟练掌握基本知识，重在动手实践学习
例2.8 例2.3判定闰年的算法用流程图表 示。判定2000—2500年中的每一年是否 闰年，将结果输出。
学习方法－熟练掌握基本知识，重在动手实践学习 开始

第二章程序的灵魂-算法概要


举例： 张丘建《算经》中提出“百鸡问题”鸡翁一值钱五，鸡母一值钱三， 鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？（体会编程步骤）
① 分析 ：cocks+hens+chicks=100 5﹡cocks+3﹡hens+chicks/3=100 其中：0≤cocks≤19 0≤hens≤33 0≤chicks≤100 思路：依次取cocks的值域中的值，然后求其余两数，看是 否合乎题意
§ 2.2 算法的描述方法 常用的算法描述方法：
① 带序号的自然语言描述（例2.1源自例2.5），易懂却不直观，不严格 ② 流程图：灵活、 自由、 形象、直观， 可表示任何算法
输入/输出 处理
判断
起止
连接点 流程线
③ N-S图(盒图)：特点：完全去掉了带箭头的流程线，算法的 所有处理步骤都写在一个大矩形框(表示简单、符合结构化思想)
② 用计算机语言写出程序
void main() { int cocks=0,hens,chicks; while(cocks<=19) {hens=0; while(hens<=33) {chicks=100-cocks-hens; if(5﹡cocks+3﹡hens+chicks/3==100) printf(“%d %d %d\n”,cocks,hens,chicks); hens++; } cocks++ } }
CH2 程序的灵魂——算法
内容提要：
算法及其算法的表示方法 结构化程序设计方法 程序、程序设计和程序设计语言
著名计算机科学家沃思（Nikiklaus Wirth)提出 数据结构+算法=程序
描述数据的类型、 组织形式 描述对数据的 操作步骤

第2章 算法---程序的灵魂


判断框 防止交叉 处理框
流程线
连接点
注释框
开始
例2.6 将例2.1的算法用流程图表示。 求1×2×3×4×5 如果需要将最后结果输出:
S1：使p=1，或写成1p
1t
2i t*it i+1i N
S2：使i=2，或写成2i
S3：使p与i相乘，乘积仍放在变量p中，可
表示为： p*ip S4：使i的值加1，即i+1 i S5：如果i不大于5，返回重新执行S3；否则， 算法结束 最后得到p的值就是 5!的值
由三种基本结构派生出来的结构：
B
A
根据表达式p 的值进行选择
Y
p2 N A B … M N
例2.11将例2.1的求5!算法用N-S图表示。
开始
1t
2i t*it i+1i N i>5 Y 结束
1t
2i
t*it
i+1i
直到i>5 输出t
例2.12 将例2.2的算法用NS图表示。将50名学生中 成绩高于80分者的学号和 成绩输出。
可以用最原始的方法进行： 步骤1：先求1*2，得到结果2。 步骤2：将步骤1得到的乘积2再乘以3，得到结果6。 步骤3：将6再乘以4，得24。 步骤4：将24再乘以5，得120。这就是最后的结果。
太繁琐
例2.1 求1×2×3×4×5 S1：使p=1，或写成1p S2：使i=2，或写成2i 3 3 S3：使p与i相乘，乘积仍放在变量p中，可表示为： p*ip 相当于i ≦11 S4：使i的值加1，即i+1 i 2 2 S5：如果i不大于5，返回重新执行S3；否则，算法结束 11 最后得到p的值就是11! 5!的值 若是1000，求什么？

第2章 算法---程序的灵魂

算法描述：
用变量ni放第i个学生学号，用变量gi放第i个学生成绩（ 假设学生的学号和成绩已经分别放到这两组变量中了
i从1取到50)
S1：1i
//下标从1开始，即，从第一个学生成绩开始检查
，否则不输出 //下标加1，即，准备检查下一个学生
S2：如果gi≥80，则输出ni和gi S3：i+1i
int main() A B
T
输入n:
F
{
n%2==0
int n;
scanf("%d",&n); if(n%2==0)
printf("%d是偶数\n",n);
b p Y A N B
输出 n是偶数 输出 n不是偶数
else
结束 printf("%d不是偶数\n",n);
输入n n%2==0 真 输出 n是偶数 假 输出 n不是偶数
2
3
4
1 1 99 100

算法描述：



S1：sign=1 -- 给出第一个符号 S2：sum=1 -- 给出第一个被加数 S3：deno=2 -- 给出第一个加数的分母 S4：sign=-sign -- 求当前项的符号 S5：term=sign/deno -- 求出当前项 S6：sum=sum+term -- 累加上所求出的项 S7：deno=deno+1 -- 求出下一项的分母 S8：若deno≤100返回S4；否则算法结束 -- 99次循环后sum的值就是所要求的结果

如，a/b当b=0时，或负数开平方根等运算都是无效的，是应该 避免的
11
2.4.1 五种表示算法的方法
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第二章程序的灵魂—— 算法
PPT文档演模板
2020/12/10
第二章程序的灵魂——算法
程序设计概述
一个程序应包括对数据的描述和对数据处理的描述。 1．对数据的描述，即数据结构。数据结构是计算机学 科的核心课程之一，有许多专门著作论述，本课程就不再 赘述。 在C语言中，系统提供的数据结构，是以数据类型的形 式出现的。 2．对数据处理的描述，即计算机算法。算法是为解决 一个问题而采取的方法和步骤，是程序的灵魂。为此，著 名计算机科学家沃思（Nikiklaus Wirth）提出一个公式：
• 例如：不需要输入任何信息，就可以计算出5！；（0个 输入）
• 例如：如果要计算两个整数的最大公约数，则需要输入2 个整数m，n。（2个输入）
• 4、有1个或多个输出（即算法必须得到结果） • 算法的输出：算法得到的结果。算法必须有结果，没有
结果的算法没有意义。（结果可以是显示在屏幕上的， 也可以是将结果数据传递给程序的其它部分） • 5、有效性 • 算法的每个步骤都应当能有效执行，并能得到确定的结 果。例如：b=0，则执行a/b是不能有效执行的。
PPT文档演模板
第二章程序的灵魂——算法
PPT文档演模板
•例： 求5！
•开始
•t=1 •i=2 •t=t*i •i=i+1
• N •i>5
•Y
•结束
第二章程序的灵魂——算法
• 传统流程图采用流程线指出各框的执行顺序，对 流程线的使用没有严格限制。因此，使用者可以 不受限制地使流程转来转去，使流程图变得毫无 规律。人们对这种流程图进行改进，规定几种基 本的结构，然后由这些基本结构按一定规律组成 算法结构，整个算法结构是由上而下地将各个基 本结构顺序排列起来。这样可以在一定程度上， 提高算法的质量。
PPT文档演模板
第二章程序的灵魂——算法
•买电视机的步骤：
•选好货物 •开票 •付款 •拿发票 •取货
•回家
•考大学上大学的步骤
•填报名单 •交报名费
•拿准考证
•参加考试
PPT文档演模板
•报到注册
•得到录取通知书
第二章程序的灵魂——算法
2.2、 简单算法举例
例1 求1×2×3×4×5。 可先写出这样的算法：
• 依次顺序执行程序语句
•执行a块 •执行b块
•例如，令a、b的值 •分别为5、10； • a = 5； • b = 10；
•A
•a块
•b块
•B
第二章程序的灵魂——算法
(2)判别选择结构程序设计
• 首先判别条件，若条件满足，程序执行 a块，否则，执行b块；
• 举例，求a、b两个 数中的最大值；
•满足•满足条件否•不满足
作为程序来使用，最后还需转换成用某种程序设计 语言所描述的程序。
◆与程序设计语言的区别：
前者比较自由，不象后者那样受语法的约束，只要
描述得人们能理解就行，而不必考虑计算机处理时
所要遵循的规定或其它一些细节。 PPT文档演模板
第二章程序的灵魂——算法
2.4.2 用流程图表示算法
•一、流程的描 在程序设计过程中，一般述不可能在一开始就用某种
PPT文档演模板
第二章程序的灵魂——算法
算法如下：设y为被检测的年份，可采取以下步骤：
s1: 2000 y; s2: 若y不能被4整除，则输出y “不是闰年”。然后转到s6. S3: 若y能被100整除，又能被400整除，输出y “是闰年”，
否则输出“不是闰年”。然后转到s6。 S4: 若y 能被100整除，又能被400整除，输出y “是闰年”，
• 自然语言就是人们常用的语言，可以是汉 语、英语或其他语言。
•用自然语言表示通俗易懂； •但文字冗长，容易出现“歧义”性；
•而且，用自然语言描述包含分支和循环 的算法，不很方便。
•一般不使用自然语言描述算法
PPT文档演模板
第二章程序的灵魂——算法
•自然语言描述举例
例如：描述计算并输出z=y/x的流程，可以用自 然语言描述如下： （1）输入x，y。 （2）判断x是否为0：
学生，第几个成绩）。当 i超过50时，表示已对50 个学生的成绩处理完毕，算法结束。
PPT文档演模板
第二章程序的灵魂——算法
例4
判断2000年---2500年中的每一年是否闰 年，将结果输出。
解：闰年的条件是：(1)能被4整除，但 不能被100整除的年份是闰年；如1996， 2004年(2)能被100整除，又能被400整除 的年份是闰年。如1600，2000年。不符 合这两个条件的年份不是闰年。
•Max = a；
•执行a块 •执行b块
•Y
•N
•b >max？
•max = b；
•成立
•不成立
•条件成立？
•执行a块
•执行b块
PPT文档演模板
第二章程序的灵魂——算法
(3)循环结构程序设计
• 循环又分“当型循环”和“直到型循环”
•当条件满足时
•执行循环中的指令
•执行循环中指令
•直到条件满足为止
• 举例，求1~100的累加和。
PPT文档演模板
第二章程序的灵魂——算法
•2.4. 怎法表示方法：
•
自然语言，传统流程图，结构化流程
图（N-S流程图），伪代码、计算机语言等。
（重点：传统流程图，N-S流程图）
PPT文档演模板
第二章程序的灵魂——算法
•2.4.1 用自然语言表示算 法
第二章程序的灵魂——算法
求1×3×5×7×9 ×11
请同学们仔细分析循环结束的条件，即s5 步骤，如果在求求1×3×5×7×9 ×11时， 将s5步骤写成： s5：若I<11，返回s3。 这样会有什么问题？会得到什么结果？
PPT文档演模板
第二章程序的灵魂——算法
例3
有50个学生，要求将他们之中成绩在80 分以上者打印出来。
（1）先求1×2，得到结果2； （2）将步骤1得到的结果再乘以3，得到结
果6； （3）将6再乘以4，得到24； （4）将24再乘以5，得到120。
PPT文档演模板
第二章程序的灵魂——算法
求1×2×3×4×5
• 上述算法太繁琐，我们找一种通用 的表示方法。
S1:设变量p，被乘数，p=1;
s2:设变量i,代表乘数，i=2;
l连接点：用于将画在不同地方的流程线连接起来。同一 个编号的点是相互连接在一起的，实际上同一编号的点是 同一个点，只是画不下才分开画。使用连接点，还可以避 免流程线的交叉或过长，使流程图更加清晰。
l注释框：注释框不是流程图中必须的部分，不反映流程 和操作，它只是对流程图中某些框的操作做必要的补充说 明，以帮助阅读流程图的人更好地理解流程图的作用。
若X=0,则输出错误信息； 否则计算 y/x z，且输出z。
PPT文档演模板
第二章程序的灵魂——算法
•算法描述语 ◆算法描述语言：是为了言说明程序的流程而专门规定
的某种语言。它一般介于自然语言与程序设计语言 之间，它具有自然语言灵活的特点，同时又接近于 程序设计语言的描述。
◆注意：算法描述语言所描述的流程，一般不能直接
• 例如：“将成绩优秀的同学名单打印输出”就是有歧义 的。“成绩优秀”是要求每门课程都90分以上，还是平 均成绩在90分以上？不明确，有歧义，不适合描述算法 步骤。
PPT文档演模板
第二章程序的灵魂——算法
• 3、有0个或多个输入（即：可以没有输入，也可以有输 入）
• 所谓输入是指算法执行时从外界获取必要信息。（外界 是相对算法本身的，输入可以是人工键盘输入的数据， 也可以是程序其它部分传递给算法的数据）
• 事实上“有穷性”往往指“在合理的范围之内”的有限 步骤。如果让计算机执行一个历时1000年才结束的算法， 算法尽管有穷，但超过了合理的限度，人们也不认为此 算法是有用的。
• 2、确定性：算法中的每一个步骤都应当是确定的，而不 是含糊的、摸棱两可的。也就是说不应当产生歧义。特 别是算法用自然语言描述时应当注意这点。
s3:使p×i,乘积放在被乘数变量p中，可
表示为：p× i
p;
s4:使i的值加1，即i+1 i;
s5:如果i不大于5，返回重新执行步骤 s3以及其后的s4、s5;否则，算法结
束。最后得到的p就是5!的值。
PPT文档演模板
第二章程序的灵魂——算法
PPT文档演模板
例2.求1×3×5×7×9 ×11
• 如果题目改为求1×3×5×7×9 ×11。 上述算法稍作改动： s1: 1 p; s2: 3 i; s3: p ×i p; s4: i+2 i s5: 若i11,返回s3;否则，结束。
（4）N+1 N；
（5）若N≤100，转去执行（3）以及其后的各步骤； 否则执行（6）；
（6）打印S的值（即所求之总和）。
PPT文档演模板
第二章程序的灵魂——算法
2.3. 算法的特性
• 1、有穷性：一个算法应当包含有限的步骤，而不能是无 限的步骤；同时一个算法应当在执行一定数量的步骤后， 算法结束，不能死循环。
解：用n表示学生学号，n1代表第一个学 生学号，ni 代表第i 个学生学号。用g代 表学生成绩，gi代表第i个学生成绩，算 法表示如下：
PPT文档演模板
第二章程序的灵魂——算法
S1: 1 i;
S2: 如果gi80,则打印ni和gi,否则不打印。 S3: i+1 i; S4: 如果i50,返回s2,继续执行，否则算法结束。 本例中，变量i作为下标，用它来控制序号（第几个
PPT文档演模板
第二章程序的灵魂——算法
•2.4.3 三种基本结构和改进的流程 图
★三种基本结构是：