1.1算法与程序框图


1.1算法与程序框图

求解:二元一次方程组 解: 第一步,

x-2y=-1 ①
2x+y=1




①+②×2,得 5x=1 . 解③,得

第二步,
第三步, 第四步,

1 x? . 5


②-①×2,得 5y=3 . 解④,得

3 y .? 5

第五步,

得到方程组的解为

3 y? 5

1 x? 5

思考1:你能写出求解一般的二元一次方程组的步 骤吗?

a1 x ? b1 y ? c1 a2 x ? b2 y ? c2
其中

a1b2 ? a2 b1 ? 0

b b ①× ②× , 得 2 1 第一步: (a1b2 ? a2b1 ) x ? b2c1 ? b1c2
第二步:解③ ,得 x ? b2c1 ? b1c2 第三步:②×a1 - ①× a2 ,得
a1b2 ? a2b1



(a1b2 ? a2b1 ) y ? a1c2 ? a2c1 ④
b2 c1 ? b1c2 x? a1b2 ? a2b1 a1c2 ? a2 c1 y? a1b2 ? a2b1

a1c2 ? a2 c1 第四步: 解 ④ ,得 y ? a b ? a b 1 2 2 1

第五步: 得到方程组的解为

思考2:根据上述分析,用加减消元法 解二元一次方程组,可以分为五个步骤进 行,这五个步骤就构成了解二元一次方程 组的一个“算法”.我们再根据这一算法编 制计算机程序,就可以让计算机来解二元 一次方程组.那么解二元一次方程组的算法 包括哪些内容?

思考3:一般地,算法是由按照一定规则解决某 一类问题的基本步骤组成的. 你认为: (1)这些步骤的个数是有限的还是无限的? (2)每个步骤是否有明确的计算任务? 总结:在数学中,按照一定规则解决某一类问 题的明确和有限的步骤称为算法.

例1:如果让计算机判断7是否为质数,如何设计 算法步骤?

第一步,用2除7,得到余数1,所以2不能整除7. 第二步,用3除7,得到余数1,所以3不能整除7.
第三步,用4除7,得到余数3,所以4不能整除7. 第四步,用5除7,得到余数2,所以5不能整除7.

第五步,用6除7,得到余数1,所以6不能整除7.
因此,7是质数.

练习1:如果让计算机判断35是否为质数,如何设 计算法步骤? 第一步,用2除35,得到余数1,所以2不能整除35.
第二步,用3除35,得到余数2,所以3不能整除35. 第三步,用4除35,得到余数3,所以4不能整除35. 第四步,用5除35,得到余数0,所以5能整除35.

因此,35不是质数.

练习2:整数89是否为质数?如果让计算机判断

89是否为质数,按照上述算法需要设计多少个步骤?
第一步,用2除89,得到余数1,所以2不能整除89. 第二步,用3除89,得到余数2,所以3不能整除89. 第三步,用4除89,得到余数1,所以4不能整除89. …… 第八十七步,用88除89,得到余数1,所以88不能 整除89. 因此,89是质数.

思考4:用2~88逐一去除89求余数,需要87个步 骤,这些步骤基本是重复操作,我们可以按下面的思 路改进这个算法,减少算法的步骤.

(1)用i表示2~88中的任意一个整数,并从2开 始取数; (2)用i除89,得到余数r. 若r=0,则89不是质 数;若r≠0,将i用i+1替代,再执行同样的操作; (3)这个操作一直进行到i取88为止.
你能按照这个思路,设计一个“判断89是否为质 数”的算法步骤吗?

算法设计: 第一步,令i=2; 第二步,用i除89,得到余数r; 第三步, 若r=0,则89不是质数,结束算法;若r≠0, 将i用i+1替代; 第四步,判断“i>88”是否成立?若是,则89是 质数,结束算法;否则,返回第二步.

探究:一般地,判断一个大于2的整数是否为质数 的算法步骤如何设计? 第一步,给定一个大于2的整数n; 第二步,令i=2; 第三步,用i除n,得到余数r;

第四步,判断“r=0”是否成立.若是,则n不是
质数,结束算法;否则,将i的值增加1,仍用i表示; 第五步,判断“i>(n-1)”是否成立,若是,则n 是质数,结束算法;否则,返回第三步.

在中央电视台幸运 52 节目中 , 有一个猜商品价 格的环节 , 竟猜者如在规定的时间内大体猜出某种 商品的价格 , 就可获得该件商品 . 现有一商品 , 价格 在 0~8000 元之间 , 采取怎样的策略才能在较短的时 间内说出比较接近的答案呢? 第一步:报“4000”; 第二步 : 若主持人说高了 ( 说明答案在 0~4000 之间 ),就报“ 2000”,否则 (答数在 4000~8000之间 ) 报“6000”; 第三步:重复第二步的报数方法取中间数,直至 得到正确结果. 这其实蕴含了数学中“二分法”的思想.

二分法 对于在区间[a,b ]上连续不断,且 f(a)f(b)<0 的函数y=f(x),通过不断地把函数f(x)的零点所在 的区间一分为二,使区间的两个端点逐步逼近零 点,而得到零点近似值的方法叫做二分法.

例2:写出用“二分法”求方程 x 2 ? 2 ? 0( x ? 0) 的近似解的算法.

算法分析:

令f(x)=

x ? 2,则方程 x2 ? 2 ? 0( x ? 0) 的解就是
2

函数f(x)的零点.

y ? x ? 2 ( x ? 0)
2

m?

a?b 2

第一步,令f(x)=

x ? 2 ,给定精确度d.
2

第二步,确定区间[a,b],满足f(a)· f(b)<0.
a?b 第三步,取区间中点 m ? . 2

第四步,若f(a)· f(m)<0,则含零点的区间为[a,m],否 则,含零点的区间为[m,b]. 将新得到的含零点的区间仍记为[a,b]; 第五步,判断[a,b]的长度是否小于d或f(m)是否等于 0.若是,则m是方程的近似解;否则,返回第三步.

对于方程x ? 2 ? 0( x ? 0),当d=0.005,按照以上算法, 可以得到下表.
2

a 1 1 1.25 1.375 1.375 1.406 25 1.406 25 1.414 062 5 1.414 062 5

b |a-b| 2 1 1.5 0.5 1.5 0.25 1.5 0.125 1.437 5 0.062 5 1.437 5 0.031 25 1.421 875 0.015 625 1.421 875 0.007 812 5 1.417 968 75 0.003 906 25

小结: 计算机解决任何问题都要依赖算法,算法是建立 在解法基础上的操作过程,算法不一定要有运算结 果.设计一个解决某类问题的算法的核心内容是将解 决问题的过程分解为若干个明确的步骤,即算法,它 没有一个固定的模式,但有以下几个基本要求:

(1)符合运算规则,计算机能操作; (2)每个步骤都有一个明确的计算任务;
(3)对重复操作步骤作返回处理; (4)步骤个数尽可能少; (5)每个步骤的语言描述要准确、简明.

布置作业: P5练习:1,2.

1.1.2 程序框图与算法 的基本逻辑结构(1)

复习

引入新课

1. 算法是什么? 在数学中,按照一定规则解决某一类问题的明 确和有限的步骤称为算法. 2.算法是由一系列明确和有限的步骤组成的, 我们可以用自然语言表述一个算法,但往往过程复 杂,缺乏简洁性,因此,我们有必要探究使算法表 达得更加直观、准确的方法,这个想法可以通过程 序框图来实现.

程序框图的概念
程序框图又称流程图,是一种用程序框、流程线 及文字说明来表示算法的图形.程序框图是算法的一 种表示形式,也就是说,算法可以用算法步骤表示,也 可以用程序框图表示.

程序框图的基本符号 (1)起止框: 起止框是任何流程图都不可缺少的,它表示 一个算法的开始和结束,所以一个完整的流程图 的首末两端必须是起止框.

(2)输入、输出框:
表示一个算法输入和输出的信息,它可用在 算法中的任何需要输入、输出的位置.

(3)处理框: 它是用来赋值、执行计算语句、传送运算结 果的图形符号. (4)判断框:

判断框一般有一个入口和两个出口,它是 惟一的具有两个出口的符号,判断某一条件是 否成立,成立时在出口处标明“是”或“Y”,不 成立时标明“否”或“N”. (5)流程线:
用于连接程序框图

回顾:“判断整数n(n>2)是否为质数”的算法 步骤如何? 第一步,给定一个大于2的整数n;
第二步,令i=2; 第三步,用i除n,得到余数r;

第四步,判断“r=0”是否成立.若是,则n 不是质数,结束算法;否则,将i的值增加1,仍 用i表示; 第五步,判断“i>(n-1)”是否成立,若是, 则n是质数,结束算法;否则,返回第三步.

我们将上述 算法用右边的图 形表示:

开始

输入n
i=2 求n除以i的余数r

i的值增加1,仍用i表示

i>n-1或r=0?
是 r=0?

否 否
输 出 “ n 是质数”



输出“n不是质数”

结束

开始

输入n
i=2 求n除以i的余数r i的值增加1,仍用i表示 否

在这个程序 框图中,其中的 多边形就是程序 框,带方向箭头 的线就是流程线. 在此有4 种程序框,2 种流程线,还 记得它们的名 称和功能吗?
输 出 “ n 是质数 ”

i>n-1或r=0?
是 r=0? 是 输出“n不是质数” 否

结束

图形符号

名 称

功 能

终端框 (起止框) 输入、输出框 处理框 (执行框) 判断框 流程线

表示一个算法的起始和结束 表示一个算法输入和输出的 信息 赋值、计算 判断某一条件是否成立,成立 时在出口处标明“是”或 “Y”;不成立时标明“否” 或“N” 连接程序框

开始

输入n
i=2 求n除以i的余数 i的值增加1,仍用i表示 否

用程序框图 表示算法时,算 法的逻辑结构展 现得非常清楚. 在逻辑结构 上,“判断整数 n(n>2)是否为 质数”的程序框 图由几部分组成?
输 出 “ n 是质数 ”

i>n-1或r=0?
是 r=0? 是 输出“n不是质数” 否

结束

求n除以i的余数 输入n
i=2 i的值增加1,仍用i表示 否 i>n-1或r=0?

顺序结构



循环结构


r=0? 是 输出“n不是质数”

输 出 “ n 是质数 ”

条件结构

思考:任何一个算法各步骤之间都有明确的顺序 性,在算法的程序框图中,由若干个依次执行的步 骤组成的逻辑结构,称为顺序结构,用程序框图可 以表示为:

步骤n 步骤n+1

例3:若一个三角形的三条边长分别为a,b,c, 令 p ? a ? b ? c ,则三角形的面积

2

S ? p( p ? a)( p ? b)( p ? c)

这个公式被称为海伦-秦九韶公式,请利用这个公 式设计一个计算三角形面积的算法,并画出程序框 图表示. 第一步,输入三角形三条边的边长a,b,c.

a?b?c 第二步,计算 p ? 2
第四步,输出S.

.

第三步,计算 S ? p( p ? a)( p ? b)( p ? c) .

上述算法的程序框图如何表示?
开始

输入a,b,c

p=

a + b+ c 2

S = p( p - a )( p - b)( p - c)
输出S 结束

小结:
一、程序框图又称流程图,是一种用程序框、流程线

及文字说明来表示算法的图形.
二、三种逻辑结构:顺序结构、条件结构和循环结构 . 三、顺序结构的程序框图的基本特征: (1)必须有两个起止框,穿插输入、输出框和处理框, 没有判断框. (2)各程序框从上到下用流程线依次连接. (3)处理框按计算机执行顺序沿流程线依次排列.

1.1.2 程序框图与算 法的基本逻辑结构(2)

复习 1.用程序框、流程线及文字说明来表示算法的图形称 为程序框图,它使算法步骤显得直观、清晰、简明.

2. 程序框图由以下几种基本图形构成,它们表示的功 能分别如下:

终端框 输入、输 处理框 (起止框) 出框 (执行框)

判断框

流程线

3.顺序结构是任何一个算法都离不开的基本逻辑结构.

在一些算法中,有些步骤只有在一定条件下才会被 执行,有些步骤在一定条件下会被重复执行,这需要我

们对算法的逻辑结构作进一步探究.
在一个算法中,经常会遇到一些条件的判断,有些 步骤只有在一定条件下才会被执行,算法的流程因条件

是否成立有不同的流向.在算法的程序框图中,由若干
个在一定条件下才会被执行的步骤组成的逻辑结构,称

为条件结构,用程序框图可以表示为下面两种形式:

满足条件? 是 步骤A



满足条件?




步骤B

步骤A

例4:判断以任意给定的3个正实数为三条边边长 的三角形是否存在,设计一个算法,并画出这个算法 的程序框图. 第一步,输入三个正实数a,b,c. 第二步,判断a+b>c,b+c>a,c+a>b是否同时 成立.若是,则存在这样的三角形;否则,不存在这 样的三角形.

开始 输入a,b,c a+b>c , b+c>a , c+a>b 是否同时成立? 是 否

存在这样的三角形 结束

不存在这样的三角形

例5 设计一个求解一元二次方程ax2+bx+c=0的算法, 并画出程序框图表示. 第一步,输入三个系数a,b,c. 第二步,计算△=b2-4ac.
b 第三步,判断△≥0是否成立.若是,则计算 p ? ? 2a

? ;否则,输出“方程没有实数根”,结束算法. q? 2a

第四步,判断△=0是否成立.若是,则输出 x1=x2=p,否
则,计算x1=p+q,x2=p-q,并输出x1,x2.

开始 输入a,b,c

程序框图:

△ = b2 - 4 a c △ ≥0 ? 是
p?? b 2a
? 2a



q ?



△=0? 否 x1=p+q x2=p-q

输出x1=x2=p

输出x1,x2 结束

输出“方程没有实数根”

在一些算法中,经常会出现从某处开始,按照一


的条件反复执行的某些步骤组成的逻辑结构,称为循 环

结构,反复执行的步骤称为循环体.

某些循环结构用程序框图可以表示为: 在执行了一次 循环体后,对条件 循环体 进行判断,如果条 件不满足,就继续 否 满足条件? 执行循环体,直到 条件满足时终止循 是 环. 先执行后判断 这种循环结构称为直到型循环结构,你能指出直 到型循环结构的特征吗?

还有一些循环结构用程序框图可以表示为: 在每次执行 循环体前,对条 件进行判断,如 果条件满足,就 执行循环体,否 则终止循环.

循环体 满足条件? 否 是

先判断后执行 这种循环结构称为当型循环结构,你能指出当型 循环结构的特征吗?

直到型循环结构

当型循环结构

循环体 否 满足条件? 否

循环体


满足条件? 是

总结:循环结构中一定包含条件结构,用于确 定何时终止执行循环体.

例6:设计一个计算1+2+3+?+100的值的算法,并 画出程序框图. 第1步,0+1=1. 第2步,1+2=3. 第3步,3+3=6. 第4步,6+4=10. ?? 第100步,4950+100=5050. 显然,这个过程包含重复操作的步骤,可以用循 环结构表示.分析上述计算过程,可以发现每一步都可 以表示为第(i﹣1)步的结果+i=第i步的结果.

我们用一个累加变量S表示每一步的计算结果,即 把S+i的结果仍记为S,从而把第i步表示为S=S+i,其中 S的初始值为0,i依次取1,2,?,100.由于i同时记录 了循环体的次数,所以也称为计数变量.通过重复操作, 上述问题的算法设计如下:

第一步, 令i=1,S=0. 第二步, S =S+i.
第三步, i=i+1. 第四步,判断i>100是否成立.若是,则输出S,结 束算法;否则,返回第二步.

直到型循环结构

开始
i=1 S=0

S=S+i i=i+1 i>100?
是 输出S 否

结束

当型循环结构

开始
i=1 S=0 i=i+1 S=S+i i≤100? 是 否 输出S 结束

例7 某工厂2005年的年生产总值为200万元,技 术革新后预计以后每年的年生产总值都比上一年增 长5%.设计一个程序框图,输出预计年生产总值超过 300万元的最早年份.
算法分析: 第一步, 输入2005年的年生产总值. 第二步, 计算下一年的年生产总值. 第三步, 判断所得的结果是否大于300.若是, 则输出该年的年份;否则,返回第二步.

由于“第二步”是重复操作的步骤,所以可以 用循环结构来实现.按照“确定循环体”“初始化变 量”“设定循环控制条件”的顺序来构造循环结构.
循环结构: (1)确定循环体:设a为某年的年生产总值,t为 年生产总值的年增长量,n为年份,则循环体为 t=0.05a,a=a+t,n=n+1. (2)初始化变量:n=2005,a=200. (3)设定循环控制条件:当“a>300”时终止循环. 所以可通过判断“a>300”是否成立来控制循环.

开始

程序框图:

n=2005

a=200
t=0.05a

a=a+t
n=n+1

a>300?
是 输出n 结束



思考:这是 直到型循环结构 的程序框图,你 能画出包含当型 循环结构的程序 框图吗?

条件结构和循环结构的基本特征:

(1)程序框图中必须有两个起止框,穿插输入、 输出框和处理框,一定有判断框. (2)循环结构中包含条件结构,条件结构中不含 循环结构.
(3)条件结构和循环结构的程序框图各有两种形 式,相互对立统一.

布置作业:

P20习题1.1A组:2,3.

1.1.2 程序框图与算 法的基本逻辑结构(3)

复习 1.算法的基本逻辑结构有哪几种?用程序框图分别 如何表示? 顺序结构 步骤n 步骤n+1

条件结构

满足条件?否

满足条件?否


步骤A

是 步骤B 步骤A

(1)

(2)

循环结构

循环体 循环体 满足条件? 否 是 直到型

是 满足条件?
否 当型

回顾例2:用“二分法”求方程 x 2 ? 2 ? 0( x ? 0) 的近 似解的算法是如何设计的? 第一步,令f(x)=x2-2,给定精确度d. 第二步,确定区间[a,b],满足f(a)·f(b)<0.
a?b 第三步,取区间中点 m ? . 2

第四步,若f(a)·f(m)<0,则含零点的区间为[a,m]; 否则,含零点的区间为[m,b].将新得到的含零点的区 间仍记为[a,b]. 第五步,判断[a,b]的长度是否小于d或f(m)是否等于 0.若是,则m是方程的近似解;否则,返回第三步.

在用自然语言表述一个算法后,可以画出程序 框图,用顺序结构、条件结构和循环结构来表示这个 算法.
根据例2的算法步骤,利用三种基本逻辑结构画 出程序框图.讨论:该算法中哪几个步骤可以用顺序结 构来表示?哪几个步骤可以用条件结构来表示?哪几 个步骤可以用循环结构来表示?

该算法步骤中的“第一步”“第二步”“第三步” 可以用顺序结构来表示,你能做出这个顺序结构的程 序框图吗? 该算法中第四步可以用条件结构来表示,这个步 骤用程序框图如何表示?
该算法步骤中的“第五步”包含一个条件结构, 这个条件结构与“第三步”“第四步”构成一个循环 结构,循环体由“第三步”“第四步”组成,终止循 环的条件“f(m)=0或|a-b|<d”.在第五步中,还包含有 循环结构与“输出m”所组成的顺序结构.这个循环结构 用程序框图如何表示?

f(x)=x2-2 输入精确度d 和初始值a,b
m? a?b 2



f(a)f(m)<0? 是

a=m

b=m

在这个条件结构中,“否”和“是”两个分支的区间 都计为[a,b].

第三步 第四步 |a-b|<d 或 f(m)=0? 是 输出m 否

根据上述分析,你能画出表示整个算法的程序框图吗?

开始

f(x)=x2-2
输入精确度d 和初始值a,b
m = a + b 2

否 a=m

f(a)f(m)<0? 是 b=m 否 |a-b|<d或f(m)=0? 是 输出m
结束

小结 设计一个算法的程序框图的基本思路:

第一步,用自然语言表述算法步骤.
第二步,确定每个算法步骤所包含的逻辑结构, 并用相应的程序框图表示,得到该步骤的程序框图.

第三步,将所有步骤的程序框图用流程线连接起 来,并加上两个终端框,得到表示整个算法的程序框 图.

课堂练习:设计一个用有理指数幂逼 2 5 近无理指数幂 的算法,并估计它的近 似值,画出算法的程序框图.

布置作业: P20习题1.1 A组:1 B组:2.


相关文档

更多相关文档

1.1算法与程序框图练习
第一节 算法与程序框图
1.1.2算法与程序框图
1.1 算法与程序框图 教案[word版教案]
1.1.2 程序框图与算法的基本逻辑结构1
1.1.2_程序框图与算法的基本逻辑结构
1.1.2 程序框图与算法的基本逻辑结构3
1.1.2 程序框图与算法的基本逻辑结构2
1.1.2程序框图与和算法的基本逻辑结构(1)
1.1.2程序框图与算法的基本逻辑结构1
1.1.2程序框图与算法的基本逻辑结构(导学案)
程序框图与算法的基本逻辑结构3
1.1.2程序框图与算法的基本逻辑结构
1.1.2程序框图与算法的基本逻辑结构1
1.1.2-1.1.3 程序框图与算法的基本逻辑结构(一、二)
电脑版