1.1 算法与程序框图
图片预览
文档简介
(共44张PPT)
1.1.1 算法的概念
1.1 算法与程序框图
第一章 算法初步
一般地, 按照一定规则解决某一类问题的明确和有限的步骤称为算法。
从更广义的角度来看,并不是只有“计算”的问题才有算法,日常生活中处处都有.如乐谱是乐队演奏的算法,菜谱是做菜肴的算法,珠算口诀是使用算盘的算法.
它是解决某一类问题的程序或步骤.
问1:在初中，对于解二元一次方程组你学过哪些方法？
加减消元法和代入消元法
问2:用加减消元法解二元一次方程组
的具体步骤是什么？
①+②×2，得 5x=1 . ③
解③，得 .
②-①×2，得 5y＝3 . ④
解④，得 .
第一步：
第二步：
第三步：
第四步：
第五步：
得到方程组的解为 .
问3:参照上述思路,一般地,解方程组
的基本步骤是什么？
②
①
第一步：
解③ ，得
②× - ①× ，得
解④ ，得
得到方程组的解为
①× - ②× ，得
③
第二步：
④
第三步：
第四步：
第五步：
根据上述分析，用加减消元法解二元一次方程组，可以分为五个步骤进行，这五个步骤就构成了解二元一次方程组的一个“算法”.我们再根据这一算法编制计算机程序，就可以让计算机来解二元一次方程组.
在数学中，现代意义上的算法通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确的和有效的，而且能够在有限步之内完成。
1.算法定义：
2.算法的基本特征:
确定性:算法中的每一步都应该是确定的,并且能有效地执行且得到确定的结果.
有限性:一个算法的步骤序列是有限的它应在有限步操作之后停止，而不能是无限的．
顺序性与正确性:算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且每一步都准确无误，才能解决问题．
不唯一性:求解某一个问题的算法不一定是唯一的，对于一个问题可以有不同的算法．
普遍性:很多具体的问题，都可以设计合理的算法去解决．
3.设计算法的要求:
(1)写出的算法,必须能解决一类问题(例如解任意一个二元一次方程组),并且能重复使用;
(2)要使算法尽量简单、步骤尽量少；
(3)要保证算法正确，且计算机能够执行.
⑴用日常语言和数学语言或借助于形式语言（算法语言）；
⑵程序框图（简称框图）；
⑶程序语言。
4.算法的表述形式:
第一步：用2除7，得到余数1,所以2不能整除7.
第二步：用3除7，得到余数1,所以3不能整除7.
例1:设计一个算法，判断7是否为质数？
第三步：用4除7，得到余数3,所以4不能整除7.
第四步：用5除7，得到余数2,所以5不能整除7.
第五步：用6除7，得到余数1,所以6不能整除7.
因此，7是质数.
例2:设计一个算法，判断35是否为质数？
例2:设计一个算法，判断35是否为质数？
第一步：用2除35，得到余数1,所以2不能整除35.
第二步：用3除35，得到余数2,所以3不能整除35.
第三步：用4除35，得到余数3,所以4不能整除35.
第四步：用5除35，得到余数0,所以5能整除35.
因此，35不是质数.
第一步：给定一个大于2的整数n；
第二步：令i=2；
第三步：用i除n，得到余数r；
第五步：判断“i>(n-1)”或“r=0”是否成立.
第四步：将i的值增加1，仍用i表示；
若是，再判断“r=0”是否成立，否则，返回第三步；
若“r=0”成立，则n不是质数，否则，n是质数.
写出判断整数n(n>2)是否为质数的算法(二)
例3.用二分法设计一个求方程 x2-2=0（x>0） 的近似根的算法.(精确度为0.005)
第一步：
第二步：
第三步：
第四步：
第五步：
令 ，
给定精确度d.
确定区间[a，b]，
满足f(a)·f(b)<0.
取区间中点
若f(a)·f(m)<0,
则含零点的区间为
否则，含零点的区间为
将新得到的含零点的区间仍记为[a,b];
判断|a-b|若是，则m是方程的近似解；
否则，返回
[a,m],
[m，b].
第三步.
a b |a-b|
1 2 1
1 1.5 0.5
1.25 1.5 0.25
1.375 1.5 0.125
1.375 1.437 5 0.062 5
1.406 25 1.437 5 0.031 25
1.406 25 1.421 875 0.015 625
1.414 625 1.421 875 0.007 812 5
1.414 062 5 1.417 968 75 0.003 906 25
对于方程 ,给定d=0.005.
此步骤也是求 的近似值的一个算法.
教材5页练习1: 任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.
第一步：
第二步：
第三步：
输入任意一个正实数r；
计算S=πr2;
输出圆的面积S.
教材5页练习2:任意给定一个大于1的正整数n，设计一个算法求出n的所有因数.
第一步：
第二步：
第三步：
依次用2 ～（n – 1）除 n ，
检查余数是否为0；
若是，则是 n 的因数；
若不是，则不是 n 的因数；
在 n 的因数中加入 1 和 n；
输出n的所有因数.
练习3:写出过P(a1,b1)、Q(a2,b2)两点直线斜率的算法：
第一步：
第二步：
第三步：
取x1=a1，y1=b1，x2=a2，y2=b2；
若x1=x2,
输出斜率不存在；
若x1≠x2,
计算
第四步：
输出结果。
写出判断整数n(n>2)是否为质数的算法
第一步：
给定一个大于2的整数n；
令i=2；
第二步：
第三步：
用i除n，得到余数r；
第四步：
判断“r=0”是否成立.
若是，则
否则，将i的值增加1，仍用i表示；
第五步：
判断“i>(n-1)”是否成立，
若是，则
否则，返回
n不是质数，结束算法；
n是质数，结束算法；
第三步.
1.1.2 程序框图与算法 的基本逻辑结构
第二课时
复习回顾
1.用程序框、流程线及文字说明来表示算法的图形称为程序框图，它使算法步骤显得直观、清晰、简明.其中程序框有哪几种基本图形？它们表示的功能分别如何？
终端框 （起止框）
输入、输出框
处理框 （执行框）
判断框
流程线
2.顺序结构是任何一个算法都离不开的基本逻辑结构，在一些算法中，有些步骤只有在一定条件下才会被执行，有些步骤在一定条件下会被重复执行，这需要我们对算法的逻辑结构作进一步探究.
1.1.2-2 条件结构与循环结构
在某些问题的算法中，有些步骤只有在一定条件下才会被执行，算法的流程因条件是否成立而变化.在算法的程序框图中，由若干个在一定条件下才会被执行的步骤组成的逻辑结构，称为条件结构，用程序框图可以表示为下面两种形式：
一、条件结构：
满足条件？
步骤A
是
否
步骤B
满足条件？
步骤A
是
否
你如何理解这两种程序框图的共性和个性？
判断“以任意给定的3个正实数为三条边边长的三角形是否存在”的算法步骤如何设计？
第二步，判断a+b>c，b+c>a，c+a>b是否同时成立.若是，则存在这样的三角形；否则，不存在这样的三角形.
第一步，输入三个正实数a，b，c.
你能画出这个算法的程序框图吗？
开始
输入a, b, c
a+b>c,b+c>a,
c+a>b是否同时成立？
是
否
存在这样的
三角形
不存在这样的三角形
结束
在算法的程序框图中，由按照一定的条件反复执行的某些步骤组成的逻辑结构，称为循环结构，反复执行的步骤称为循环体，那么循环结构中一定包含条件结构吗？
二、循环结构：
某些循环结构用程序框图可以表示为：
循环体
满足条件？
是
否
这种循环结构称为直到型循环结构
在执行了一次循环体后，对条件进行判断，如果条件不满足，就继续执行循环体，直到条件满足时终止循环.
还有一些循环结构用程序框图可以表示为：
循环体
满足条件？
是
否
这种循环结构称为当型循环结构
在每次执行循环体前，对条件进行判断，如果条件满足，就执行循环体，否则终止循环.
计算1+2+3+…+100的值可按如下过程进行：
第1步，0+1=1.
第2步，1+2=3.
第3步，3+3=6.
第4步，6+4=10.
……
第100步，4950+100=5050.
1.确定循环体:
S=S+i,
i=i+1
2.初始化变量:
S=0,
i=1;
3.控制条件:
i>100
直到型:
当 型:
i≤100
第三步，判断“i>100”是否成立.
第一步，令i=1，S=0.
第二步，S=S+i,i=i+1.
若是，则输出S；
否则，返回第二步.
计算1+2+3+…+100的算法(直到型循环)
直到型循环结构
程序框图
开始
i=1
i>100？
是
输出S
结束
S=0
i=i+1
S=S+i
否
注意框中的
前后顺序
当型循环结构
是
i≤100？
开始
输出S
结束
i=i+1
S=S+i
否
i=1, S=0
开始
i=1
i>100？
是
输出S
结束
S=0
i=i+1
S=S+i
否
直到型循环结构
例1 设计一个求解一元二次方程ax2+bx+c=0的算法，并画出程序框图表示.
第一步，输入三个系数a，b，c.
第二步，计算△=b2-4ac.
第四步，判断△=0是否成立.
第三步，判断△≥0是否成立.
若是，则计算 ；
否则，输出“方程没有实数根”
若是，则输出p，
否则，计算x1=p+q，x2=p-q，并输出x1，x2.
程序框图：
开始
输入a，b，c
△= b2-4ac
△≥0？
△=0？
否
x1=p+q
输出x1, x2
否
是
输出p
是
输出“方程没有实数根”
结束
x2=p-q
例2 某工厂2005年的年生产总值为200万元，技术革新后预计以后每年的年生产总值都比上一年增长5%.设计一个程序框图，输出预计年生产总值超过300万元的最早年份.
（3）控制条件：
（1）循环体：
（2）初始值：n=
t为年生产总值的年增长量，
n为年份，
则t=0.05a，
设a为某年的年生产总值，
a=a+t，
n=n+1.
2005，a=
200.
a>300 .
第三步，
第一步，
第二步，
（3）控制条件：
（1）循环体：
（2）初始值：n=
t为年生产总值的年增长量，
n为年份，
则t=0.05a，
设a为某年的年生产总值，
a=a+t，
n=n+1.
2005，a=
200.
a>300 .
n=2005，a=200;
计算年增量: t=0.05a，
判断“a>300”是否成立.
计算年产量：a=a+t，
若是，则
第四步，
输出n；否则，
返回第二步.
第五步，
计算年份：n=n+1，
开始
n=2005
a=200
t=0.05a
a=a+t
n=n+1
a>300？
结束
输出n
是
否
程序框图：
(直到型循环)
开始
n=2005，a=200
t=0.05a
a=a+t
n=n+1
a≤300？
结束
输出n
是
否
(当型循环)
开始
n=2005
a=200
t=0.05a
a=a+t
n=n+1
a>300？
结束
输出n
是
否
(直到型循环)
（3）条件结构和循环结构的程序框图各有两种形式，相互对立统一.
条件结构和循环结构的基本特征：
小结
（1）程序框图中必须有两个起止框，穿插输入、输出框和处理框，一定有判断框.
（2）循环结构中包含条件结构，条件结构中不含循环结构.
1.1.1 算法的概念
1.1 算法与程序框图
第一章 算法初步
一般地, 按照一定规则解决某一类问题的明确和有限的步骤称为算法。
从更广义的角度来看,并不是只有“计算”的问题才有算法,日常生活中处处都有.如乐谱是乐队演奏的算法,菜谱是做菜肴的算法,珠算口诀是使用算盘的算法.
它是解决某一类问题的程序或步骤.
问1:在初中，对于解二元一次方程组你学过哪些方法？
加减消元法和代入消元法
问2:用加减消元法解二元一次方程组
的具体步骤是什么？
①+②×2，得 5x=1 . ③
解③，得 .
②-①×2，得 5y＝3 . ④
解④，得 .
第一步：
第二步：
第三步：
第四步：
第五步：
得到方程组的解为 .
问3:参照上述思路,一般地,解方程组
的基本步骤是什么？
②
①
第一步：
解③ ，得
②× - ①× ，得
解④ ，得
得到方程组的解为
①× - ②× ，得
③
第二步：
④
第三步：
第四步：
第五步：
根据上述分析，用加减消元法解二元一次方程组，可以分为五个步骤进行，这五个步骤就构成了解二元一次方程组的一个“算法”.我们再根据这一算法编制计算机程序，就可以让计算机来解二元一次方程组.
在数学中，现代意义上的算法通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确的和有效的，而且能够在有限步之内完成。
1.算法定义：
2.算法的基本特征:
确定性:算法中的每一步都应该是确定的,并且能有效地执行且得到确定的结果.
有限性:一个算法的步骤序列是有限的它应在有限步操作之后停止，而不能是无限的．
顺序性与正确性:算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且每一步都准确无误，才能解决问题．
不唯一性:求解某一个问题的算法不一定是唯一的，对于一个问题可以有不同的算法．
普遍性:很多具体的问题，都可以设计合理的算法去解决．
3.设计算法的要求:
(1)写出的算法,必须能解决一类问题(例如解任意一个二元一次方程组),并且能重复使用;
(2)要使算法尽量简单、步骤尽量少；
(3)要保证算法正确，且计算机能够执行.
⑴用日常语言和数学语言或借助于形式语言（算法语言）；
⑵程序框图（简称框图）；
⑶程序语言。
4.算法的表述形式:
第一步：用2除7，得到余数1,所以2不能整除7.
第二步：用3除7，得到余数1,所以3不能整除7.
例1:设计一个算法，判断7是否为质数？
第三步：用4除7，得到余数3,所以4不能整除7.
第四步：用5除7，得到余数2,所以5不能整除7.
第五步：用6除7，得到余数1,所以6不能整除7.
因此，7是质数.
例2:设计一个算法，判断35是否为质数？
例2:设计一个算法，判断35是否为质数？
第一步：用2除35，得到余数1,所以2不能整除35.
第二步：用3除35，得到余数2,所以3不能整除35.
第三步：用4除35，得到余数3,所以4不能整除35.
第四步：用5除35，得到余数0,所以5能整除35.
因此，35不是质数.
第一步：给定一个大于2的整数n；
第二步：令i=2；
第三步：用i除n，得到余数r；
第五步：判断“i>(n-1)”或“r=0”是否成立.
第四步：将i的值增加1，仍用i表示；
若是，再判断“r=0”是否成立，否则，返回第三步；
若“r=0”成立，则n不是质数，否则，n是质数.
写出判断整数n(n>2)是否为质数的算法(二)
例3.用二分法设计一个求方程 x2-2=0（x>0） 的近似根的算法.(精确度为0.005)
第一步：
第二步：
第三步：
第四步：
第五步：
令 ，
给定精确度d.
确定区间[a，b]，
满足f(a)·f(b)<0.
取区间中点
若f(a)·f(m)<0,
则含零点的区间为
否则，含零点的区间为
将新得到的含零点的区间仍记为[a,b];
判断|a-b|
否则，返回
[a,m],
[m，b].
第三步.
a b |a-b|
1 2 1
1 1.5 0.5
1.25 1.5 0.25
1.375 1.5 0.125
1.375 1.437 5 0.062 5
1.406 25 1.437 5 0.031 25
1.406 25 1.421 875 0.015 625
1.414 625 1.421 875 0.007 812 5
1.414 062 5 1.417 968 75 0.003 906 25
对于方程 ,给定d=0.005.
此步骤也是求 的近似值的一个算法.
教材5页练习1: 任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.
第一步：
第二步：
第三步：
输入任意一个正实数r；
计算S=πr2;
输出圆的面积S.
教材5页练习2:任意给定一个大于1的正整数n，设计一个算法求出n的所有因数.
第一步：
第二步：
第三步：
依次用2 ～（n – 1）除 n ，
检查余数是否为0；
若是，则是 n 的因数；
若不是，则不是 n 的因数；
在 n 的因数中加入 1 和 n；
输出n的所有因数.
练习3:写出过P(a1,b1)、Q(a2,b2)两点直线斜率的算法：
第一步：
第二步：
第三步：
取x1=a1，y1=b1，x2=a2，y2=b2；
若x1=x2,
输出斜率不存在；
若x1≠x2,
计算
第四步：
输出结果。
写出判断整数n(n>2)是否为质数的算法
第一步：
给定一个大于2的整数n；
令i=2；
第二步：
第三步：
用i除n，得到余数r；
第四步：
判断“r=0”是否成立.
若是，则
否则，将i的值增加1，仍用i表示；
第五步：
判断“i>(n-1)”是否成立，
若是，则
否则，返回
n不是质数，结束算法；
n是质数，结束算法；
第三步.
1.1.2 程序框图与算法 的基本逻辑结构
第二课时
复习回顾
1.用程序框、流程线及文字说明来表示算法的图形称为程序框图，它使算法步骤显得直观、清晰、简明.其中程序框有哪几种基本图形？它们表示的功能分别如何？
终端框 （起止框）
输入、输出框
处理框 （执行框）
判断框
流程线
2.顺序结构是任何一个算法都离不开的基本逻辑结构，在一些算法中，有些步骤只有在一定条件下才会被执行，有些步骤在一定条件下会被重复执行，这需要我们对算法的逻辑结构作进一步探究.
1.1.2-2 条件结构与循环结构
在某些问题的算法中，有些步骤只有在一定条件下才会被执行，算法的流程因条件是否成立而变化.在算法的程序框图中，由若干个在一定条件下才会被执行的步骤组成的逻辑结构，称为条件结构，用程序框图可以表示为下面两种形式：
一、条件结构：
满足条件？
步骤A
是
否
步骤B
满足条件？
步骤A
是
否
你如何理解这两种程序框图的共性和个性？
判断“以任意给定的3个正实数为三条边边长的三角形是否存在”的算法步骤如何设计？
第二步，判断a+b>c，b+c>a，c+a>b是否同时成立.若是，则存在这样的三角形；否则，不存在这样的三角形.
第一步，输入三个正实数a，b，c.
你能画出这个算法的程序框图吗？
开始
输入a, b, c
a+b>c,b+c>a,
c+a>b是否同时成立？
是
否
存在这样的
三角形
不存在这样的三角形
结束
在算法的程序框图中，由按照一定的条件反复执行的某些步骤组成的逻辑结构，称为循环结构，反复执行的步骤称为循环体，那么循环结构中一定包含条件结构吗？
二、循环结构：
某些循环结构用程序框图可以表示为：
循环体
满足条件？
是
否
这种循环结构称为直到型循环结构
在执行了一次循环体后，对条件进行判断，如果条件不满足，就继续执行循环体，直到条件满足时终止循环.
还有一些循环结构用程序框图可以表示为：
循环体
满足条件？
是
否
这种循环结构称为当型循环结构
在每次执行循环体前，对条件进行判断，如果条件满足，就执行循环体，否则终止循环.
计算1+2+3+…+100的值可按如下过程进行：
第1步，0+1=1.
第2步，1+2=3.
第3步，3+3=6.
第4步，6+4=10.
……
第100步，4950+100=5050.
1.确定循环体:
S=S+i,
i=i+1
2.初始化变量:
S=0,
i=1;
3.控制条件:
i>100
直到型:
当 型:
i≤100
第三步，判断“i>100”是否成立.
第一步，令i=1，S=0.
第二步，S=S+i,i=i+1.
若是，则输出S；
否则，返回第二步.
计算1+2+3+…+100的算法(直到型循环)
直到型循环结构
程序框图
开始
i=1
i>100？
是
输出S
结束
S=0
i=i+1
S=S+i
否
注意框中的
前后顺序
当型循环结构
是
i≤100？
开始
输出S
结束
i=i+1
S=S+i
否
i=1, S=0
开始
i=1
i>100？
是
输出S
结束
S=0
i=i+1
S=S+i
否
直到型循环结构
例1 设计一个求解一元二次方程ax2+bx+c=0的算法，并画出程序框图表示.
第一步，输入三个系数a，b，c.
第二步，计算△=b2-4ac.
第四步，判断△=0是否成立.
第三步，判断△≥0是否成立.
若是，则计算 ；
否则，输出“方程没有实数根”
若是，则输出p，
否则，计算x1=p+q，x2=p-q，并输出x1，x2.
程序框图：
开始
输入a，b，c
△= b2-4ac
△≥0？
△=0？
否
x1=p+q
输出x1, x2
否
是
输出p
是
输出“方程没有实数根”
结束
x2=p-q
例2 某工厂2005年的年生产总值为200万元，技术革新后预计以后每年的年生产总值都比上一年增长5%.设计一个程序框图，输出预计年生产总值超过300万元的最早年份.
（3）控制条件：
（1）循环体：
（2）初始值：n=
t为年生产总值的年增长量，
n为年份，
则t=0.05a，
设a为某年的年生产总值，
a=a+t，
n=n+1.
2005，a=
200.
a>300 .
第三步，
第一步，
第二步，
（3）控制条件：
（1）循环体：
（2）初始值：n=
t为年生产总值的年增长量，
n为年份，
则t=0.05a，
设a为某年的年生产总值，
a=a+t，
n=n+1.
2005，a=
200.
a>300 .
n=2005，a=200;
计算年增量: t=0.05a，
判断“a>300”是否成立.
计算年产量：a=a+t，
若是，则
第四步，
输出n；否则，
返回第二步.
第五步，
计算年份：n=n+1，
开始
n=2005
a=200
t=0.05a
a=a+t
n=n+1
a>300？
结束
输出n
是
否
程序框图：
(直到型循环)
开始
n=2005，a=200
t=0.05a
a=a+t
n=n+1
a≤300？
结束
输出n
是
否
(当型循环)
开始
n=2005
a=200
t=0.05a
a=a+t
n=n+1
a>300？
结束
输出n
是
否
(直到型循环)
（3）条件结构和循环结构的程序框图各有两种形式，相互对立统一.
条件结构和循环结构的基本特征：
小结
（1）程序框图中必须有两个起止框，穿插输入、输出框和处理框，一定有判断框.
（2）循环结构中包含条件结构，条件结构中不含循环结构.