流程图
算法:是按照一定规则解决某一类问题的明确和有限的步骤。 算法的特征: 、 、
流程图:是由一些图框和带箭头的流线组成的,其中图框表示各种操作的类型,图框中的文字和符号表示操作的内容,带箭头的流线表示操作的先后次序 程序框图的基本图形:
算法的三种基本的逻辑结构: 、 、
[例1] 已知三个单元存放了变量x ,y ,z 的值,试给出一个算法,顺次交换x ,y ,z
的值(即y 取x 的值,z 取y 的值,x 取z 的值),并画出流程图.
[例2]已知三个数a ,b ,c . 试给出寻找这三个数中最大的一个算法,画出该算法的流程图.
[例3]画出求1-2+3-4+ +99-100的值的算法流程图.
[例4] 设计一算法,求使1+2+3+ +n >2006成立的最小正整数n 的值.
[例5]任意给定一个大于1的整数n ,试设计一个程序或步骤对n 是否为质数做出判断.
[例6]设计一个求无理数2的近似值的算法.
四、典型习题导练
2
2
2
2
2
2
2
2
2
2
1.已知两个单元分别存放了变量A 和B 的值,则可以实现变量A , B 交换的算法是( ). A .S1 B ←A B .S1 C ←A C .S1 C ←A D .S1 C ←A S2 A ←B S2 B ←C S2 A ←B S2 D ←B
S3 C ←B S3 B ←C 2. 下面流程图中的错误是( )
.
图13-1-11
A .i 没有赋值 B .循环结构有错 C .S 的计算不对 D .判断条件不成立 3. 在表示求直线ax +by +c =0(a ,b 为常数,且a ,b 不同时为0)的斜率的算法 的流程图中,判断框中应填入的内容是
4. 3个正实数,设计一个算法,判断分别以这3个数为三边边长的三角形是否存在,画 出这个算法的流程图.
基本算法语句
1. 输入语句: 输出语句: 2. 赋值语句用符号“=”表示,“x=y”表示将y 的值赋给x ,其中x 是一个变量,y 是一个与x 同类型的变量或表达式. 3. 条件语句
4. 循环语句主要有两种类型:直到型和当型循环语句. [例1] 下列程序的运行结果是.
X=9 Y=9
If X>5 then
Y=Y+7 End IF
IF X>4 then Y=Y+6 End IF
IF X>3 then Y=Y+6 End IF Print Y
[例2] 下面的代码的结果是
i=0
While i
[例3]下面的程序运行时输出的结果是( )
I=1
While I
S=0 I=I+1 S=S+I*I Wend Print S
[例4]已知当-100
y =x -4,设计一算法求y 的值.
[例6]设计一个算法,使得输入一个正整数n ,输出1!+2!+3!+…+n !的值. 写出伪代码. 四 、典型习题导练
1. 下列的循环语句循环的次数为( )
I=1 Do
J=1
While j7
A.7次 B.9次 C.63次 D.16次
2.运行下面的程序后输出的结果是 ,若将程序中的A 语句与B 语句的位置互换,再次执行程序后输出的结果为 .
X=1 Y=0
While X
Y=Y+X ‘A 语句 X=X+1 ‘B 语句 Wend
Print X,Y
3. 下面代码描述的求T 的代数式是 ,求S 的代数式是 .
Input n T=1 S=0 I=1
While I
T=T*I S=S+I I=I+1 Wend
Print T,S
4. 将100名学生的一门功课的成绩依次输入并计算输出平均成绩.
§ 13.3 算法案例 (1)辗转相除法和更相减损术
辗转相除法和更相减损术都是求两个正整数的最大公约数的方法.
辗转相除法就是对于给定的两个正整数,用大数除以小数,若余数不为0,则将小数和余数构成新的一对数,继续上面的除法,反复执行此步骤,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数.
更相减损术就是对于给定的两个正整数,若它们都是偶数,则将它们反复除以2(假设进行了k 次) ,直到它们至少有一个不是偶数后,将大数减小数,然后将差和较小的数构成一对新数,继续上面的减法,反复执行此步骤,直到差和较小的数相等,此时相等的数再乘以原来约简的2即为所求两数的最大公约数. (2)秦九韶算法
秦九韶算法是求多项式值的优秀算法. 设f (x ) =a n x n +a n -1x n -1+改写为如下形式:
k
+a 1x +a 0,
f (x ) =((a n x +a n -1) x +a n -2) x
设v 0=a n , v 1=v 0x +a n -1
+a 1) x +a 0.
v 2=v 1x +a n -2v 3=v 2x +a n -3v n =
v n -1x +a 0
这样求n 次多项式f (x ) 的值就转化为求n 个一次多项式的值. 当多项式中有些项不存在时,可将这几项看做0⨯x ,补齐后再利用秦九韶算法进行计算. 对于一个n 次多项式,只需做n 次乘法和n 次加法运算即可. (3)进位制
K 进制数的基数为k ,k 进制数是由0k -1之间的数字构成的. 将十进制的数转化为k 进制数的方法是除k 取余法.
n
把k 进制数a n a n -1a 1a 0(0
a n a n -1
a 1a 0(k ) =a n k n +a n -1k n -1+
+a 1k +a 0.
[例1]、某市对排污水进行综合治理,征收污水处理费,系统对各厂一个月内排出的污水量m 吨收取的污水处理费y 元,运行程序如下所示:
INPUT m IF m
IF m
y =150+25*(m -100) END IF E ND IF EN D
请写出y 与m 的函数关系,并求排放污水150吨的污水处理费用. [例2](1)求三个数72,120,168的最大公约数.
(2)试写出求正整数m , n (m >n ) 的最小公倍数的算法程序.
[例4].用秦九韶算法求多项式f (x ) =x 5+2x 4+3x 3+4x 2+5x +6在x =2时的值. 例5. 完成下列进制的转化
(1)10202(3)=
____(10)(2)101(10)=__________(8)
下面是把二进制数11111(2)化为十进制数的一个程序框图, 判断框内应填入的条件是 ( )
A . i >5?
B . i ≤4? C . i >4? D . i ≤5?
1.下列给出的赋值语句中正确的是( )
A 4=M B M =-M C B =A =3 D x +y =0
2 当x =2时,下面的程序输出的结果是 ( )
i =1
s =0
I NP U T x
WHILE i
s =s *x +1
i =i +1
WEND PRINT s
E N D
A 3 B 7 C 15 D 3.运行下列程序:
INPUT m , n
DO
r =m MOD n
m =n
n =r
LOOP UNTIL r =0 PRINT m
END
当输入56,42时,输出的结果是
A.56 B.42 C.84 D.14 4( )
a =0
j =1
WHILE j
a =(a +j ) MOD 5 j =j +1
WEND
PRINT a
17
A 50 B 5 25 D 0 二、填空题
15 三个数324, 243, 的最大公约数是_________________
6. 阅读下列程序:
INPUT x
IF x >100AND x
x =100*c +10*b +a PRINT x END IF END
当程序输入x 值为123时, 问运行的结果是_____________.
n n -1
7.(2005年高考北京卷理14)已知n 次多项式P +n (x ) =a 0x +a 1x
+a n -1x +a n ,
如果在一种算法中,计算x 0k (k =2,3,4,…,n )的值需要k -1次乘法,计算P ,那么计算P 3(x 0) 的值共需要9次运算(6次乘法,3次加法)10(x 0) 的值共需要 次运算. 下面给出一种减少运算次数的算法:
(k =0, 1,2,…,n -1).利用该算法,计算P P 0(x ) =a 0, P k +1(x ) =xP k (x ) +a k +13(x 0) 的值共需要6次运算,计算P 10(x 0) 的值共需要. 8.下面程序运行后输出的结果为_______________
x =5
y =-20
IF x
x =y -3
ELSE
y =y +3 END IF
PRINT x -y , y -x
END
三、解答题
9. 用秦九韶算法求多项式f (x ) =3x 5+4x 4-15x 3+76x 2+7x +8在x =-2时的值.
111
10.设计程序,求出满足1+++⋯+>10的最小的正整数n.
23n
11若a =111111(2), b =210
(6)
, c =85
(9)
, 试判断a , b , c 的大小关系,并将c 化为7
进制的数.
12. 某电信公司规定:拨打市内电话时,如果不超过3分钟,则收取话费0.2元;如果通话时间超过3分钟,则超出部分按每分钟0.1元收取通话费,不足一分钟按一分钟计算. 设通话时间为t (分钟),通话费用y (元),如何设计一个程序,计算通话的费用.
流程图
算法:是按照一定规则解决某一类问题的明确和有限的步骤。 算法的特征: 、 、
流程图:是由一些图框和带箭头的流线组成的,其中图框表示各种操作的类型,图框中的文字和符号表示操作的内容,带箭头的流线表示操作的先后次序 程序框图的基本图形:
算法的三种基本的逻辑结构: 、 、
[例1] 已知三个单元存放了变量x ,y ,z 的值,试给出一个算法,顺次交换x ,y ,z
的值(即y 取x 的值,z 取y 的值,x 取z 的值),并画出流程图.
[例2]已知三个数a ,b ,c . 试给出寻找这三个数中最大的一个算法,画出该算法的流程图.
[例3]画出求1-2+3-4+ +99-100的值的算法流程图.
[例4] 设计一算法,求使1+2+3+ +n >2006成立的最小正整数n 的值.
[例5]任意给定一个大于1的整数n ,试设计一个程序或步骤对n 是否为质数做出判断.
[例6]设计一个求无理数2的近似值的算法.
四、典型习题导练
2
2
2
2
2
2
2
2
2
2
1.已知两个单元分别存放了变量A 和B 的值,则可以实现变量A , B 交换的算法是( ). A .S1 B ←A B .S1 C ←A C .S1 C ←A D .S1 C ←A S2 A ←B S2 B ←C S2 A ←B S2 D ←B
S3 C ←B S3 B ←C 2. 下面流程图中的错误是( )
.
图13-1-11
A .i 没有赋值 B .循环结构有错 C .S 的计算不对 D .判断条件不成立 3. 在表示求直线ax +by +c =0(a ,b 为常数,且a ,b 不同时为0)的斜率的算法 的流程图中,判断框中应填入的内容是
4. 3个正实数,设计一个算法,判断分别以这3个数为三边边长的三角形是否存在,画 出这个算法的流程图.
基本算法语句
1. 输入语句: 输出语句: 2. 赋值语句用符号“=”表示,“x=y”表示将y 的值赋给x ,其中x 是一个变量,y 是一个与x 同类型的变量或表达式. 3. 条件语句
4. 循环语句主要有两种类型:直到型和当型循环语句. [例1] 下列程序的运行结果是.
X=9 Y=9
If X>5 then
Y=Y+7 End IF
IF X>4 then Y=Y+6 End IF
IF X>3 then Y=Y+6 End IF Print Y
[例2] 下面的代码的结果是
i=0
While i
[例3]下面的程序运行时输出的结果是( )
I=1
While I
S=0 I=I+1 S=S+I*I Wend Print S
[例4]已知当-100
y =x -4,设计一算法求y 的值.
[例6]设计一个算法,使得输入一个正整数n ,输出1!+2!+3!+…+n !的值. 写出伪代码. 四 、典型习题导练
1. 下列的循环语句循环的次数为( )
I=1 Do
J=1
While j7
A.7次 B.9次 C.63次 D.16次
2.运行下面的程序后输出的结果是 ,若将程序中的A 语句与B 语句的位置互换,再次执行程序后输出的结果为 .
X=1 Y=0
While X
Y=Y+X ‘A 语句 X=X+1 ‘B 语句 Wend
Print X,Y
3. 下面代码描述的求T 的代数式是 ,求S 的代数式是 .
Input n T=1 S=0 I=1
While I
T=T*I S=S+I I=I+1 Wend
Print T,S
4. 将100名学生的一门功课的成绩依次输入并计算输出平均成绩.
§ 13.3 算法案例 (1)辗转相除法和更相减损术
辗转相除法和更相减损术都是求两个正整数的最大公约数的方法.
辗转相除法就是对于给定的两个正整数,用大数除以小数,若余数不为0,则将小数和余数构成新的一对数,继续上面的除法,反复执行此步骤,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数.
更相减损术就是对于给定的两个正整数,若它们都是偶数,则将它们反复除以2(假设进行了k 次) ,直到它们至少有一个不是偶数后,将大数减小数,然后将差和较小的数构成一对新数,继续上面的减法,反复执行此步骤,直到差和较小的数相等,此时相等的数再乘以原来约简的2即为所求两数的最大公约数. (2)秦九韶算法
秦九韶算法是求多项式值的优秀算法. 设f (x ) =a n x n +a n -1x n -1+改写为如下形式:
k
+a 1x +a 0,
f (x ) =((a n x +a n -1) x +a n -2) x
设v 0=a n , v 1=v 0x +a n -1
+a 1) x +a 0.
v 2=v 1x +a n -2v 3=v 2x +a n -3v n =
v n -1x +a 0
这样求n 次多项式f (x ) 的值就转化为求n 个一次多项式的值. 当多项式中有些项不存在时,可将这几项看做0⨯x ,补齐后再利用秦九韶算法进行计算. 对于一个n 次多项式,只需做n 次乘法和n 次加法运算即可. (3)进位制
K 进制数的基数为k ,k 进制数是由0k -1之间的数字构成的. 将十进制的数转化为k 进制数的方法是除k 取余法.
n
把k 进制数a n a n -1a 1a 0(0
a n a n -1
a 1a 0(k ) =a n k n +a n -1k n -1+
+a 1k +a 0.
[例1]、某市对排污水进行综合治理,征收污水处理费,系统对各厂一个月内排出的污水量m 吨收取的污水处理费y 元,运行程序如下所示:
INPUT m IF m
IF m
y =150+25*(m -100) END IF E ND IF EN D
请写出y 与m 的函数关系,并求排放污水150吨的污水处理费用. [例2](1)求三个数72,120,168的最大公约数.
(2)试写出求正整数m , n (m >n ) 的最小公倍数的算法程序.
[例4].用秦九韶算法求多项式f (x ) =x 5+2x 4+3x 3+4x 2+5x +6在x =2时的值. 例5. 完成下列进制的转化
(1)10202(3)=
____(10)(2)101(10)=__________(8)
下面是把二进制数11111(2)化为十进制数的一个程序框图, 判断框内应填入的条件是 ( )
A . i >5?
B . i ≤4? C . i >4? D . i ≤5?
1.下列给出的赋值语句中正确的是( )
A 4=M B M =-M C B =A =3 D x +y =0
2 当x =2时,下面的程序输出的结果是 ( )
i =1
s =0
I NP U T x
WHILE i
s =s *x +1
i =i +1
WEND PRINT s
E N D
A 3 B 7 C 15 D 3.运行下列程序:
INPUT m , n
DO
r =m MOD n
m =n
n =r
LOOP UNTIL r =0 PRINT m
END
当输入56,42时,输出的结果是
A.56 B.42 C.84 D.14 4( )
a =0
j =1
WHILE j
a =(a +j ) MOD 5 j =j +1
WEND
PRINT a
17
A 50 B 5 25 D 0 二、填空题
15 三个数324, 243, 的最大公约数是_________________
6. 阅读下列程序:
INPUT x
IF x >100AND x
x =100*c +10*b +a PRINT x END IF END
当程序输入x 值为123时, 问运行的结果是_____________.
n n -1
7.(2005年高考北京卷理14)已知n 次多项式P +n (x ) =a 0x +a 1x
+a n -1x +a n ,
如果在一种算法中,计算x 0k (k =2,3,4,…,n )的值需要k -1次乘法,计算P ,那么计算P 3(x 0) 的值共需要9次运算(6次乘法,3次加法)10(x 0) 的值共需要 次运算. 下面给出一种减少运算次数的算法:
(k =0, 1,2,…,n -1).利用该算法,计算P P 0(x ) =a 0, P k +1(x ) =xP k (x ) +a k +13(x 0) 的值共需要6次运算,计算P 10(x 0) 的值共需要. 8.下面程序运行后输出的结果为_______________
x =5
y =-20
IF x
x =y -3
ELSE
y =y +3 END IF
PRINT x -y , y -x
END
三、解答题
9. 用秦九韶算法求多项式f (x ) =3x 5+4x 4-15x 3+76x 2+7x +8在x =-2时的值.
111
10.设计程序,求出满足1+++⋯+>10的最小的正整数n.
23n
11若a =111111(2), b =210
(6)
, c =85
(9)
, 试判断a , b , c 的大小关系,并将c 化为7
进制的数.
12. 某电信公司规定:拨打市内电话时,如果不超过3分钟,则收取话费0.2元;如果通话时间超过3分钟,则超出部分按每分钟0.1元收取通话费,不足一分钟按一分钟计算. 设通话时间为t (分钟),通话费用y (元),如何设计一个程序,计算通话的费用.