第一章 算法初步
算法知识结构:
基本概念 表示方法
自然语言 程序框图 基本算法语句 输入、输出语句 赋值语句 条件语句 循环语句
算 法
顺序结构
基本结构
条件结构 循环结构 辗转相除法和更相减损数
应用
秦九韶算法 进位制
算法的定义:
通常指可以用计算机来解决的某一类 问题的程序或步骤,这些程序或步骤必 须是明确和有效的,而且能够在有限步 之内完成。 算法最重要的特征: 1.有序性 2.确定性 3.有限性
算法的基本特点
1、有限性 一个算法应包括有限的操作步骤,能在执 行有穷的操作步骤之后结束。 2、确定性 算法的计算规则及相应的计算步骤必须是唯 一确定的,既不能含糊其词,也不能有二义 性。 3、有序性 算法中的每一个步骤都是有顺序的,前一步 是后一步的前提,只有执行完前一步后,才 能执行后一步,有着很强逻辑性的步骤序列。
二、程序框图
用程序框、流程线及文字说明来表示算 法的图形称为程序框图,它使算法步骤显得 直观、清晰、简明.
○
终端框 (起止框)
输入、 输出框
处理框 (执行框)
判断框
流程线
连接点
程序框图又称流程图,是一种用规定的图形,指向线及 文字说明来准确、直观地表示算法的图形。 程序框 名称 功能
终端框(起 表示一个算法的起始和结束 止框) 输入、输出 表示算法的输入和输出的信 框 息
处理框(执 赋值、计算 行框) 判断框 判断一个条件是否成立,用 “是”、“否”或“Y”、 “N”标明
二、程序框图
?1、顺序结构
步骤n
步骤n+1
满足条件?
否
满足条件?
否
?
2、条件结构
是 步骤A 步骤B
先做后判, 否去循环
循环体
是 先判后做, 步骤 A 是去循环
循环体
?
3、循环结构
否 满足条件?
是
满足条件? 否
是
二、程序框图
?1、顺序结构
开始
输入n=100 s=(n+1)n/2 输出s 结束
设计一算法,求和1+2+3+ … +100, 并画出程序框图。 算法: 第一步:取n=100; 第二步:计算
n ( n ? 1) ; 2
第三步:输出结果。
二、程序框图
?2、条件结构
设计一个算法,求数x的绝对值,并画出程序框图。
算法分析:实数X的绝对值
开始 输入x
N Y
?x x ?? ?? x
( x ? 0) ( x ? 0)
算法: 第一步:输入x; 第二步:如果x≥0; 则输出x;否则输出 - x。
x≥0
输出x
输出-x
结束
二、程序框图
?3、循环结构
直到型循环结构 当型循环结构
A
P
是 否 否
A P
是 是
A P
否 否
A P
是
(A)
(B)
A D
(C)
(D)
直到型循环结构对应的程序框图是 当型循环结构对应的程序框图是
设计一个计算1+2+3+……+100的值的算法,并画出程序框图。 程序框图如下: 算法: 开始 第一步:令i=1,s=0; 第二步:s=s+i i=1 第三步:i=i+1; 循环结构 第四步: 直到i>100时,输出S, s=0 结束算法,否则返回第二步。
s=s+i
i=i+1 i>100? 是 输出s 结束
循环体 条件
是
否
直到型循环结构
设计一个计算1+2+3+……+100的值的算法,并画出程序框图。 算法: 第一步:令i=1,s=0; 第二步:若i<=100成立,则执行第三步;否则,输出s,结束算法; 第三步:s=s+i; 第四步:i=i+1,返回第二步。
程序框图如下:
循环体 条件
否 是
开始 i=1 s=0 i<=100?
当型循环结构
i=i+1 是 s=s+i
否 输出s
结束
三.五种基本算法语句
语句 一般格式 主要功能
可对程序中 的变量赋值
说明
(1)提示内容和它后面 的“;”可以省略 (2)一个语句可以给多个变 量赋值,中间用“,”分隔 (3)无计算功能
1.输入 INPUT “提示内容”;变量 语句
2.输出 PRINT “提示内容”;表达式 语句
(1)表达式可以是变量, 可输出表达式 计算公式,或系统信息 (2)一个语句可以输入多
的值,计算
3.赋值 语句
变量=表达式
个表达式,中间用“,”分隔 (3)有计算功能 (1)“=”的右侧必须是表达 可对程序中 式,左侧必须是变量 的变量赋值, (2)一个语句只能给一个 变量赋
计算
(3)有计算功能
(4)条件语句
IF-THEN-ELSE格式
IF 条件 语句1 ELSE 语句2 END IF
?
THEN
满足条件?
是 语句1
否 语句2
IF-THEN格式
是 满足条件? 否 语句
IF 条件 THEN 语句 END IF
(5)循环语句
①WHILE语句
WHILE 条件 循环体 WEND
循环体
满足条件?
否
是
②UNTIL语句
DO 循环体 LOOP UNTIL 件
循环体
条
满足条件? 是
否
两种循环结构有什么差别?
While(当型)循环
先判断 后执行
先判断指定的条件是否为真, 若条件为真,执行循环条件, 条件为假时退出循环。
A P
不成立 成立
Until(直到型)循环
先执行 后判断
A
P
成立 不成立
先执行循环体,然后再检查条 件是否成立,如果不成立就重 复执行循环体,直到条件成立 退出循环。
编写程序,求和1+2+3+ … +n。 顺序结构:
开始 输入n
输入语句
程序语句: INPUT n
变量=表达式
s=(n+1)n/2
输出s
赋值语句
s=(n+1) * n/2
输出语句
PRINT “S=” ; S
结束
END
练:编写一程序,求实数X的绝对值。
开始 输入X
程序: 条件结构:
N
INPUT X
条件语句:
X≥0 Y 输出X
输出-X
IF X>=0 THEN PRINT X ELSE PRINT -X END IF
结束
END
当型循环语句 练:设计一算法,求和1+2+3+ … +100。 程序框图:
开始
i ?1
程序语句:
i=1 条件
否
循环体
是
S?0
当型循环结构
S=0
WHILE i<=100
i ? i ?1
当型循环语句
S=S+i i=i+1 WEND PRINT S END
WHILE 循环体 WEND
条件
S ? S?i
i ? 100?
否 输出S 结束
是
直到型循环语句
循环体
开始
i ?1
S?0
i=1
直到型循环结构
S=0
DO
条件
是
否
S ? S?i
i ? i ?1
直到型循环语句
S=S+i i=i+1 LOOP UNTIL i>100
DO
i ? 100?
否
是
输出S
循环体
LOOP UNTIL 条件
PRINT S
END
结束
一、辗转相除法(欧几里得算法)
1、定义: 所谓辗转相除法,就是对于给定的两个 数,用较大的数除以较小的数。若余数不为 零,则将余数和较小的数构成新的一对数, 继续上面的除法,直到大数被小数除尽,则 这时较小的数就是原来两个数的最大公约数。
(1)、算法步骤: 第一步:输入两个正整数
m,n(m>n).
第二步:计算m除以n所得的余
数r.
第三步:m=n,n=r.
第四步:若r=0,则m,n的最大
公约数等于m;否则 转到第二步. 第五步:输出最大公约数m.
以求8251和6105的最大公约数的过程为例 步骤: 8251=6105×1+2146
6105=2146×2+1813
2146=1813×1+333 显然37是148和37的最大公约数, 也就是8251和6105的最大公约 数
1813=333×5+148
333=148×2+37
148=37×4+0
更相减损术
1、背景介绍:
(1)、《九章算术》中的更相减损术:
可半者半之,不可半者,副置分母、子之数,以少减多, 更相减损,求其等也,以等数约之。 (2)、现代数学中的更相减损术: 第一步:任意给定两个正整数;判断他们是否都是偶数。 若是,则用2约简;若不是则执行第二步。 第二步:以较大的数减较小的数,接着把所得的差与较小 的数比较,并以大数减小数。继续这个操作,直到所得的 减数和差相等为止,则这个等数就是所求的最大公约数。
2、定义:
所谓更相减损术,就是对于给定的两个 数,用较大的数减去较小的数,然后将差和 较小的数构成新的一对数,再用较大的数减 去较小的数,反复执行此步骤直到差数和较 小的数相等,此时相等的两数便为原来两个 数的最大公约数。
3、方法: 例: 用更相减损术求98与63的最大公约数.
解:由于63不是偶数,把98和63以大数减小数, 并辗转相减 98-63=35 63-35=28 35-28=7 28-7=21 21-7=21 14-7=7 所以,98和63的最大公约数等于7
比较辗转相除法与更相减损术的区别
(1)都是求最大公约数的方法,计算上辗转相除 法以除法为主,更相减损术以减法为主,计算次数
上辗转相除法计算次数相对较少,特别当两个数字
大小区别较大时计算次数的区别较明显。 (2)从结果体现形式来看,辗转相除法体现结果 是以相除余数为0则得到,而更相减损术则以减数与 差相等而得到。
练习:
1、用更相减损术求两个正数84与72的最大公约数. 思路分析:先约简,再求21与18的最大公约数, 然后乘以两次约简的质因数4。 2、求324、243、135这三个数的最大公约数。 思路分析:求三个数的最大公约数可以先求出两个 数的最大公约数,第三个数与前两个数的最大公约 数的最大公约数即为所求。
《数书九章》——秦九韶算法 设 f ( x ) 是一个n 次的多项式
f ( x ) ? a n x ? a n ?1 x ? ? ? a1 x ? a 0 对该多项式按下面的方式进行改写:
n
n ?1
f ( x ) ? a n x n ? a n ?1 x n ?1 ? ? ? a1 x ? a 0
? ( a n x n ?1 ? a n ?1 x n ? 2 ? ? ? a1 ) x ? a 0
? ??
? (( a n x
n?2
? a n ?1 x
n ?3
? ? ? a 2 ) x ? a1 ) x ? a 0
? (? ( a n x ? a n ?1 ) x ? a n ? 2 ) x ? ? ? a1 ) x ? a 0
f ( x ) ? (? ( a n x ? a n ?1 ) x ? a n ? 2 ) x ? ? ? a1 ) x ? a 0
要求多项式的值,应该先算最内层的一次多项式的值,即
v1 ? a n x ? a n ?1
然后,由内到外逐层计算一次多项式的值,即
v 2 ? v1 x ? a n ? 2
??
v3 ? v 2 x ? a n ? 3 v n ? v n ?1 x ? a 0
这种将求一个n次多项式f(x)的值转化成求n个一 次多项式的值的方法,称为秦九韶算法。
秦九韶算法的特点:
通过一次式的反复计算,逐步得出高次多 项式的值,对于一个n次多项式,只需做n次乘 法和n次加法即可。
在秦九韶算法中反复执行的步骤,可用循环结 构来实现。
?v 0 ? a n ? ?循环体: ?v ? v x ? a (k ? 1, 2,? ,n ) k ?1 n ?k ? k
例:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法一:首先将原多项式改写成如下形式 : f(x)=((((2x-5)x-4)x+3)x-6)x+7 然后由内向外逐层计算一次多项式的值,即
v0=2
v1=v0x-5=2×5-5=5 v2=v1x-4=5×5-4=21 v3=v2x+3=21×5+3=108 v4=v3x-6=108×5-6=534 v5=v4x+7=534×5+7=2677
所以,当x=5时,多 项式的值是2677.
例.用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法二:列表 2 x=5 -5 10 5 -4 25 21 3 105
原多项式 的系数
-6 7 540 2670 534 2677
多项式 的值.
2
108
所以,当x=5时,多项式的值是2677.
一、进位制
进位制是人们为了计数和运算方便而约定的记数系统。 进位制是一种记数方式,用有限的数字在不同的位 置表示不同的数值。可使用数字符号的个数称为基 数,基数为n,即可称n进位制,简称n进制。
基数: “满几进一”就是几进制,几进制的基数就是几.
二进制、七进制、八进制、十二进制、六十进制等 二进制只有0和1两个数字,七进制用0~6七个数字
十六进制有0~9十个数字及ABCDEF六个字母.
十进制:
我们最常用最熟悉的就是十进制数,它的数值部分是十个不 同的数字符号0,1,2,3,4,5,6,7,8,9来表示的。
例如133.59,它可用一个多项式来表示:
133.59=1*102+3*101+3*100 +5*10-1+9*10-2
式中 1 处在百位,第一个 3 所在十位,第二个 3 所在 个位,5 和9 分别处在十分位和百分位。十进制数是逢 十进一的。
为了区分不同的进位制,常在数的右下角标明基数, 十进制一般不标注基数.
例如十进制的133.59,写成133.59(10)
七进制的13,写成13(7);二进制的10,写成10(2)
一般地,若k是一个大于1的整数,那么以k
为基数的k进制可以表示为一串数字连写在一起
的形式:
anan?1 ?a1a0(k ) (0 ? an ? k,0 ? an?1,?, a1, a0 ? k ).
二进制与十进制的转换 1、二进制数转化为十进制数 例1:将二进制数110011(2)化成十进制数。
解:根据进位制的定义可知
110011( 2 ) ? 1 ? 2 ? 1 ? 2 ? 0 ? 2 ? 0 ? 2 ? 1 ? 2 ? 1 ? 2
5 4 3 2 1
0
? 51
? 1 ? 32 ? 1 ? 16 ? 1 ? 2 ? 1
所以,110011(2)=51.
把其他进位制的数化为十进制数的公式是什么?
an an ?1 ? a1a0( k ) ? an ? k n ? an ?1 ? k n ?1 ? ? ? a1 ? k 1 ? a0 ? k 0 (10)
十进制转换为二进制
方法:除2取余法,即用2连续去除89或所得的商,然后取余数。 例、 把89化为二进制数 解: 根据“逢二进一”的原则,有 89=2×44+1 89=2×44+1 = 2× (2×22+0)+1 44= 2×22+0 = 2×( 2×( 2×11+0)+0)+1 22= 2×11+0 = 2× (2× (2× (2× 5+1)+0)+0)+1 11= 2× 5+1 = 2× (2× (2× (2× (2× 2+1)+1)+0)+0)+1 5= 2× 2+1 所以89=2×(2×(2×(2×(2 × 2 +1)+1)+0)+0)+1 =2×(2×(2×(2×(22+1)+1)+0)+0)+1 =2×(2×(2×(23+2+1)+0)+0)+1 =2×(2×(24+22+2+0)+0)+1 =2×(25+23+22+0+0)+1 =26+24+23+0+0+20 89=1×26+0×25+1×24+1×23+0×22+0×21+1×20 所以:89=1011001(2)
另解(除2取余法的另一直观写法): 2 2 2 2 2 2 2
注意: 1.最后一步商为0, 2.将上式各步所得的余数从下到上排列,得到: 89=1011001(2) 练习 将下面的十进制数化为二进制数? (1)10 (2)20
89 44 22 11 5 2 1 0
余数 1 0 0 1 1 0 1
例:把89化为五进制数。 解:根据除k取余法 以5作为除数,相应的除法算式为:
5 5 89 17 5 3 0 余数
4 2 3
所以,89=324(5)
除k取余法:十进制数转化为k进制数的方法 用k连续去除该十进制数或所得的商,直 到商为零为止,然后把每次所得的余数倒着 排成一个数,就是相应的k进制数。
考题剖析
例、(2007海南、宁夏)如果执行下面的程序框图, 那么输出的 s =( )。 开始 A 2450 B 2500 C 2550 D 2652 k =1 解:由程序知 s=2×1+2×2+┄+2×50 1 ? 50 ? 2? ? 50 2 =2550 故选(C) s=0
k ≤50?
否
是 s = s +2 k k = k+1
输出s 结束
[点评]本小题考查程序框图中的循环结构,主 要是根据框图,找到规律。
考题剖析
例、(2008海南、宁夏)右面的程序框图,如果输入三个 实数a,b,c,要求输出这三个数中最大的数,那么在空白 的判断框中,应该填入下面四个选项中的( )。 A c>x B x>c
开始
输入a,b,c x =a 是 b > x? 否 是 否 输出x 结束 x =c
C c>b D b>c 解:由程序框图可知第一个判断框 作用是比较x与b的大小,故第二个 判断框的作用应该是比较x与c的 大小。故选(A) [点评]本题考查条件结构的程 序框图,求解时,对字母比较难理解, 可以取一些特殊的数值,代进去,方 便理解。
x=b
(2010安徽理数)如图所示,程序框图(算法流程图) 的输出值
x?
________。
【解析】 程序运行如下:
x ? 1, x ? 2, x ? 4, x ? 5, x ? 6, x ? 8, x ? 9, x ? 10, x ? 12
输出12
解析:因为第一次判断 执行后 i ? 2, s ? 12 , 第二次判断执行后, i ? 3, s ? 12 ? 2 2
.
题目要求计算 12 ? 22 ? 32 ? ? ? ? ? 1002
故,n ? 100
例、如图给出了一个算法流程图,该算法流程 图的功能是( ) A.求a,b,c三数的最大数 B.求a,b,c三数的最小数 C.将a,b,c按从小到大排序 D.将a,b,c按从大到小排序