文档介绍：算法与程序设计
一、什么是算法
同学们都很喜欢数学,我们根据数学研究的目的大致可以将数学分为两类:“理论”数学和“应用”数学。
侧重于理论的数学重点研究数学逻辑,其目的通常是通过一些已知条件,推导出公式、定理(逻辑推理)。典型的例子就是古希腊的“平面几何”(欧几里德几何学),可见西方古典数学是侧重于这方面的。
解理论数学问题要靠大量知识的积累和经验,不容易找到固定的方式方法,我们称这些问题是“非结构化”的。
侧重于应用的数学重点在于应用已知的公式、定理,方法等(这些公式、定理,方法由理论研究或其他途径得到),解决具体问题。即对某一具体问题进行分析,应用已知公式、定理,方法写出解题的步骤(算法),再按这些步骤一步一步对问题进行求解。典型的例子是祖冲之的“圆周率求解”,计算二项系数的“杨辉三角形”等,可见中国古典数学是侧重于这方面的。这种应用的问题比较容易找到固定的方式方法,我们称这些问题是“结构化”的。
对我们同学来说,学习公式、定理(特别是几何证明),重点就是学习逻辑推理;而解各种应用题,就是要找出求解某一具体问题的“算法”——解题步骤,然后根据算法,一步步计算,最后得出答案。
例如:求做一个直径 40厘米高 1米的圆柱形水桶,至少需要多少铁皮?
我们知道,桶的表面由侧面和底面组成,因此根据面积计算公式:
桶的表面积= 侧面积+ 底面积
底面积= 半径 2 ×π
侧面积= 高× 底面周长
底面周长= 直径× π
这是一个解决圆柱面加一个底面的“结构化”的方法。
根据上面公式写出计算所需铁皮的一个算法如下:
A= ()2× {A表示底面积}
B = × {B表示底面周长}
C = 1× B {C表示侧面积}
D = A + C {D表示桶的表面积}
上面的算法一共有 4个步骤,按照这四个步骤一步一步计算,桶的表面积就算出来了。
问题 1:这 4个步骤的顺序可以调换吗?例如按照前面的分析步骤,将D = A+ C放在最前面(作为算法第一步)
问题 2:这个问题显然不止一个算法,请你写出另一个算法。
可见,算法步骤的顺序是很重要的,许多后面的计算是以前面的计算为基础的,顺序不能改变。另外,解决某问题的算法不是唯一的,因此有必要寻找较好的算法。
练习:有A、B、C三个杯子,其中A、B装了不同容量的水,请写一个利用C杯交换A、B杯水容量(即使A具有原来B的容量, B具有原来A的容量)的算法,并说明所需要的操作能力。
算法的“设计”与“运行(执行)”
从上面例子还可以看出,解决一个具体问题可以分为两个步骤:
1. 应用已知公式、定理、方法写出解题步骤。这一步称为“算法设计”。这件工作由我们做。
2. 按照算法设计的步骤,一步一步地计算。这一步称为“算法运行”或“算法执行”。这件工作由计算机做。
算法设计练习
1)A、B两地相距100公里,轮船经过10小时从A地行使到B地,返回A地用了12小时。求轮船在静水中的航速。
写出计算船速的算法步骤。
注意,只能写出算式,不许做任何实际计算,实际计算的结果可以用字母表示。例如,只能写A=1+2,表示经过该步骤A表示1+2的和,不能用3代替1+2。同一字母可以多次表示算式,但要注意它们的顺序及每次表示结果可能不同。例如:
A=1+2,B=A+2,A=1+B,A开始表示3,最后表示6,B表示5。
用AB表示两地的距离,用TA、TB表示去、回时间,重写算法,这个新算法有什么特点?
2)写出求解下面二元一次方程组的过程。
3X + 2Y = 1
{
2X + 3Y = 2
注意,不要做任何实际计算,实际计算的结果可以用字母表示。要求字母X、Y最后能表示方程组的解。