算法第1章算法概述详解
- 格式:ppt
- 大小:2.07 MB
- 文档页数:47
算法与数据结构学习指导第一章第1章概述讲课提要【主要内容】1.数据结构的研究目的和研究内容2.数据结构中的几个重要概念和术语3.算法设计的基本要求以及算法复杂度的分析和计算方法【教学目标】1.了解数据结构的研究目的和研究内容2.掌握数据结构中的重要概念和术语3.掌握算法设计的基本要求以及算法复杂度的分析和计算方法【所需课时】2次课。
[第一次课]1.数据结构的研究目的和研究内容2.数据结构中的重要概念和术语[第二次课]3.算法设计的基本要求以及算法复杂度的分析和计算方法学习指导1.概念和术语数据:是能输入到计算机中并能被计算机程序处理的符号的总称。
数据元素:是数据的基本单位,它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。
一个数据元素可由若干数据项组成。
数据对象:是具有相同特征的数据元素的集合,是数据的一个子集。
数据结构:是数据元素的组织形式,或数据元素相互之间存在一种或多种特定关系的集合。
数据的逻辑结构:是指数据结构中数据元素之间的逻辑关系。
数据的存储结构:是数据的逻辑结构在计算机内存中的存储方式,又称物理结构。
数据类型:是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。
抽象数据类型:是指一个数学模型以及在该模型上定义的一套运算规则的集合。
算法:建立在数据结构基础上的,为解决问题而采取的步骤和方法。
2.逻辑结构的四种基本形态根据数据元素之间关系的不同特征,通常有下列四类基本结构:(1)集合:结构中的数据元素间除了“同属于一个集合”的关系外,别无其它关系。
(2)线性结构:结构中的数据元素之间存在一个对一个的关系。
(3)树型结构:结构中的数据元素之间存在一个对多个的关系。
(4)图型结构或网状结构:结构中的数据元素之间存在多个对多个的关系。
3.数据存储结构的基本组织方式数据存储结构有顺序和链式两种方式。
(1)顺序存储结构的特点:要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系,常用高级编程语言中的“一维数组”来描述或实现。
第1章 群体智能算法概述1975年,美国Michigan大学的John Holland[1]教授发表了其开创性的著作《Adapatation in Natural and Artificail System》,在该著作中John Holland教授对智能系统及自然界中的自适应变化机制进行了详细阐述,并提出了计算机程序的自适应变化机制,该著作的发表被认为是群体智能(Swarm Intelligence)[2]算法的开山之作。
随后,John Holland和他的学生对该算法机制进行了推广,并正式将该算法命名为遗传算法(Gentic Algorithm,GA)[3]~[5]。
遗传算法的出现和成功,极大地鼓舞了广大研究工作者向大自然现象学习的热情。
经过多年的发展,已经诞生了大量的群体智能算法,包括:遗传算法、蚁群优化(Ant Colony Optimization,ACO)[6]~[7]算法、差异演化(Differential Evolution,DE)[8]~[12]算法、粒子群优化(Particle Swarm Optimization,PSO)[13]~[16]算法等。
随着群体智能算法在诸如机器学习、过程控制、经济预测、工程预测等领域取得了前所未有的成功,它已经引起了包括数学、物理学、计算机科学、社会科学、经济学及工程应用等领域的科学家们的极大兴趣。
目前关于群体智能计算的国际会议在全世界各地定期召开,各种关于信息技术或计算机技术的国际会议也都将智能进化技术作为主要研讨课题之一。
甚至有专家指出,群体智能计算技术、混沌分析技术、分形几何、神经网络等将会成为研究非线性现象和复杂系统的主要工具,也将会成为人们研究认知过程的主要方法和工具。
1.1 群体智能算法的特点1.1.1 智能性群体智能算法通过向大自然界中的某些生命现象或自然现象学习,实现对于问题的求解,这一类算法中包含了自然界生命现象所具有的自组织、自学习和自适应性等特性。
第一章算法概述1、算法的五个性质:有穷性、确定性、能行性、输入、输出。
2、算法的复杂性取决于:(1)求解问题的规模(N) , (2)具体的输入数据(I),( 3)算法本身的设计(A),C=F(N,I,A。
3、算法的时间复杂度的上界,下界,同阶,低阶的表示。
4、常用算法的设计技术:分治法、动态规划法、贪心法、回溯法和分支界限法。
5、常用的几种数据结构:线性表、树、图。
第二章递归与分治1、递归算法的思想:将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。
递归的时间复杂性可归结为递归方程:1 11= 1T(n) <aT(n—b) + D(n) n> 1其中,a是子问题的个数,b是递减的步长,~表示递减方式,D(n)是合成子问题的开销。
递归元的递减方式~有两种:1、减法,即n -b,的形式。
2、除法,即n / b,的形式。
2、D(n)为常数c:这时,T(n) = 0(n P)。
D(n)为线形函数cn:r O(n) 当a. < b(NT(n) = < Ofnlog^n) "n = blljI O(I1P)二"A bl吋其中.p = log b a oD(n)为幕函数n x:r O(n x) 当a< D(b)II JT{ii) = O(ni1og b n) 'ia = D(b)ll].O(nr)D(b)lHJI:中,p= log b ao考虑下列递归方程:T(1) = 1⑴ T( n) = 4T(n/2) +n⑵ T(n) = 4T(n/2)+n2⑶ T(n) = 4T(n/2)+n3解:方程中均为a = 4,b = 2,其齐次解为n2。
对⑴,T a > b (D(n) = n) /• T(n) = 0(n);对⑵,•/ a = b2 (D(n) = n2) T(n) = O(n2iog n);对⑶,•/ a < b3(D(n) = n3) - T(n) = 0(n3);证明一个算法的正确性需要证明两点:1、算法的部分正确性。
第⼀章数据结构和算法简介—算法的时间复杂度和空间复杂度-总结算法的时间复杂度和空间复杂度-总结通常,对于⼀个给定的算法,我们要做两项分析。
第⼀是从数学上证明算法的正确性,这⼀步主要⽤到形式化证明的⽅法及相关推理模式,如循环不变式、数学归纳法等。
⽽在证明算法是正确的基础上,第⼆部就是分析算法的时间复杂度。
算法的时间复杂度反映了程序执⾏时间随输⼊规模增长⽽增长的量级,在很⼤程度上能很好反映出算法的优劣与否。
因此,作为程序员,掌握基本的算法时间复杂度分析⽅法是很有必要的。
算法执⾏时间需通过依据该算法编制的程序在计算机上运⾏时所消耗的时间来度量。
⽽度量⼀个程序的执⾏时间通常有两种⽅法。
⼀、事后统计的⽅法这种⽅法可⾏,但不是⼀个好的⽅法。
该⽅法有两个缺陷:⼀是要想对设计的算法的运⾏性能进⾏评测,必须先依据算法编制相应的程序并实际运⾏;⼆是所得时间的统计量依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本⾝的优势。
⼆、事前分析估算的⽅法因事后统计⽅法更多的依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本⾝的优劣。
因此⼈们常常采⽤事前分析估算的⽅法。
在编写程序前,依据统计⽅法对算法进⾏估算。
⼀个⽤⾼级语⾔编写的程序在计算机上运⾏时所消耗的时间取决于下列因素:(1). 算法采⽤的策略、⽅法;(2). 编译产⽣的代码质量;(3). 问题的输⼊规模;(4). 机器执⾏指令的速度。
⼀个算法是由控制结构(顺序、分⽀和循环3种)和原操作(指固有数据类型的操作)构成的,则算法时间取决于两者的综合效果。
为了便于⽐较同⼀个问题的不同算法,通常的做法是,从算法中选取⼀种对于所研究的问题(或算法类型)来说是基本操作的原操作,以该基本操作的重复执⾏的次数作为算法的时间量度。
1、时间复杂度(1)时间频度⼀个算法执⾏所耗费的时间,从理论上是不能算出来的,必须上机运⾏测试才能知道。
但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。
数学·必修3(人教A版)
本章概述
1.算法的含义、程序框图
(1)了解算法的含义,了解算法的思想.
(2)能根据问题设计运算(执行)步骤.
(3)
理解程序框图的三种基本逻辑结构:顺序、条件分支、循环.2.基本算法语句
理解几种基本算法语句——输入语句、输出语句、赋值语句、条件语句、循环语句的含义.
算法是从2007年开始出现在高考中的,从目前情况看,已成为高考必考内容,现在各地高考中算法主要考查程序框图的阅读和理解,而且难度较小,今后高考不排除考查阅读程序语言、画程序框图甚至写程序语言.由于采用“一标多本”的模式,因此考查框图的可能性最大.
算法初步。
§1.1算法与程序框图1.1.1算法的概念学习目标1.了解算法的含义和特征.2.会用自然语言描述简单的具体问题的算法.知识点一算法的概念知识点二算法的特征算法的五个特征(1)有限性:一个算法的步骤是有限的,它应在有限步操作之后停止.(2)确定性:算法中的每一步应该是确定的,并且能有效地执行且得到确定的结果,而不是模棱两可的.(3)逻辑性:算法从初始步骤开始,分为若干个明确的步骤,前一步是后一步的前提,只有完成前一步,才能进行下一步,而且每一步都是正确无误的,从而组成具有很强逻辑性的步骤序列.(4)普遍性:一个确定的算法,应该能够解决一类问题.(5)不唯一性:求解某一个问题的算法不一定只有唯一的一个,也可以有不同的算法.特别提醒:判断一个问题是不是算法,关键是明确算法的含义及算法的特征.知识点三算法的设计1.设计算法的目的设计算法的目的实际上是寻求一类问题的解决方法,它可以通过计算机来完成.设计算法的关键是把过程分解成若干个明确的步骤,然后用计算机能够接受的“语言”准确地描述出来,从而达到让计算机执行的目的.2.设计算法的要求①写出的算法必须能解决一类问题.②要使算法尽量简单、步骤尽量少.③要保证算法步骤有效,且计算机能够执行.1.算法是解决一个问题的方法.(×)2.一个算法可以产生不确定的结果.(×)3.算法的步骤必须是明确的、有限的.(√)4.求解一类问题的算法是唯一的.(×)题型一对算法概念的理解例1下列说法正确的是()A.算法就是某个问题的解题过程B.算法执行后可以产生不同的结果C.解决某一个具体问题算法不同,则结果不同D.算法执行步骤的次数不可以很多,否则无法实施★答案★ B解析选项B正确,例如:判断一个整数是否为偶数,结果为“是偶数”和“不是偶数”两种;选项A,算法不能等同于解法;选项C,解决某一个具体问题算法不同,但结果应相同;选项D,算法可以为很多次,但不可以为无限次.反思感悟算法实际上是解决问题的一种程序性方法,它通常解决某一个或一类问题,用算法解决问题,体现了从特殊到一般的数学思想.跟踪训练1下列描述不是解决问题的算法的是()A.从中山到北京先坐汽车,再坐火车B.解可化为一元一次方程的分式方程的步骤是去分母、去括号、移项、合并同类项、系数化为1C.方程x2-4x+3=0有两个不相等的实根D.解不等式ax+3>0时,第一步移项,第二步讨论★答案★ C解析A选项,从中山到北京,先坐汽车,再坐火车,解决了怎样去的问题;B选项,解可化为一元一次方程的分式方程的步骤:去分母、去括号、移项、合并同类项、系数化为1,解决了怎样解一元一次方程的问题;D选项,解不等式ax+3>0时,第一步移项,将不等式化为ax>-3,第二步讨论a的符号,进而根据不等式的基本性质,求出不等式的解集,解决了怎样求不等式解集的问题; 选项C 只是一个真命题,没有解决什么问题,因此不是算法.题型二 算法的设计命题角度1 直接应用数学公式设计算法例2 有一个底面半径为3,母线长为5的圆锥,写出求该圆锥体积的算法.解 如图,先给r ,l 赋值,计算h ,再根据圆锥体积公式V =13πr 2h 计算V ,然后输出结果.第一步,令r =3,l =5. 第二步,计算h =l 2-r 2. 第三步,计算V =13πr 2h .第四步,输出运算结果.反思感悟 利用公式解决问题时,必须先求出公式中的各个量,在设计算法时,应优先考虑未知量的求法.跟踪训练2 已知一个等边三角形的周长为a ,求这个三角形的面积.设计一个算法解决这个问题.解 第一步,输入a 的值. 第二步,计算l =a3的值.第三步,计算S =34×l 2的值. 第四步,输出S 的值.命题角度2 非数值性问题的算法例3所谓正整数p为素数是指:p的所有约数只有1和p.例如,35不是素数,因为35的约数除了1,35外,还有5与7;29是素数,因为29的约数就只有1和29.试设计一个能够判断一个任意正整数n(n>1)是否为素数的算法.解算法如下:第一步,给出任意一个正整数n(n>1).第二步,若n=2,则输出“2是素数”,判断结束.第三步,令m=1.第四步,将m的值增加1,仍用m表示.第五步,如果m≥n,则输出“n是素数”,判断结束.第六步,判断m能否整除n,①如果能整除,则输出“n不是素数”,判断结束;②如果不能整除,则转第四步.反思感悟设计一个具体问题的算法,通常按以下步骤(1)认真分析问题,找出解决该问题的一般数学方法.(2)借助有关变量或参数对算法加以表述.(3)将解决问题的过程划分为若干步骤.(4)用简练的语言将这个步骤表示出来.跟踪训练3判断一个大于2的整数是否为质数的算法步骤如何设计?解第一步,给定大于2的整数n.第二步,令i=2.第三步,用i除n,得到余数r.第四步,判断“r=0”是否成立.若是,则n不是质数,结束算法;否则,将i的值增加1,仍用i表示.第五步,判断“i>(n-1)”是否成立.若是,则n是质数,结束算法;否则,返回第三步.解方程组的算法设计典例 写出解方程组⎩⎪⎨⎪⎧2x +y =7,①4x +5y =11②的一个算法.解 方法一 (代入消元法) 第一步,由①得y =7-2x .③ 第二步,将③代入②,得4x +5(7-2x )=11.④ 第三步,解④得x =4.第四步,将x =4代入③,得y =-1.第五步,得到方程组的解为⎩⎪⎨⎪⎧x =4,y =-1.方法二 (加减消元法)第一步,①×5-②得,(2×5-4)x =7×5-11.⑤ 第二步,解⑤得x =4.第三步,①×2-②,得(1×2-5)y =7×2-11.⑥ 第四步,解⑥得y =-1.第五步,得到方程组的解为⎩⎪⎨⎪⎧x =4,y =-1.[素养评析] (1)设计算法时,经常遇到解方程组的算法问题,一般是按照数学上解方程组的方法进行设计,但应注意全面考虑方程组解的情况,即先确定方程组是否有解,有解时有几个解,然后依据求解步骤设计算法步骤.(2)从对运算方法的选择,运算程序的设计,到最后求得运算结果,整个过程就是典型的数学运算素养的体现.1.下列关于算法的说法正确的是()A.一个算法的步骤是可逆的B.描述算法可以有不同的方式C.算法可以看成是按照要求设计好的、有限的、确切的计算序列,并且这样的步骤或序列只能解决当前问题D.算法只能用一种方式显示★答案★ B解析由算法的定义知A,C,D错.2.下列叙述中:①植树需要运苗、挖坑、栽苗、浇水这些步骤;②按顺序进行下列运算:1+1=2,2+1=3,3+1=4,…,99+1=100;③从青岛乘火车到济南,再从济南乘飞机到广州;④3x>x+1;⑤求所有能被3整除的正数,即3,6,9,12,….能称为算法的个数为()A.2B.3C.4D.5★答案★ B解析根据算法的含义和特征知,①②③都是算法;④⑤不是算法.其中④只是一个问题,而没有解决问题,不能称为算法;⑤的步骤是无穷的,与算法的有限性矛盾.3.已知直角三角形两直角边长为a,b,求斜边长c的一个算法分下列三步:(1)计算c=a2+b2;(2)输入直角三角形两直角边长a,b的值;(3)输出斜边长c的值.其中正确的顺序是________. ★答案★ (2)(1)(3)解析 算法的步骤是有先后顺序的,第一步是输入,最后一步是输出,中间的步骤是赋值、计算.4.下面是解决一个问题的算法: 第一步:输入x .第二步:若x ≥4,转到第三步;否则转到第四步. 第三步:输出2x -1. 第四步:输出x 2-2x +3.当输入x 的值为________时,输出的数值最小值为________. ★答案★ 1 2解析 所给算法解决的问题是求分段函数f (x )=⎩⎪⎨⎪⎧2x -1,x ≥4,x 2-2x +3,x <4的函数值问题,当x ≥4时,f (x )=2x -1≥2×4-1=7;当x <4时,f (x )=x 2-2x +3=(x -1)2+2≥2,所以f (x )min =2,此时x =1.即输入x 的值为1时,输出的数值最小,最小值为2. 5.下面算法要解决的问题是____________________________. 第一步,输入三个数,并分别用a ,b ,c 表示.第二步,比较a 与b 的大小,如果a <b ,则交换a 与b 的值. 第三步,比较a 与c 的大小,如果a <c ,则交换a 与c 的值. 第四步,比较b 与c 的大小,如果b <c ,则交换b 与c 的值. 第五步,输出a ,b ,c .★答案★ 输入三个数a ,b ,c ,并按从大到小的顺序输出 解析 第一步是给a ,b ,c 赋值. 第二步运行后a >b . 第三步运行后a >c .第四步运行后b >c ,所以a >b >c .第五步运行后,显示a ,b ,c 的值,且从大到小排列.6.写出解二元一次方程组⎩⎪⎨⎪⎧3x -2y =-1,①2x +y =1 ②的算法.解 第一步,①+2×②得7x =1.③ 第二步,解③得x =17.第三步,②×3-①×2得7y =5.④ 第四步,解④得y =57.第五步,得到方程组的解为⎩⎨⎧x =17,y =57.1.算法的特点:有限性、确定性、逻辑性、普遍性、不唯一性. 2.算法设计的要求:(1)写出的算法必须能够解决一类问题(如判断一个整数是否为质数,求任意一个方程的近似解等),并且能够重复使用.(2)要使算法尽量简单,步骤尽量少.(3)要保证算法正确,且算法步骤能够一步一步执行,每步执行的操作必须确切,不能含混不清,而且在有限步后能得到结果.一、选择题1.下列可以看成算法的是( )A .学习数学时,课前预习,课上认真听讲并记好笔记,课下先复习再做作业,之后做适当的练习题B .今天餐厅的饭真好吃C .这道数学题难做D .方程2x 2-x +1=0无实数根★答案★ A解析 A 是学习数学的一个步骤,所以是算法.2.在用二分法求方程零点的算法中,下列说法正确的是( )A .这个算法可以求所有的零点B .这个算法可以求任何方程的零点C .这个算法能求所有零点的近似解D .这个算法可以求变号零点的近似解★答案★ D解析 二分法的理论依据是函数的零点存在性定理.它解决的是求变号零点的问题,并不能求所有零点的近似值.3.如下算法:第一步,输入x 的值.第二步,若x ≥0,则y =x .第三步,否则,y =x 2.第四步,输出y 的值.若输出的y 值为9,则x 的值为( )A .3B .-3C .3或-3D .-3或9 ★答案★ D解析 根据题意可知,此为分段函数y =⎩⎪⎨⎪⎧x ,x ≥0,x 2,x <0的算法, 当x ≥0时,x =9;当x <0时,x 2=9,所以x =-3.综上所述,x 的值是-3或9.4.对于算法:第一步,输入n .第二步,判断n 是否等于2,若n =2,则n 满足条件;若n >2,则执行第三步.第三步,依次从2到(n -1)检测能不能整除n ,若不能整除n ,则执行第四步;若能整除n ,则结束算法.第四步,输出n.满足条件的n是()A.质数B.奇数C.偶数D.合数★答案★ A解析此题首先要理解质数,只能被1和自身整除的大于1的整数叫质数.2是最小的质数,这个算法通过对2到(n-1)一一验证,看是否有其他约数,来判断其是否为质数.5.有蓝、黑两个墨水瓶,但现在却错把蓝墨水装在了黑墨水瓶中,黑墨水错装在了蓝墨水瓶中,要求将其互换,现有空墨水瓶若干,解决这一问题最少需要的步骤数为()A.2 B.3C.4 D.5★答案★ B解析第一步,将蓝墨水装到一个空墨水瓶中;第二步,将黑墨水装到黑墨水瓶中;第三步,将蓝墨水装到蓝墨水瓶中,这样就解决了这个问题,故选B.6.早上从起床到出门需要洗脸刷牙(5min)、刷水壶(2min)、烧水(8min)、泡面(3min)、吃饭(10min)、听广播(8min)几个过程.下列选项中最好的一种算法是()A.第一步,洗脸刷牙.第二步,刷水壶.第三步,烧水.第四步,泡面.第五步,吃饭.第六步,听广播B.第一步,刷水壶.第二步,烧水同时洗脸刷牙.第三步,泡面.第四步,吃饭.第五步,听广播C.第一步,刷水壶.第二步,烧水同时洗脸刷牙.第三步,泡面.第四步,吃饭同时听广播D.第一步,吃饭同时听广播.第二步,泡面.第三步,烧水同时洗脸刷牙.第四步,刷水壶★答案★ C解析最好算法的标准是方便、省时、省力.A中共需5+2+8+3+10+8=36(min),B中共需2+8+3+10+8=31(min),C中共需2+8+3+10=23(min),D中共需10+3+8+2=23(min),但算法步骤不合理,最好的算法为C.7.对于求18的正因数,给出下列两种算法:算法1:第一步,1是18的正因数,将1列出.第二步,2是18的正因数,将2列出.第三步,3是18的正因数,将3列出.第四步,4不是18的正因数,将4剔除.……第十八步,18是18的正因数,将18列出.算法2:第一步,18=2×9.第二步,18=2×32.第三步,列出所有的正因数1,2,3,32,2×3,2×32.则这两个算法()A.都正确B.算法1正确,算法2不正确C.算法1不正确,算法2正确D.都不正确★答案★ A解析算法1是用1~18的整数逐一验证,得出正因数.算法2是利用因数分解得到18的正因数.两种算法都正确.故选A.8.一个算法步骤如下:第一步,S取值0,i取值1.第二步,若i≤9,则执行第三步;否则,执行第六步.第三步,计算S+i并用结果代替S.第四步,用i+2的值代替i.第五步,转去执行第二步.第六步,输出S.运行以上算法,则输出的结果S等于()A.16 B.25C.36 D.以上均不对★答案★ B解析解本题关键是读懂算法,本题中的算法功能是求S=1+3+5+7+9=25.9.结合下面的算法:第一步,输入x.第二步,判断x是否小于0,若是,则输出x+2,否则执行第三步.第三步,输出x-1.当输入的x的值为-1,0,1时,输出的结果分别为()A.-1,0,1 B.-1,1,0C.1,-1,0 D.0,-1,1★答案★ C解析 依据算法可知,当x =-1时,满足x <0,则输出x +2=-1+2=1;当x =0时,不满足x <0,则输出x -1=0-1=-1;当x =1时,不满足x <0,则输出x -1=1-1=0.故选C.二、填空题10.下面给出了解决问题的算法:第一步:输入x .第二步:若x ≤1,则y =2x -1,否则y =x 2+3.第三步:输出y .(1)这个算法解决的问题是________;(2)当输入的x 值为________时,输入值与输出值相等.★答案★ (1)求分段函数y =⎩⎪⎨⎪⎧2x -1,x ≤1,x 2+3,x >1的函数值 (2)111.以下是解二元一次方程组⎩⎪⎨⎪⎧2x -y +6=0,①x +y +3=0 ②的一个算法,请将该算法补充完整. 第一步,①②两式相加得3x +9=0.③第二步,由③式可得________.④第三步,将④式代入①式得y =0.第四步,输出方程组的解为________.★答案★ x =-3 ⎩⎪⎨⎪⎧x =-3,y =0 解析 该算法的流程实质是解二元一次方程组的过程,由消元法易得.12.下面是求15和18的最小公倍数的算法,其中不恰当的一步是________.第一步,先将15分解素因数:15=3×5.第二步,然后将18分解素因数:18=32×2.第三步,确定它们的所有素因数:2,3,5.第四步,计算出它们的最小公倍数:2×3×5=30.★答案★ 第四步解析 素因数2,3,5的最高指数是1,2,1,算出它们的最小公倍数为2×32×5=90.三、解答题13.某商场举办优惠促销活动.若购物金额在800元以上(不含800元),打7折;若购物金额在400元以上(不含400元),800元以下(含800元),打8折;否则,不打折.请为商场收银员设计一个算法,要求输入购物金额x ,输出实际交款额y .解 算法步骤如下:第一步,输入购物金额x(x>0).第二步,判断“x>800”是否成立,若是,则y=0.7x,转第四步;否则,执行第三步.第三步,判断“x>400”是否成立,若是,则y=0.8x,转第四步;否则,y=x.第四步,输出y,结束算法.14.下面算法的功能是()第一步,令i=1.第二步,i除以3,得余数r.第三步,若r=0,则输出i;否则,执行第四步.第四步,令i的值增加1.第五步,若i≤1000,则返回第二步;否则,算法结束.A.求3的倍数B.求1至1000中3的倍数C.求i除以3D.求i除以3的余数★答案★ B解析由第二步和第三步可知,输出的是3的倍数,由第四步和第五步可知,输出的是1至1000中3的倍数.15.如图所示,汉诺塔问题是指有3根杆子A,B,C,杆子上有若干碟子,把所有的碟子从B杆移动到A杆上,每次只能移动一个碟子,大的碟子不能叠在小的碟子上面.把B杆上的3个碟子全部移动到A杆上,最少需要移动的次数是________.★答案★7解析直接进行分析,将最小的碟子命名为①,中间的碟子命名为②,最大的碟子命名为③,进行如下移动:①→A,②→C,①→C,③→A,①→B,②→A,①→A,此时按要求全部放好,移动7次.。
高中数学必修三第一章高中数学必修三第一章 1第一章算法初步1.1.1 算法的概念1、算法概念:在数学上,现代意义上的“算法”通常是指可以用计算机来解决的某一类问题是程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成.2. 算法的特点:(1)有限性:一个算法的步骤序列是有限的,必须在有限操作之后停止,不能是无限的.(2)确定性:算法中的每一步应该是确定的并且能有效地执行且得到确定的结果,而不应当是模棱两可.(3)顺序性与正确性:算法从初始步骤开始,分为若干明确的步骤,每一个步骤只能有一个确定的后继步骤,前一步是后一步的前提,只有执行完前一步才能进行下一步,并且每一步都准确无误,才能完成问题.(4)不唯一性:求解某一个问题的解法不一定是唯一的,对于一个问题可以有不同的算法.(5)普遍性:很多具体的问题,都可以设计合理的算法去解决,如心算、计算器计算都要经过有限、事先设计好的步骤加以解决.1.1.2 程序框图1、程序框图基本概念:(一)程序构图的概念:程序框图又称流程图,是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形。
一个程序框图包括以下几部分:表示相应操作的程序框;带箭头的流程线;程序框外必要文字说明。
(二)构成程序框的图形符号及其作用程序框名称功能起止框表示一个算法的开始和结束,对于任何流程图都是不可缺少的。
输入输出框表示算法的输入输出信息,可以用在算法中任何需要输入输出的位置。
处理框赋值、计算,算法中处理数据需要的算式、公式等分别写在不同的用以处理数据的处理框内。
判断框判断某一条件是否成立,成立时在出口处标明“是”或“Y”;不成立时明“否”或“N”。
学习这部分知识的时候,要掌握各个图形的形状、作用及使用规则,画程序框图的规则如下:1、使用标准的图形符号。
2.框图一般是从上到下,从左到右画的。
3、除判断框外,大多数流程图符号只有一个进入点和一个退出点。
判断框具有超过一个退出点的唯一符号。