算法的概念

  • A+
所属分类:算法初步

假设家中生火泡茶有以下几个步骤:

$a.$ 生火   $b.$ 将水倒入壶中   $c.$找茶叶   $d.$洗茶壶、茶碗   $e.$用开水冲茶

请选出一个最优方案(     )(注意:有些工作可以同时进行)

$A$. $abcde$      $B$. $bacde$      $C$. $cadbe$      $D$. $dcabe$

广义的算法是指完成某项工作的方法和步骤,那么我们可以说洗衣机的使用说明书是操作洗衣机的算法,菜谱是做菜的算法等.

算法的概念:算法(algorithm)一词出现于12世纪,指的是用阿拉伯数字进行算术运算的过程.在数学中,算法通常是指按照一定规则解决某一类问题的明确和有限的步骤.现在,算法通常可以编成计算机程序,让计算机执行并解决问题.

算法的基本特征

明确性:算法的每一个步骤都是确切的,能有效执行且得到确定结果,不能模棱两可.

有限性:算法应由有限步组成,至少对某些输入,算法应在有限多步内结束,并给出计算结果.

有效性:算法从初始步骤开始,分为若干明确的步骤,每一步都只能有一个确定的继任者,只有执行完前一步才能进入到后一步,并且每一步都确定无误后,才能解决问题.

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

写出解方程组$\left\{\begin{array}{l}{3x-2y=3}\\{2x+y=4}\end{array} \right.$的步骤

第一步,(消元)$①+②×2$,得 $7x=11$.   ③

第二步,(解一元一次方程)解$③$得$x=\dfrac {11}{7}.$

第三步,(代入求解)将$x=\dfrac {11}{7}$代入$①$,得$x=\dfrac {6}{7}.$

【思考1】解方程组$\begin{cases}a_1x+b_1y=c_1\\a_2x+b_2y=c_2\end{cases}$ $(a_1b_2-a_2b_1\ne 0)$的算法该如何写?

第一步,$①×a_2- ②×a_1$得$(a_2b_1-a_1b_2)y=a_2c_1-a_1c_2$. $③$

第二步,解$③$,得$x=\dfrac{a_2c_1-a_1c_2}{a_2b_1-a_1b_2}$

第三步,将$④$代入$①$得$x=\dfrac{b_1c_2-b_2c_1}{a_2b_1-a_1b_2}$

【思考2】问题2:请你说出登录腾讯QQ的步骤.(电脑已经打开)

第一步:打开QQ程序.

第二步:输入QQ号码.

第三步:输入密码.

第四步:点击登录.

【思考3】一位商人有9枚金币,其中有一枚略轻的假币,你能用天平(无砝码)将假币找出来吗?写出解决这一问题的算法.

第一步,把9枚金币平均分成三组,每组三枚.

第二步,先将其中的两组放在天平的两边,如果天平不平衡,那么假金币就在轻的那一组;如果天平左右平衡,则假金币就在未称量的那一组里.

第三步,取出含假币的那一组,从中任取两枚金币放在天平两边进行称量,如果天平不平衡,则假金币在轻的那一边;若平衡,则未称的那一枚就是假币.

【思考4】问题4:有人对歌德巴赫猜想“任何大于4的偶数都能写成两个奇质数之和”设计了如下操作步骤:

第一步,检验6=3+3.

第二步,检验8=3+5.

第三步,检验10=5+5.

……

利用计算机无穷地进行下去!

请问,利用这种程序能够证明猜想的正确性吗?这是一种算法吗?

很显然这种程序不能证明猜想的正确性,它根本就不是一种算法,因为它不具有算法的有限性.

例1.设计一个算法,判断7是否为质数.

算法分析:根据质数的定义,可以这样判断:依次用2~6除7,如果它们中有一个能整除7,则7不是质数,否则7是质数.

根据以上分析,可写出如下算法:

第一步,用2除7,得到余数1,因为余数不为0,所以2不能整除7.

第二步,用3除7,得到余数1,因为余数不为0,所以3不能整除7.

第三步,用4除7,得到余数3,因为余数不为0,所以4不能整除7.

第四步,用5除7,得到余数2,因为余数不为0,所以5不能整除7.

第五步,用6除7,得到余数1,因为余数不为0,所以6不能整除7.
因此,7是质数.

【变式练习】

1.设计一个算法,判断35是否为质数.

第一步,用2除35,得到余数1,因为余数不为0,所以2不能整除35.

第二步,用3除35,得到余数2,因为余数不为0,所以3不能整除35.

第三步,用4除35,得到余数3,因为余数不为0,所以4不能整除35.

第四步,用5除35,得到余数0,因为余数为0,所以5能整除35.因此,35不是质数.

2.有关算法的描述正确的是 (  )

$A$. 解决某一类问题的算法只能设计一个

$B$.算法可以无限步操作下去

$C$.算法执行后可以产生模棱两可的结果

$D$.算法一定在有限步操作之后停止

【解析】选$D.$因为算法是按照一定规则解决某一类问题的明确和有限的步骤,具有有限性、有序性、确定性和不唯一性,因此选项$A$,$B$,$C$错误,只有$D$选项正确.

想一想:什么是二分法?

对于区间$[a,b ]$上连续不断且$f(a)·f(b)<0$的函数$y=f(x)$,通过不断地把函数$f(x)$的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法叫做二分法.

【思考】:如何应用二分法求解实际问题呢?

例2.写出用“二分法”求方程$ x^2-2=0$($x>0$)的近似解的算法.

第一步,令$f(x)=x^2-2$,给定精确度$d$.

第二步,确定区间$[a,b]$,满足$f(a)·f(b)<0$.

第三步,取区间中点$m=\dfrac {a+b}{2}$

第四步,若$f(a)·f(m)<0$,则含零点的区间为$[a,m]$;否则,含零点的区间为$[m,b]$.将新得到的含零点的区间仍记为$[a,b]$.

第五步,判断$|a-b|<d$是否成立或$f(m)$是否等于$0$.若是,则$m$是方程的近似解;否则,返回第三步.

对于方程$x^2-2=0(x>0)$,给定%d=0.005%.

$a$$b$$|a-b|$
121
11.50.5
1.251.50.25
1.3751.50.125
1.3751.437 50.062 5
1.406 251.437 50.031 25
1.406 251.421 8750.015 625
1.414 062 51.421 8750.007 812 5
1.414 062 51.417 968 750.003 906 25

于是,开区间$(1.414 062 5,1.417 968 75)$中的实数都是当精确度为$0.005$时的原方程的近似解.此步骤也是求$\sqrt 2$的近似值的一个算法.

【变式练习】

任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.

第一步,输入任意一个正实数$r$;

第二步,计算圆的面积$S=\pi r^2$;

第三步,输出圆的面积$S$.

给出一个问题,设计算法时应注意的问题:

(1)认真分析问题,联系解决此问题的一般数学方法.

(2)综合考虑此类问题中可能涉及的各种情况.

(3)将解决问题的过程划分为若干个步骤.

(4)用简练的语言将各个步骤表示出来.

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: