逍遥学能 2018-09-12 12:36
第一章 算法初步
1.1 算法与程序图框
1. 算法的含义：在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。比如解方程的算法、函数求值的算法、作图的算法，等等。
2. 例子：
1例1 任意给定一个大于1的整数n，试设计一个程序或步骤对n是否为质数做出判定。
算法分析：根据质数的定义，很容易设计出下面的步骤：
第一步：判断n是否等于2，若n=2，则n是质数；若n>2，则执行第二步。
第二步：依次从2至（n-1）检验是不是n的因数，即整除n的数，若有这样的数，则n不是质数；若没有这样的数，则n是质数。
这是判断一个大于1的整数n是否为质数的最基本算法。
2例2 用二分法设计一个求议程x?2=0的近似根的算法。
算法分析：回顾二分法解方程的过程，并假设所求近似根与准确解的差的绝对值不超过0.005，则不难设计出以下步骤：
2第一步：令f(x)=x?2。因为f(1)<0，f(2)>0，所以设x1=1，x2=2。
第二步：令m=(x1+x2)/2，判断f(m)是否为0，若则，则m为所长；若否，则继续判断f(x1)?f(m)大于0还是小于0。
第三步：若f(x1)?f(m)>0，则令x1=m；否则，令x2=m。
第四步：判断|x1?x2|<0.005是否成立？若是，则x1、x2之间的任意取值均为满足条件的近似根；若否，则返回第二步。
例3 写出解二元一次方程组 的算法
2x+y=1②
解：第一步，②-①×2得5y=3；③
第二步，解③得y=3/5；
第三步，将y=3/5代入①，得x=1/5
学生做一做：对于一般的二元一次方程组来说，上述步骤应该怎样进一步完善？ 老师评一评：本题的算法是由加减消元法求解的，这个算法也适合一般的二元一次方
A1xB1yC10(A1B2B1A20)的解的算法： 程组的解法。下面写出求方程组AxByC0222
第一步：②×A1-①×A2，得(A1B2-A2B1)y+A1C2-A2C1=0；③ 第二步：解③，得yA2C1A2C2； A1B2A2B1
第三步：将yA2C1A2C2B2C1B1C2代入①，得x。 A1B2A2B1A1B2A2B1
此时我们得到了二元一次方程组的求解公式，利用此公司可得到倒2的另一个算法： 第一步：取A1=1，B1=-2，C1=1，A2=2，B2=1，C2=-1；第二步：计算xB2C1B1C2ACA2C2与y21 A1B2A2B1A1B2A2B1
第三步：输出运算结果。
可见利用上述算法，更加有利于上机执行与操作。
基础知识应用题
例4 写出一个求有限整数列中的最大值的算法。
解：算法如下。
S1 先假定序列中的第一个整数为“最大值”。
S2 将序列中的下一个整数值与“最大值”比较，如果它大于此“最大值”，这时你就假定“最大值”是这个整数。
S3 如果序列中还有其他整数，重复S2。
S4 在序列中一直到没有可比的数为止，这时假定的“最大值”就是这个序列中的最大值。
学生做一做 写出对任意3个整数a,b,c求出最大值的算法。
老师评一评 在例2中我们是用自然语言来描述算法的，下面我们用数学语言来描述本题的算法。
S1 max=a
S2 如果b>max, 则max=b.
S3 如果C>max, 则max=c.
S4 max就是a,b,c中的最大值。
综合应用题
例5 写出求1+2+3+4+5+6的一个算法。
分析：可以按逐一相加的程序进行，也可以利用公式1+2+„+n=
根据加法运算律简化运算过程。
解：算法1：
S1：计算1+2得到3；
S2：将第一步中的运算结果3与3相加得到6；
S3：将第二步中的运算结果6与4相加得到10；
S4：将第三步中的运算结果10与5相加得到15；
S5：将第四步中的运算结果15与6相加得到21。
算法2：
S1：取n=6；
S2：计算n(n1
1)进行，也可以2n(n1)； 2
S3：输出运算结果。
算法3：
S1：将原式变形为(1+6)+(2+5)+(3+4)=3×7；
S2：计算3×7；
S3：输出运算结果。
小结：算法1是最原始的方法，最为繁琐，步骤较多，当加数较大时，比如1+2+3+„+10000，再用这种方法是行不通的；算法2与算法3都是比较简单的算法，但比较而言，算法2最为简单，且易于在计算机上执行操作。
学生做一做 求1×3×5×7×9×11的值，写出其算法。
老师评一评 算法1；第一步，先求1×3，得到结果3；
第二步，将第一步所得结果3再乘以5，得到结果15；
第三步，再将15乘以7，得到结果105；
第四步，再将105乘以9，得到945；
第五步，再将945乘以11，得到10395，即是最后结果。
算法2：用P表示被乘数，i表示乘数。
S1 使P=1。
S2 使i=3
S3 使P=P×i
S4 使i=i+2
S5 若i≤11，则返回到S3继续执行；否则算法结束。
1、写出解一元二次方程ax2+bx+c=0(a≠0)的一个算法。
2、写出求1至1000的正数中的3倍数的一个算法（打印结果）
1、解：算法如下
2S1 计算△=b-4ac
S2 如果△〈0，则方程无解；否则x1=
S3 输出计算结果x1，x2或无解信息。
2、解：算法如下：
S1 使i=1
S2 i被3除，得余数r
S3 如果r=0，则打印i，否则不打印
S4 使i=i+1
S5 若i≤1000,则返回到S2继续执行，否则算法结束。
21、写出解不等式x-2x-3<0的一个算法。
2解：第一步：x-2x-3=0的两根是x1=3，x2=-1。
2第二步：由x-2x-3<0可知不等式的解集为x。
2评注：该题的解法具有一般性，下面给出形如ax+bx+c>0的不等式的解的步骤（为方
便，我们设a>0）如下：
第一步：计算△= b4ac； 2
第二步：若△>0，示出方程两根x1,2
x； bb24ac（设x1>x2），则不等式解集为2a
b}； 2a第三步：若△= 0，则不等式解集为{x | x∈R且x
第四步：若△<0，则不等式的解集为R。
2、求过P(a1,b1)、Q(a2,b2)两点的直线斜率有如下的算法：
第一步：取x1= a1，y1= b1，x2= a2，y1= b2；
第二步：若x1= x2；第三步：输出斜率不存在；
第四步：若x1≠x2； 第五步：计算ky2y1； x2x1
第六步：输出结果。
3、写出求过两点M(-2,-1)、N(2,3)的直线与坐标轴围成面积的一个算法。
解：算法：第一步：取x1=-2，y1=-1，x2=2，y2=3； 第二步：计算yy1xx1； y2y1x2x1
第三步：在第二步结果中令x=0得到y的值m，得直线与y轴交点(0,m)；
第四步：在第二步结果中令y=0得到x的值n，得直线与x轴交点(n,0)；
第五步：计算S=1|m||n|； 2
第六步：输出运算结果
3. 程序框图的概念：是一种用规定的图形，指向线及文字说明来准确、直观地表示算法的
图形。
4. 基本概念：
（1）起止框图：
起止框是任何流程图都不可缺少的，它表明程序的开始和结束，所以一个完整的流程图的首末两端必须是起止框。
（2表示数据的输入或结果的输出，它可用在算法中的任何需要输入、输出的位置。图1-1中有三个输入、输出框。第一个出现在开始后的第一步，它的作用是输入未知数的系数a11,a12,a21,a22和常数项b1,b2,通过这一步，就可以把给定的数值写在输入框内，它实际上是把未知数的系数和常数项的值通知给了计算机，另外两个是输出框，它们分别位于由判断分出的两个分支中，它们表示最后给出的运算结果，左边分支中的输出分框负责输出D≠0时未知数x1,x2的值，右边分支中的输出框负责输出D=0时的结果，即输出无法求解信息。
（3）处理框：1-1中出现了两个处理框。第一个处理框的作用是计算D=a1
1a22-a21a12的值，第二个处理框的作用是计算x1=(b1a22-b2a12)/D,x2=(b2a11-b1a21)/D的值。
（4）判断框一般有一个入口和两个出口，有时也有多个出口，它是惟一的具有两个或两个以上出口的符号，在只有两个出口的情形中，通常都分成“是”与“否”（也可用“Y”与“N”）两个分支，在图1-1中，通过判断框对D的值进行判断，若判断框中的式子是D=0，则说明D=0时由标有“是”的分支处理数据；若D≠0，则由标有“否”的分支处理数据。例如，我们要打印x的绝对值，可以设计如下框图。