1.1.1 算法的概念

时间:2019-9-9 19:05:03   作者:数学名师王老师
1.通过对解决具体问题的过程与步骤的分析,体会算法的思想,了解算法的含义.
2.根据算法的要求和特征,能够判断算法的对与错,优与劣,并能写出解决简单问题的算法步骤.
知识点
  • 1.算法的概念

    算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤,或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤或序列能够解决一类问题.

    知识拓展1.算法一般是机械的,有时要进行大量重复的计算,只要按部就班地去做,总能算出结果.通常把算法过程称为“数学机械化”.数学机械化的最大优点是它可以让计算机来完成.本章主要以计算机能够实现的算法作为讨论的内容.

    2.实际上,处理任何问题都需要算法,中国象棋有中国象棋的棋谱,国际象棋有国际象棋的棋谱.再比如,邮寄物品有其相应的手续,购买飞机票也有一系列的手续等.

    3.解决某个问题的算法不唯一.

    【做一做1】 下列说法正确的是(  )

    A.算法就是某个问题的解题过程

    B.算法执行后可以产生不同的结论

    C.解决某一个具体问题,算法不同所得的结果不同

    D.算法执行步骤的次数不可以很多,否则无法实施

    解析:B项,如判断一个整数是否为偶数,结果有“是偶数”和“不是偶数”两种;A项,算法不能等同于解法;C项,解决某一个具体问题,算法不同所得的结果应该相同,否则算法不正确;D项,算法执行步骤的次数可以为很多次,但不可以为无限次.

    答案:B

  • 2.算法的表示形式

    描述算法可以有不同的方式.例如,可以用自然语言和数学语言加以叙述,也可以借助形式语言(算法语言)给出精确的说明,也可以用框图直观地显示算法的全貌.

    名师点拨

    对于数值型问题要建立数学模型,或通过固有的公式或计算方法设计算法;对于非数值型问题要建立过程模型,通过它来描述算法,在描述过程中,体会算法的含义和思想.

    【做一做2】 写出求方程$2 x+3=0$的解的算法步骤:$S1$_____________;$S2$_____________;$S3$_____________ . 

    答案:移项,得$2 x=-3$

    两边同除以2,得$x=-\frac{3}{2}$

    输出$x=-\frac{3}{2}$

  • 3.算法设计的要求

    (1)写出的算法,必须能解决一类问题,并且能重复使用.

    (2)算法过程要能一步一步执行,每一步执行的操作,必须确切,不能含混不清,而且经过有限步后能得出结果.

    【做一做3】 写出一个判断圆$(x-a)^{2}+(y-b)^{2}=r^{2}$和直线$A x+B y+C=0$的位置关系的算法.

    解:算法步骤如下:

    $S1$ 输入圆心的横坐标a、纵坐标b、直线方程的系数$A,B,C$和半径$r$的值;

    $S2$ 计算$z_{1}=A a+B b+C$;

    $S3$ 计算$z_{2}=A^{2}+B^{2}$;

    $S4$ 计算$d=\frac{\left|z_{1}\right|}{\sqrt{z_{2}}}$;

    $S5$ 如果$d>r$,那么直线与圆相离;如果d=r,那么直线与圆相切;如果$d < r$,那么直线与圆相交.

  • 4.高斯消去法

    高斯消去法是求解二元一次方程组的一种算法,其实质就是用加减法消元,通过对系数变换,达到求解的目的.设二元一次方程组为$\left\{\begin{array}{l}{a_{11} x_{1}+a_{12} x_{2}=b_{1},①} \\ {a_{21} x_{1}+a_{22} x_{2}=b_{2} \cdot②}\end{array}\right.$

    用高斯消去法求解的算法步骤如下:

    $S1$

    假定$a_{11} \neq 0$(若$a_{11}=0$,将方程$①$与方程$②$互换),$① \times\left(-\frac{a_{21}}{a_{11}}\right)+②$,得到$\left(\mathrm{a}_{22}-\frac{\mathrm{a}_{21} \mathrm{a}_{12}}{\mathrm{a}_{11}}\right) x 2=b 2-\frac{\mathrm{a}_{21} \mathrm{b}_{1}}{\mathrm{a}_{11}}$

    于是原方程组可化$\left\{\begin{array}{l}{a_{11} x_{1}+a_{12} x_{2}=b_{1}③} \\ {D x_{2}=a_{11} b_{2}-a_{21} b_{1} \cdot④}\end{array}\right.$

    $S2$

    若$D \neq 0$,由$④$得到$x 2=\frac{a_{11} b_{2}-a_{21} b_{1}}{D}$

    $S3$

    将$⑤$代入$③$,整理得到$x 1=\frac{a_{22} b_{1}-a_{12} b_{2}}{D}$

    $S4$

    输出结果$x_{1}, x_{2}$.

    若$D=0$,则由$④$知方程组无解或者有无穷多组解

    【做一做4】 试给出解下面方程组的一个算法:

    $\left\{\begin{array}①{2 x+y=5,(1)} \\ {4 x+5 y=11 .②}\end{array}\right.$

    解:算法步骤如下:

    $S1$ $①×(-2)+②$,得到$3 y=1$;

    $S2$ 解方程$③$,得到$y=\frac{1}{3}$;

    $S3$ 将$y=\frac{1}{3}$代入$①$,得到$x=\frac{7}{3}$;

    $S4$ 输出$x,y$的值.

重难点
  • 1.算法的五个特征

    剖析:(1)有穷性:一个算法应包含有限的操作步骤,而不能是无限的.

    (2)确定性:算法中的每一个步骤都应当是确定的,而不应当是模棱两可的.

    (3)有序性:算法是从初始步骤开始,分为若干个明确的步骤,前一步是后一步的前提,只有执行完前一步才能进行下一步,并且每一步都准确无误,才能解决问题.

    (4)不唯一性:求解某个问题的算法不一定是唯一的,对于同一个问题可以有不同的算法.

    (5)普遍性:很多具体的问题,都可以设计合理的算法去解决.

  • 2.教材中的“思考与讨论”

    说出你过去和现在对“算法”一词的理解.

    剖析:过去可能认为“算法”是“计算方法”的简称.通过本节课的学习,已经认识到“算法”与“计算方法”其实是两个不同的概念,不能混淆.

    现在学习的算法不同于求解一个具体问题(特殊)的计算方法,它有如下一些要求:(1)算法必须能解决一类问题,并且能够重复使用;(2)算法过程要能一步一步地执行,每一步执行的操作必须确切,而且有限步后能得出结果,所以算法并不是计算方法的简称,它是“解题方法的精确描述”,而计算方法则是对于求数值解的方法的研究.

例题解析
  • 对算法概念与特征的理解

    【例1】 下列叙述中表示的是解决问题的算法的个数为________. 

    ①找出十个数中的最大值;

    ②解一元一次方程的步骤是去分母、去括号、移项、合并同类项、系数化为1;

    ③测量某棵树的高度,判断其是不是大树;

    ④求$1×2×3×4$的值,先计算$1×2=2$,再由$2×3=6,6×4=24$得最终结果是$24$.

    反思

    算法中的每一个步骤不应产生歧义,而应当是明确无误的.有了确定的步骤之后,在执行过程中,我们只需一步一步机械地照着做即可.

    【变式训练1】 下列关于算法的说法,正确的是(  )

    A.某算法可以无止境地运算下去

    B.一个问题的算法步骤可以是可逆的

    C.完成一件事情的算法有且只有一种

    D.设计算法要本着简单方便可操作的原则

  • 数值型问题的算法描述

    【例2】 设计一个算法,求周长为6的正三角形的面积.

    分析:可有两种方法:方法一是先由周长求出该正三角形的边长,再求出正三角形的高,最后套用正三角形的面积公式求解;方法二是直接用公式$S=\frac{\sqrt{3}}{4}\left(\frac{l}{3}\right)^{2}$(其中$S$是面积,$l$是周长)代入求解.

    反思

    1.数值型问题主要是指以数值计算、数据处理为主的问题,它通常需要借助数学中相关的公式或定理解决问题.

    2.对于数值型算法,一般包括数据说明步骤(输入的信息、输出的结论)、数据处理步骤(计算、赋值)、逻辑判断步骤(真假判断)、重复步骤(循环特征),关键是先把解决问题的方法理清楚,再用算法语言按先后的逻辑关系表示即可.

    【变式训练2】 给出求$1+2+3+4+5+6$的一个算法.

    【例3】 已知函数$f(x)=\left\{\begin{array}{l}{x^{2}-x+1, x \geq 2} \\ {x+1, x < 2}\end{array}\right.$设计一个算法求函数的任一函数值.

    分析:此函数是分段函数,在不同区间上的函数解析式不同,函数值与自变量的取值范围有关,必须讨论自变量与2的关系.

    反思

    这是求分段函数函数值的一个基本算法,问题的核心是进行有效的判断,明确执行哪个命令.

    【变式训练3】 已知函数$y=\left\{\begin{array}{l}{-x^{2}-1, x \leq-1} \\ {x^{3}, x>-1}\end{array}\right.$试设计一个算法输入$x$的值,求对应的函数值.

  • 非数值型问题的算法描述

    【例4】 一个人带三只狼和三只羚羊过河,只有一条船,同船可以容纳一个人和两只动物,没有人在的时候,如果狼的数量不少于羚羊的数量,狼就会吃掉羚羊.

    (1)请你设计一个安全渡河的算法;

    (2)思考算法每一步所遵循的原则是什么.

    分析:解答本题可先根据条件建立过程模型,再设计算法.

    【变式训练4】 写出从下面的数字序列中,搜索出数“23”的一个算法.

    12 7 32 34 22 12 23 17 50

  • 真题

    1.下列四种叙述能称为算法的是(  )

    A.在家里一般是妈妈做饭

    B.做米饭时要经过刷锅、淘米、添水、加热这些步骤

    C.在野外做饭叫野炊

    D.做饭必须要有米

    2.下面对算法描述正确的一项是(  )

    A.算法只能用自然语言来描述

    B.算法只能用图形方式来表示

    C.同一问题可以有不同的算法

    D.同一问题的算法不同,结果也许不同

    3.某工厂生产的产品的数量每年递增18$\%$,若第一年的产量为$a$,计算第$n$年的产量$y$.在这个问题的算法中所用到的一个函数式为_______. 

    4.已知点$P\left(x_{0}, y_{0}\right)$和直线$l : A x+B y+C=0$,写出求点$P\left(x_{0}, y_{0}\right)$到直线l的距离d的一个算法.

    有如下步骤:①输入点的坐标$x_{0}, y_{0}$;②计算$z_{1}=A x_{0}+B y_{0}+C$;③计算

    $z_{2}=A^{2}+B^{2}$;④输入直线方程的系数$A, B, C$;⑤计算$d=\frac{\left|z_{1}\right|}{\sqrt{Z_{2}}}$;⑥输出$d$的值.

    5.某节目中,选手可以竞猜推出商品的价格(或质量),竞猜者如在规定的时间内猜出某种商品的价格(或质量),就可获得该件商品.现有一件商品,价格在1~8 000元之间,采取怎样的策略才能在较短的时间内说出正确的答案呢?试设计一种算法.

声明:本站部分内容搜集整理自互联网,如果涉及侵犯您的版权,请联系我们举报,并提供相关证据,工作人员会在5个工作日内回复您,一经查实,本站将立刻删除涉嫌侵权内容。