高一信息科技算法与程序设计复习.doc

信息科技算法与程序设计复习
一、常见的运算
运算符的优先级别：
1. 先算术，后关系，再逻辑，括号改变顺序
2. 算术运算：先乘幂，后取负，再乘除，整除余，末加减
3. 逻辑运算：先非，后与，再或
常用函数：取整函数int（）、求算术平方根函数sqr（）、求绝对值函数abs（）
类别
运算符
运算结果
优先级
算术运算符
+、-、*（乘）、/（除）、^（乘方）、mod（求余）
数值

关系运算符
>、=、<、>=、<=、<>
True（T，1）或False（F，0）

逻辑运算符
not、and、or
True（T，1）或False（F，0）
not>and>or
逻辑运算规则
A
B
A and B
A or B

C
Not C
T
T
T
T

T
F
T
F
F
T

F
T
F
T
F
T

F
F
F
F

习题：
（1）1<5 and 4>3 or not -1=1 T
（2）"a">"b" or 5<6 and 8>=2*4 T
（3）假设变量a的值是1，变量b的值是2，变量c的值是3，计算下列表达式的值。
a^3+b*c 7
c mod b +a 2
int(c/b) >b-a F
a<b and (c-a)/2>0 T
a+b>c or b+c>a and c+a>b T
二、算法的一些概念
1．用计算机解决问题的步骤：分析问题→设计算法→编写程序→运行程序
2. 计算机程序是指示计算机如何去解决问题或完成任务的一组可执行的指令。指令是依次逐条执行的。程序的组成部分：指令部分、数据部分
3. 内存中每个存储单元都有唯一的编号，成为地址。
4. 算法的定义：为解决某一问题设计的确定的有限的步骤。
5．算法的描述：自然语言、流程图描述、伪代码。
6. 算法的特点：有穷性、确定性、可行性、有0个或多个输入（可以没有输入）、有一个或多个输出（至少有一个输出）
7. 算法的流程图表示：

8．常量和变量：
常量：在程序执行过程中事先设置、其值不发生改变的量。
变量：在程序执行过程中，用来存放数据的存储单元。读取变量的值不会改变其存放
的值，但当有新的数据存放进去会覆盖其原来存放的值。
1）每个变量都有一个名字作为标记，不同程序设计语言对变量的命名规则不相同。
2）从变量中读取数据后，变量的值不发生改变。
3）变量的赋值：a = 2   或   a ← 2
4）变量赋值的特点：取之不尽，一冲就丢
5）变量的命名规则：以字母、数字、下划线组成，必须以字母开头。
常用变量的类型：整数型（Integer）、长整型（Long）、单精度实数型（Single）、双精度实数型（Double）、字符串型（String）
9. 计数器：在算法执行过程中，用来记录某种事件发生次数的变量。
1）计数器的初值通常为0，i = 0
2）在循环体中的计数语句，如：i = i + 1
10. 累加器：在算法执行过程中，用来生成并存储数据累加和的变量。
1）累加器的初值通常为0 , s = 0
2）在循环体中的累加语句，如：s = s + a
11. 累乘器：在算法执行过程中，用来生成并存储数据累乘积的变量。
1）累乘器的初值通常为1, s = 1
2）在循环体中的累乘语句，如：s = s * a
10．算法的三种基本结构：顺序结构、分支结构、循环结构

三、算法基本模式
（一）顺序结构（顺序模式）
顺序结构按照自上而下的顺序把每个步骤执行一次。
练习1：输入一个圆的半径，求圆的周长和面积，并输出结果。
代码：
Dim r As Single
r = InputBox("输入半径")
s = 3.14 * r ^ 2
c = 2 * 3.14 * r
Print "周长"; c
Print "面积"; s

练习2：输入一个两位数，交换个位和十位的值，输出结果。
代码：
x = InputBox("请输入")
a = Int(x / 10)
b = x Mod 10
y = 10 * b + a
Print y

练习3：输入两个变量的值，将两个变量中的值互相交换并输出结果。
代码：
Dim a As Single,
Dim b As Single
a = InputBox("第一个数")
b = InputBox("第二个数")
c = a
a = b
b = c
Print a; b

（二）分支结构（选择模式）
分支结构根据条件决定执行步骤1或步骤2中的算法步骤，判断框有一个入口两个出口，分支结构有一个入口，一个出口。

单分支语句格式
①If <条件> Then <步骤1的语句>

②If <条件> Then
<步骤1的语句块>
End If
双分支语句格式
If <条件> Then
<步骤1的语句块>
Else
<步骤2的语句块>
End If

练习1：输入两个数，比较它们的大小，输出较大的数。
代码：
Dim a As Single
Dim b As Single
a = InputBox("请输入")
b = InputBox("请输入")
If a > b Then
Print a
Else
Print b
End If

练习2：输入一个三位数，判断它是否是水仙花数(三位数各个数位上的立方和等于它本身)。
代码：
Dim n As Single
n = InputBox("输入一个三位数")
a = Int(n / 100)
b = Int(n / 10) - a * 10
c = n Mod 10
If a ^ 3 + b ^ 3 + c ^ 3 = n Then
Print "是水仙花数"
Else
Print "不是水仙花数"
End If

练习3：输入一个数，求它的绝对值，并输出结果。
代码：
Dim a As Single
a = InputBox("请输入")
If a < 0 Then
a = -a
End If
Print a

练习4：阶梯电价

第一档
第二档
第三档
方案1
每月用电
<110度
110度-210度
>210度
电价
维持现有电价
超出部分上涨不低于5分钱
超出部分每度涨价不低于0.20元
Dim x As Single
x = InputBox("输入用电")
If x < 110 Then
y = 0.61 * x
ElseIf x <= 210 Then
y = 0.61 * 110 + 0.66 * (x - 110)
Else
y = 0.61 * 110 + 0.66 * 100 + 0.81 * (x - 210)
End If
Print "电费"; y

练习5：购买地铁车票：乘1-4站3元/位，5-9站4元/位，9站以上5元/位，输入站数和人数，输出应付款。
Dim a,b,m as integer
a = inputbox(“请输入站台数：”)
b = inputbox(“请输入人数：”)

If a<=4 then
m=3*b
ElseIf a<=9 then
m=4*b
Else
m=5*b
End If
Print m

练习6：长江遂桥货车通行费收费标准（载重用w
表示,收费用m表示）

Dim w As Single
w = InputBox("输入载重")
If w <= 2 Then
m = 60
End If
If w > 2 And w <= 5 Then
m = 95
End If
If w > 5 And w <= 10 Then
m = 105
End If
If w > 10 And w <= 15 Then
m = 130
End If
If w > 15 Then
m = 145
End If
Print "应付款", m

（三）循环结构（重复结构）
当循环的一般形式
直到循环的一般形式
当遇到需要重复执行的操作时，可以用循环结构，循环结构有一个入口，一个出口。
Do while 条件
循环体语句
Loop

For 循环变量=初值 to 终值 步长
循环体语句
Next 循环变量

Do
循环体语句
Loop while 条件

当循环和直到循环的区别：当循环的循环体可能一次也不执行，直到循环的循环体至少执行一次。
1．输出系列问题
n = 0
Do While n < 5
Print "*"
n = n + 1
Loop
练习1：输出5个*

练习2：输出1，2，3，4，5
方法一：用次数来控制循环

方法二：用输出的数字来控制循环
a = 1
Do While a < =5
Print a
a = a + 1
Loop

练习3：输出21，22，23，24，25的值
方法一：把a当成整个数

方法二：把a当指数

2．求和系列问题
练习1：求1+2+3+4+5的和

练习2：求1+3+5+7+9的和

练习3：求21+22+23+24+25的和

练习4： 求1×2+2×3+3×4+4×5+5×6的和。

练习5：求1+2+3+……+k的和，其中k由键盘输入。

练习6：求1*2*3*4*5的积

练习7：求1+2+3+……加到第几项和超过5？
方法一：用i来计算项数
方法二

练习8：求输入的5个数的平均值（如70，60，80，50，90）
Dim a As Single
s = 0
n = 0
Do While n < 5
a = InputBox("输入数据")
s = s + a
n = n + 1
Loop
Print s / 5
方法一：不用数组
方法二：用数组

练习9：输入若干个数的和，输入-1时结束。(如输入60,50,40,-1)（标志法）

3.循环结构中嵌套分支结构
练习2：求5个数的最大值，并输出最大值的位置。

练习3：求5个数的最小值，并输出最小值的位置。

练习4：求输入的5个数中正数的和

4．直到循环
练习1：输出5个*
n = 0
Do
Print "*"
n = n + 1
Loop while n >= 5

练习2：求1+2+4+7+11的和
s = 0
a = 1
n = 1
Do
s = s + a
a = a + n
n = n + 1
Loop while n > 5
Print s

5．数组：数组是一种特殊的变量，它在内存中的位置是连续的，用于存储一批类型、作用相同的数据。
数组元素的下标可以是常量也可以是变量，也可以是一个表达式，可以从0开始，数组元素可以参与运算，和普通的变量一样。
Dim d(10) As Single
n = 1
Do While n <= 10
a(n) = InputBox("输入")
n = n + 1
Loop
n = 10
Do While n >= 1
Print a(n)
n = n - 1
Loop
练习1：输入10个数，再将其逆序输出。

算法实例复习
一、解析法
1.解析法概念：根据题目中给出的已知条件，找出已知条件与要求的结果之间的关系的数学表达式，并通过计算表达式来实现问题求解的方法。

2.解析法算法实例
（1）输入直角坐标系中两点坐标，计算两点间距离，并输出结果。
Dim x1 As Integer, y1 As Integer,
Dim x2 As Integer, y2 As Integer
x1 = InputBox("x1:")
y1 = InputBox("y1:")
x2 = InputBox("x2:")
y2 = InputBox("y2:")
d = Sqr((x1 - x2) ^ 2 + (y1 - y2) ^ 2)
print d

Print "d="; d

（2）输入圆半径，计算圆面积和周长，并输出结果。
Dim r As Integer
Dim s As Single, c As Single
r = InputBox("请输入半径值:")
s = 3.14 * r * r
c = 2 * 3.14 * r
Print "圆面积为"; s
Print "圆周长为"; c

（3）输入人民币金额，计算兑换后的美元金额并输出。（假定汇率为6.83）

Dim rmb As Integer
Dim usd As Single
rmb = InputBox("请输入人民币金额:")
usd = rmb / 6.83
Print "可以兑换美元金额为"; usd

二、枚举法
1． 枚举算法的概念
列出各种可能的情况并逐一进行检验，根据检验的结果执行相应的操作。
“枚”就是一个一个；“举”就是列举。核心：不遗漏不重复。枚举算法充分利用了计算机“运行速度快、不知疲倦”的优势。
2．枚举算法的结构特点
l 列举——由循环结构实现
l 检验——由分支结构实现
因此，枚举算法的一般结构是：循环结构中嵌套分支结构。
3．枚举算法的设计步骤
l 确定列举的范围——不能随意扩大和缩小范围，否则会造成重复或漏解。
l 明确检验的条件——根据检验的对象来设定条件，以及检验后所执行的相关操作。
l 确定循环控制的方式和列举的方式——借助循环变量的变化来列举。
4.枚举算法实例
通过输入的数据作为检验的对象。
（1）输入10个数，分别统计正数和负数的个数
（2）输入5个成绩，统计其中100分的人数
这两个问题也采用了枚举算法的思想，从结构上看，都是循环结构嵌套分支结构。所检验的对象是通过键盘输入的数据。
Dim x As Single
Dim i, n,m As Integer
i = 1
n = 0
m=0
Do While i <= 10
x = InputBox("请输入一个数：")
If x>0 Then
n = n + 1
ElseIf x<0 Then
m=m+1
End If
i = i + 1
Loop
Print n,m

Dim mark As Single
Dim i, n As Integer
i = 1
n = 0
Do While i <= 5
mark = InputBox("请输入成绩：")
If mark = 100 Then
n = n + 1
End If
i = i + 1
Loop
Print n

通过循环变量的变化来作为检验的对象。
以下6个实例是不需要输入语句的，因为检验的对象正好包含循环变量的变化。

（1）打印出1-1000以内能同时被7和11整除的自然数。
（变量 n 表示这个自然数，列举范围从1—1000）
Dim n As Integer
n = 1
Do While n <= 1000
If n Mod 7 = 0 And n Mod 11 = 0 Then
Print n
End If
n = n + 1
Loop

（2）找水仙花数：一个三位数，各个位置上的数字的立方和等于该数本身
（变量 n 表示这个三位数，列举范围从100—999）
Dim n As Integer
n = 100
Do While n <= 999
a = Int(n / 100)
b = (n - 100 * a) \ 10
c = n - 100 * a - 10 * b
If a ^ 3 + b ^ 3 + c ^ 3 = n Then
Print n
End If
n = n + 1
Loop

（3）鸡兔同笼：20只头，56只脚，问鸡、兔各有几只？
（变量 x 表示鸡的个数，列举范围从1—20）

Dim x As Integer
x = 1
Do While x <= 19
If 2 * x + (20 - x) * 4 = 56 Then
Print "鸡有："; x, "兔有："; 20 - x
End If
x = x + 1
Loop

（4）涂抹单据：一张单据上的5位数号码，千位和百位数字已经模糊不清 “1XX47” ，但这个5位数是57或67的倍数。
（变量 x 表示这个两位数，列举范围从0—99）

Dim n As Intege, x As Integer
x = 0
Do While x <= 99
If (10047 + 100 * x) Mod 57 = 0 Or (10047 + 100 * x) Mod 67 = 0 Then
Print x
End If
x = x + 1
Loop

（5）包装600个变形金刚，小盒每盒12个，大盒每盒15个。盒数都不能为0。输出所有可能的包装方案。
（变量 s 表示小盒子的数量，列举范围从1—50，不包括50）

Dim s As Integer
s = 1
Do While s < 50
If (600 - 12 * s) Mod 15 = 0 Then
Print "小盒："; s, "大盒："; (600 - 12 * s) / 15
End If
s = s + 1
Loop

（6）等式成立：34*8□56 = 43*65□8 使等式成立的数字是什么？
（变量 n表示这个数，列举的范围从0—9）
Dim x As Integer
n = 0
Do While n <= 9
If 34 * (8056 + 100 * n) = 43 * (6508 + 10 * n) Then
Print "使等式成立的数字是："; n
End If
n = n + 1
Loop

三、数组

数组是一种特殊的变量，它在内存中的位置是连续的，利用数组中各个元素下标的连续性的特点，可以采用循环结构对各个元素进行赋值或运算。
【实例】数组的输入与逆序输出
Dim i As Integer
Dim d(1 To 5) As Single
i = 1
Do While i <= 5
d( i )= InputBox("输入一个数：")
i = i + 1
Loop

i = 5
Do While i >= 1
Print d( i )
i = i - 1
Loop

四、查找
（1）顺序查找的算法思想：从数组的第一个元素开始，依次往下查找，若找到，输出该数组元素的下标值并结束；若找遍所有元素没有找到，则输出0,并结束。
（2）对分查找的算法思想：先取数组中间位置上的元素和关键字比较，若不相等则缩小近一半的查找范围，在剩下的元素中再取中间位置上的元素和关键字比较，若不相等则缩小近一半的查找范围，继续查找，以此类推，若找到，输出该数组元素的下标值并结束；若找遍所有元素没有找到，则输出0,并结束。由于对分查找每查找一次，查找范围就缩小一半，因此对分查找的效率要远高于顺序查找，但它的前提是：待查找的数据必须是有序的。
例如：顺序查找6288

例如：对分查找22

五、排序
1、冒泡排序：
l 从最下面一个元素起，自下而上地比较相邻两个元素中的数据，将较小的数值交换到上面一个元素。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。此时，最小的数据已经上升到第一个元素的位置。
l 然后对余下的i-1个元素重复上述过程。
l 由于每一遍加工都是将最小的元素像气泡一样浮至顶端，故称为冒泡排序。
例如：有4个数据：18，15，2，9，按照从小到大的顺序排列，过程如下：
原始数据
18
15
2
9
第一遍
2
18
15
9
第二遍
2
9
18
15
第三遍
2
9
15
18
i = 1
Do While i <= 3
j = 4
Do While j > i
If d(j) < d(j - 1) Then
t = d(j)
d(j) = d(j - 1)
d(j - 1) = t
End If
j = j - 1
Loop
i = i + 1
Loop

分支结构的实现语句
单分支:
if 条件 then
语句组
end if
双分支:
if  条件  then
        语句组A
else
        语句组B
end if
分支嵌套：
if  条件  then
        语句组A
elseIf
        语句组B
else
语句组C
end if

循环结构的实现语句
当型循环:
do while 循环条件
循环体语句组
loop
直到型循环:
do
循环体语句组
loop while 循环条件

计数循环for循环语句代码
for  循环变量=初值  to  终值  step 步长
         循环体语句
next  循环变量