当前位置：文档之家 › 算法程序的灵魂.ppt

算法程序的灵魂.ppt

  • 格式：ppt
  • 大小：1.82 MB
  • 文档页数：105

下载文档原格式

  / 105

合集下载

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

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

键盘输 入某一 年份， 年份， 判定是 否是闰 年
输入年份nyear y nyear能被4整除 n
nyear不能被100整除
N-S 流
y
n
nyear能被400整除
nyear
y nyear nyear 不 是 闰 年
n
nyear 不 是 闰 年
年 年
键盘输入10个数，找出其中的最大数并输出
输入x max=x I=1 I<10成立 输入x max<x
定的， 定的，不能模棱两可
（3）有零个或多个输入：在执行算法时从外 ）有零个或多个输入：
界取的必要的信息
（4）有一个或多个输出：即算法的求解 ）有一个或多个输出： （5）有效性：算法中每一个步骤都应当能 ）有效性：
有效执行
（1）自然语言表示法 ）
算 法 的 表 示
Q：将分别装有醋和酱油的两个杯子里面的内容 ： 交换。 交换。 分析： 分析：借用第三个杯子 （空杯） 空杯） Algorithm： ： Step1:将装有醋的杯子的内容倒入空杯 将装有醋的杯子的内容倒入空杯 Step2:将装有酱油的杯子的内容倒入原装醋的杯 将装有酱油的杯子的内容倒入原装醋的杯 子里 Step3:将现装有醋的杯子的内容倒入原 将现装有醋的杯子 将现装有醋的杯子的内容倒入原 装酱油的杯子里
X1 x1
Y
条件P
N
模块A
模块B
Q：键盘 输入任 意数并 输出算 术平方 根。
N X1>=0 x1>=0 Y Y1=sqrt(x1)
Y1
结束
循环结构
N N
传统 流程 图之 三种 基本 结构
条件P Y Y 模块A A
模块A Y Y

c 第二章 程序的灵魂―算法1PPT课件

c 第二章 程序的灵魂―算法1PPT课件

A B
图 2.21 死循环
28
基本结构
a
A
B
P1 Y N
b
图 2.22
a
根据表达式的 值进行选择
p=ห้องสมุดไป่ตู้1 p=p2
AB
…
p=pm p=pn MN
○ b
29
2.4.4 用N-S流程图表示算法
A B 图 2.24 顺序结构
p
成立
不成立
A
B
图 2.25 分支结构
30
当P1成立 A
图 2.26 当型循环
25
直到型循环
x= 0
x = x+1
打印x x≥5 N Y 图 2.19
以上2个框图的 作用是打印5个 数
26
只有一个入口； 只有一个出口；
注意：菱形框有2个出口，选择结构的 出口只有一个； 结构内的每一部分都有机会被执行到； 结构内不存在“死循环”；
27
A P1
图 2.20 菱形框、分支结构
10
算法 s1:sign=1 s2:deno=2 s3:sum=1 s4:sign=(-1) ×sign s5:term=sign ×(1/deno) s6:sum=sum+term s7:deno=deno+1 s8:若deno≤100返回s4;否则算法结束。
11
例２.5 对于一个大于或等于３的正整数，判 断它是不是一个素数。 算法： s1:输入n的值; s2:i=2; s3:n被i除，得余数r; s4:如果r=0,表示n能被i整除，则打印n “不是素 数” ，算法结束；否则执行s5;
y≥2500时，算法结束。
8
图 2.1
9

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

第二讲算法---程序的灵魂
信息工程学院 王垚
用传统流程图表示算法
流程图是用一些图框来表示各种操作 用图形表示算法，直观形象，易于理解
起止框
输入输出框
判断框
处理框
流程线
连接点
注释框
信息工程学院 王垚
用传统流程图表示算法
开始
1p 2i
p*ip i+1i N
2 6 24 120 3 4 5 6>5结束
i>5
Y
结束
信息工程学院 王垚
信息工程学院 王垚
2.3算法的特性
对于一般最终用户来说: 他们并不需要在处理每一个问题时都要自己设 计算法和编写程序 可以使用别人已设计好的现成算法和程序 只需根据已知算法的要求给予必要的输入，就 能得到输出的结果 输入3个数 求3个数的 黑箱子 最大数 3个数中最大数
信息工程学院 王垚
信息工程学院 王垚
Y
p
N
Y
p
N
A
B
A
顺序流程图
信息工程学院 王垚
三种基本结构的流程图
2. 选择结构
p Y A
N
B
N-S流程图
信息工程学院 王垚
三种基本结构的流程图
输出1,2,3,4,5 3.循环结构 （1） 当型循环结构
0x x<5 Y 输出x的值 x+1x N
p1 Y A
N
顺序流程图
信息工程学院 王垚
三种基本结构的流程图
信息工程学院 王垚
思考：
任意输入一个数据的阶乘是多少？
#include <stdio.h> int main( ) { int i,p,x; p=1; i=2; scanf("%d",&x); while(i<=x) { p=p*i; i=i+1; } printf("%d\n",p); return 0; }

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

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

S1: 1 i;
S2: 如果gi80,则打印ni和gi,否则不打印。 S3: i+1 i; S4: 如果i50,返回s2,继续执行，否则算法结束。 本例中，变量i作为下标，用它来控制序号（第几个
学生，第几个成绩）。当 i超过50时，表示已对50 个学生的成绩处理完毕，算法结束。
例4
判断2000年---2500年中的每一年是否闰 年，将结果输出。
束。最后得到的p就是5!的值。
例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;否则，结束。
求1×3×5×7×9 ×11
可以看出，用这种方法表示的算法 具有通用性、灵活性。S3到s5 组成一个 循环，在实现算法时，要反复多次执行 s3、s4、s5等步骤，直到某一时刻，执 行s5步骤时经过判断，乘数i已超过规定 的数值而不返回s3步骤为止。
•N-S流程图适于结构化程序设计
顺序结构程序设计
•依次顺序执行程序语句 执行a块 执行b块
先执行a操作，再执行b操作
判别选择结构程序设计
满足条件否
满足
不满足
执行a块 执行b块
•当条件成立，执行a操作，当条件不成立，执行b操作。 a，b操作允许空操作，即什么都不做。注意选择结构 是一个整体，代表一个基本结构。
买电视机的步骤：
选好货物 开票 付款
拿发票
取货
回家
考大学上大学的步骤
填报名单 交报名费
拿准考证
参加考试
报到注册
得到录取通知书
2.2、 简单算法举例

程序的灵魂--算法(共23张PPT)

程序的灵魂--算法(共23张PPT)
但是用伪代码写算法不如流程图直观，可能会出 现逻辑上的错误（例如循环或选择结构的范围搞错 等）
4.6 用计算机语言表示算法
计算机是无法识别流程图和伪代码的。只有用计算机语 言编写的程序经编译成为目标程序后，才能被计算机执 行。因此，在用流程图或伪代码描述出一个算法后，还 要将它转换成计算机语言程序。
循环结构
三种基本结构的特点:
(1)只有一个入口.a点为入口点。
(2)只有一个出口,b点为出口点。
注:一个菱形判断框有两个出口,而一个选择结构只 S2：若Y不能被4整除，则输出Y“不是闰年”。
每一行(或几行)表示一个基本操作. S7: deno=deno+1
有一个出口。 S2：若Y不能被4整除，则输出Y“不是闰年”。
自然语言表示的含义往往不太严格，要根据 上下文才能判断其正确含义。
用自然语言描述包含分支和循环的算法，不 很方便。
除了很简单的问题以外，一般不用自然语言描 述算法。
4.2 用流程图表示算法
流程图是用一些图框表示各种操作。 ANSI规定了一些常用的流程图符号，为世界 各国程序员普遍采用。
Y X>=0? N
A
B
选择结构
当P1成立
A
当型循环
A
直到P1成立 直到型循环
N-S流程图的优点：
N-S流程图比文字描述直观、形象、易于理解；由 S2: sum=1 于它废除了流程线，所以它比传统流程图紧凑易画，
[例4]求1-1/2+1/3-1/4+…+1/99-1/100
S3：将6再乘以4整，得个到24算。 法结构是由各个基本结果按顺序组成的。
循环结构
流程图表示的算法都是结构化算法。 S4：若Y能被100整除，又能被400整除，则输出

程序的灵魂-算法

程序的灵魂-算法

2.3算法的特性
一个算法应具有以下特点: 1.有穷性 2.确定性 3.有零个或多个输入 4.有一个或多个输出 5.有效性 程序设计人员设计算法,并根据算法编写程序
2.4 怎样表示一个算法 1.用自然语言表示算法
通俗易懂，但文字冗长，容易产生歧义。
2.用流程图表示算法
直观形象，容易理解。
例1 用流程图表示算法：１×２×３×４×５
用计算机语言表示算法
求５！用c语言表示．
main( ) {int i,t;
t=1; i=2; while(i<=5){
t=t*i; i=i+1;} printf("%d",t); }
/* 120 */
2.5 结构化程序设计方法
一个结构化程序就是用高级语言表示的结 构化算法 • 用三种基本结构组成的程序必然是结构 化程序
p×i=>p i+1=>i
当型循环
用伪代码表示算法
伪代码是用介于自然语言和计算机语言之的文 字和符号来描述算法。
例如，“打印x的绝对值”．
IF x is positive THEN print x
ELSE print -x
中文伪代码： 若 x 为正
打印 x 否则
打印 -x
中英文混用: IF x 为正
S5: 输出y“不是闰年”
S6: y+1=>y S7: 当y≤2500时转S2，否则算法结束
例4 求 1- ½ + 1/3 + … + 1/99 - 1/100
算法： S1: sign=1 S2: sum=1 S3: deno=2 S4: sign=-sign S5: term=sign×(1/deno) S6: sum=sum+term S7: deno=deno+1 S8: 若deno≤100返回S4,否则算法结束

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


举例： 张丘建《算经》中提出“百鸡问题”鸡翁一值钱五，鸡母一值钱三， 鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？（体会编程步骤）
① 分析 ：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)提出 数据结构+算法=程序
描述数据的类型、 组织形式 描述对数据的 操作步骤

程序的灵魂---算法41页PPT


谢谢！
36、自己的鞋子，自己知道紧在哪里。——西班牙
37、我们唯一不会改正的缺点是软弱。——拉罗什福科
xiexie! 38、我这个人走得很慢，但是我从不后退。——亚伯拉罕·林肯
39、勿问成功的秘诀为何，且尽全力做你应该做的事吧。。——孔子
1、不要轻言放弃，否则对不起自己。
2、要冒一次险!整个生命就是一场冒险。走得最远的人，常是愿意 去做，并愿意去冒险的人。“稳妥”之船，从未能从岸边走远。-戴尔．卡耐基。
梦 境
3、人生就像一杯没有加糖的咖啡，喝起来是苦涩的，回味起来却有 久久不会退去的余香。
程序的灵魂---算法4、守业的最好办法就是不断的发展。 5、当爱不能完美，我宁愿选择无悔，不管来生多么美丽，我不愿失 去今生对你的记忆，我不求天长地久的美景，我只要生生世世的轮 回里有你。

算法PPT课件


2.2简单的算法举例
➢ S1：使p=1，或写成1p
➢ S2：使i=2，或写成2i
➢ S3：使p与i相乘，乘积仍放在变量p中，可表
示为：p*ip
若是1000，求什么？
➢ S4：使i的值加1，即i+1 i
➢ S5：如果i不大于5，返回重新执行S3；否则 ，算法结束
➢ 最后得到p的值就是 5!的值
若2求.21简×3单×的5×算7×法9×举11例
➢ S4：sign=(-1)*sign -1/2
➢ S5：term=sign*(1/deno) 1-1/2
➢ S6：sum=sum+term 3 ➢ S7：deno=deno+1
满足，返回S4
➢ S8：若deno≤100返回S4；否则算法结束
例2.4 求 1 1 1 1 1 1
234
➢ 用ni代表第i个学生学号，gi表示第i个学生成绩 S1：1i S2：如果gi≥80， 则输出ni和gi，否则不输出 S3：i+1i S4：如果i≤50，返回到步骤S2，继续执行， 否则，算法结束
例2.3 判定2000—2500年中的每一年是 否闰年，并将结果输出。
➢闰年的条件：
(1)能被4整除，但不能被100整除的年份都是 闰年，如2008、2012、2048年 (2)能被400整除的年份是闰年，如2000年 不符合这两个条件的年份不是闰年 例如2009、2100年
➢算法是解决“做什么”和“怎么做”的 问题
➢程序中的操作语句，是算法的体现 ➢不了解算法就谈不上程序设计
2.1 什么是算法 2.2 简单的算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法
2.1 什么是算法

程序的灵魂算法1课件ppt


定解决方案和步骤（算法），再利用计算机能够识
别的语言编写程序，最后进行调试、输出结果。这
就是程序设计的一般过程。
一、复习巩固·程序设计的过程
程序设计
明确问题
编制程序
解决问题
确定算法 调试程序
生活实际
做什么—怎么做—实干—复查—完成
一、例题回顾·程序设计的过程
【探究学习】
3. 编写VB程序，体会程序设计的过程。
Print S
输出面积
二、算法的概念
• 用计算机编程来解决问题，首先应该确定解 决问题的思路和方法，并写出正确的求解步 骤，这就是算法。
• 简单来说，算法是解决问题的方法和步骤。
讨论·思考
• 一位农夫要带一只狼、一只羊和一棵白菜 过河，如果没有农夫看管，狼就要吃羊， 羊就要吃白菜，船又很小，只够农夫带一 样过河。农夫此时应该怎么做呢？
• 1. 1+2+3+4+……+100的值
• 2. 1-2+3-4+5-6+……+99-100的值
三、算法的描述
• 算法是解决问题的方法和步骤。那么算法就
可以用不同的方式来进行描述，如自然语言 、流程图等。
自然语言描述算法
• 前面的“烧水泡茶”就是利用自然语言进行描 述的。
• 用自然语言描述的算法易理解，适用于描述简 单的算法。但也会差生歧义：
• 【例：】阅读自然语言描述的语句，写出相应 的语句。 “将a加b除以a减b的值赋值给变量x”
流程图描述算法
• 当算法较为复杂时，自然语言描述则会显得烦 琐、冗长，此时就可以用流程图来描述算法。
• 流程图：就是用图形符号来描述解决问题的过 程。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
操作的目的是对数据进行加工处理，以 得到期望的结果
著名计算机科学家沃思(Nikiklaus Wirth) 提出一个公式：
算法 + 数据结构 = 程序
一个程序除了算法和数据结构这主要要 素外，还应当采用结构化程序设计方法 进行程序设计，并且用某一种计算机语 言表示
算法、数据结构、程序设计方法和语言 工具是一个程序设计人员应具备的知识
算法结束
最后得到p的值就是 5所!的求值的值
例2.2 有50个学生，要求将成绩在80分以上 的学生的学号和成绩输出。
用ni代表第i个学生学号，gi表示第i个学生成绩 S1：1i
S2：如果gi≥80， 则输出ni和gi，否则不输出
S3：i+1i
S4：如果i≤50，返回到步骤S2，继续执行，否 则，算法结束
闰年 year被100 整除，又能 被400整除
其他 非闰年
year不能 被4整除
非闰年
year被4整 除，但不能 被100整除
闰年
逐渐缩小判 断的范围
例2.4 求 1 1 1 1 1 1
234
99 100
规律：
①第1项的分子分母都是1
② 第2项的分母是2，以后每一项的分母子都是 前一项的分母加1
S1：sign=1 S2：sum=1 S3：deno=2
99次循环后sum的值 就是所要求的结果
S4：sign=(-1)*sign
S5：term=sign*(1/deno)
S6：sum=sum+term
S7：deno=deno+1
S8：若deno≤100返回S4；否则算法结束
例2.5 给出一个大于或等于3的正整数，判 断它是不是一个素数。
所谓素数(prime)，是指除了1和该数本身 之外，不能被其他任何整数整除的数
改进的算法：
设变量p为被乘数 变量i为乘数 用循环算法求结果
2.2简单的算法举例
S1：使p=1，或写成1p
S2：使i=2，或写成2i
S3：使p与i相乘，乘积仍放在变量p中，可表示
为：p*ip
若是1000，求什么？
S4：使i的值加1，即i+1i
S5：如果i不大于5，返回重新执行S3；否则， 算法结束
S4：sign=(-1)*sign S5：term=sign*(1/deno) S6：sum=sum+term
1/3 1-1/2+1/3

S7：deno=deno+1
4 满足，返回S4
S8：若deno≤100返回S4；否则算法结束
例2.4 求 1 1 1 1 1 1
234
99 100
对同一个问题，可以有不同的解题方法 和步骤
为了有效地进行解题，不仅需要保证算 法正确，还要考虑算法的质量，选择合 适的算法
2.1 什么是算法
计算机算法可分为两大类别： 数值运算算法 非数值运算算法
数值运算的目的是求数值解
非数值运算包括的面十分广泛，最常见 的是用于事务管理领域
2.2简单的算法举例
最后得到p的值就是 5!的值
若2.求2简1×单3×的5×算7×法9举×1例1
S1：使p=1，或写成1p
S2：使i=23，或写成23i
S3：使p与i相乘，乘积仍放在变量p中，可表示 为：p*ip
S4：使i的值加12，即i+12i
相当于i ≦11
S5：如果i不大于151，返回重新执行S3；否则，
算法是解决“做什么”和“怎么做”的 问题
程序中的操作语句，是算法的体现
不了解算法就谈不上程序设计
2.1 什么是算法 2.2 简单的算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法
2.1 什么是算法
广义地说，为解决一个问题而采取的方 法和步骤，就称为“算法”
例例22..11 求求11××22××33××44××55× …×1000
可以用最原始的方法进行：
步骤1：先求1*2太，繁得到琐结果2。
步骤2：将步骤1得到的乘积2再乘以3，得 到结果6。
步骤3：将6再乘以4，得24。 步骤4：将24再乘以5，得120。这就是最后
的结果。
2.2简单的算法举例
-1/2 1-1/2
S7：deno=deno+1
3 满足，返回S4
S8：若deno≤100返回S4；否则算法结束
例2.4 求 1 1 1 1 1 1
234
99 100
S1：sign=1 S2：sum=1 S3：deno=2
sign—当前项符号 term—当前项的值 sum—当前各项的和 1 deno—当前项分母
③ 笫2项前的运算符为“-”，后一项前面的运 算符都与前一项前的运算符相反
例2.4 求 1 1 1 1 1 1
234
99 100
S1：sign=1 S2：sum=1 S3：deno=2
sign—当前项符号 term—当前项的值 sum—当前各项的和 -1 deno—当前项分母
S4：sign=(-1)*sign S5：term=sign*(1/deno) S6：sum=sum+term
例2.3 判定2000—2500年中的每一年是否 闰年，并将结果输出。
闰年的条件：
(1)能被4整除，但不能被100整除的年份都是闰 年，如2008、2012、2048年
(2)能被400整除的年份是闰年，如2000年 不符合这两个条件的年份不是闰年 例如2009、2100年
设year为被检测的年份。算法表示如下： S1：2000year S2：若year不能被4整除，则输出year 的值和 “不是闰年”。然后转到S6 S3：若year能被4整除，不能被100整除，则 输出year的值和“是闰年”。然后转到S6 S4：若year能被400整除，则输出year的值和 “是闰年” ，然后转到S6 S5: 其他情况输出year的值和“不是闰年” S6：year+1year S7：当year≤2500时，转S2，否则停止
第2章 算法---程序的灵魂
一个程序主要包括以下两方面的信息：
(1) 对数据的描述。在程序中要指定用到哪些 数据以及这些数据的类型和数据的组织形式
这就是数据结构(data structure)
(2) 对操作的描述。即要求计算机进行操作的 步骤
也就是算法(algorithm)
数据是操作的对象