11算法的基本思想

《11算法的基本思想》由会员分享，可在线阅读，更多相关《11算法的基本思想（34页珍藏版）》请在金锄头文库上搜索。

1、 算法的基本思想1 1 1第二章第二章 算法初步算法初步 算法的基本思想算法的基本思想 1算法的含义、性质及作用算法的含义、性质及作用 2算法的特征算法的特征 特特 征征 概括性概括性 用用 具体内容具体内容 重复重复 使使写出的算法必须能解决一类问题，而且能写出的算法必须能解决一类问题，而且能 _步骤步骤 ，算法从初始步骤开始，分为若干个明确的算法从初始步骤开始，分为若干个明确的 _正确性和正确性和 前提前提 ，只有执行完上一步，才，只有执行完上一步，才上一步是下一步的上一步是下一步的 _顺序性顺序性 确切的含义确切的含义 能执行下一步，并且每一步都具有能执行下一步，并且每一步都具有 _有限

2、步有限步 之后结束之后结束 有限性有限性 一个算法必须在执行完一个算法必须在执行完 _唯一唯一 的，一个问题的，一个问题求解某个问题的算法不一定是求解某个问题的算法不一定是 _不唯一性不唯一性 不同不同 的算法的算法 可以有可以有_普遍性普遍性 算法算法 去去对于很多具体的问题，都可以设计合理的对于很多具体的问题，都可以设计合理的 _解决解决 3.算法设计的要求算法设计的要求 一类问题一类问题 (如判断一个整数是如判断一个整数是(1)写出的算法必须能够解决写出的算法必须能够解决 _ 重复重复 使用使用否为质数，否为质数， 求任意一个方程的近似解等求任意一个方程的近似解等 )， 并且能够并且能够

3、_ 步骤步骤 尽量少尽量少 (2)要使算法尽量简单，要使算法尽量简单， _正确正确 ，且算法步骤能够一步一步执行，每一步，且算法步骤能够一步一步执行，每一步(3)要保证算法要保证算法_确切确切 ，不能含混不清，而且在有限步后能得，不能含混不清，而且在有限步后能得执行的操作必须执行的操作必须 _结果结果 到到_ 判断正误判断正误(正确的打正确的打“”，错误的打，错误的打“”“” ) (1)算法与求解一个问题的方法相同算法与求解一个问题的方法相同 ( ) (2)算法过程要一步一步执行算法过程要一步一步执行 ( ) (3)有的算法执行完以后，可能没有结果有的算法执行完以后，可能没有结果 ( (4)设

4、计算法要本着简单方便的原则设计算法要本着简单方便的原则 ( ) 解析：根据算法的特征和要求知解析：根据算法的特征和要求知(1)(3)不正确，不正确，答案：答案：(1) (2) (3) (4) ) (2)(4)正确正确 看下面的四段话，其中不是算法的是看下面的四段话，其中不是算法的是 ( ) A从济南到温哥华旅游，要先坐火车，再转飞机抵达从济南到温哥华旅游，要先坐火车，再转飞机抵达 B解一元二次方程的步骤是去分母、去括号、移项、合并同解一元二次方程的步骤是去分母、去括号、移项、合并同类项，系数化为类项，系数化为 1 C方程方程 x 10 有两个实根有两个实根 D按顺序进行下列运算：按顺序进行下列

5、运算： 112，213，314，991100 2解析：选解析：选 C.算法强调的是解决一类问题的一系列的方法或步算法强调的是解决一类问题的一系列的方法或步骤，选项骤，选项C 只是陈述了有两个根的事实，没有写出如何求这两只是陈述了有两个根的事实，没有写出如何求这两个根的步骤或方法，所以不能看成是算法个根的步骤或方法，所以不能看成是算法 下列各式中下列各式中 S值不可以用算法求解的是值不可以用算法求解的是 ( ) AS1234 BS1222321002 CS111210 000 DS1234 解析：选解析：选 D.由算法的有限性知，由算法的有限性知，D 不正确，而不正确，而 A、以通过有限步步骤操

6、作，输出确定结果，故选以通过有限步步骤操作，输出确定结果，故选 D. B、C 都可都可 已知已知 A(x1，y1)，B(x2，y2)，求直线，求直线 AB的斜率的一个算法如的斜率的一个算法如下：下： 1输入输入 x1、y1、x2、y2的值的值 2计算计算 xx2x1， yy2y1. 3若若 x0，则输出斜率不存在，否则，则输出斜率不存在，否则k 4输出斜率输出斜率 k. 则则处应填处应填_ 答案：答案： y x ( x0)， 算法与数学中的解法的联系和区别算法与数学中的解法的联系和区别 (1)联系联系 算法与解法是一般与特殊的关系，也是抽象与具体的关系，算算法与解法是一般与特殊的关系，也是抽象

7、与具体的关系，算法的获取要借助一般意义上具体问题的求解方法，而任何一个法的获取要借助一般意义上具体问题的求解方法，而任何一个具体问题都可利用这类问题的一般方法解决具体问题都可利用这类问题的一般方法解决 (2)区别区别 算法是解决某些问题所需要的程序和步骤的统称，也可以理解算法是解决某些问题所需要的程序和步骤的统称，也可以理解为数学中的为数学中的“通法通解通法通解”；而解法是解决某一个具体问题的过；而解法是解决某一个具体问题的过程和步骤，是具体的解题过程程和步骤，是具体的解题过程 算法的概念算法的概念 (1)下列说法正确的是下列说法正确的是 ( ) A算法就是某个问题的解题过程算法就是某个问题的

8、解题过程 B算法执行后可以产生不同的结果算法执行后可以产生不同的结果 C解决某一个具体问题算法不同，则结果不同解决某一个具体问题算法不同，则结果不同 D算法执行步骤的次数不可以很大，否则无法实施算法执行步骤的次数不可以很大，否则无法实施 (2)下列关于算法的说法：下列关于算法的说法： 求解某一类问题的算法是唯一的；求解某一类问题的算法是唯一的； 算法必须在有限步操作后停止；算法必须在有限步操作后停止； 算法的每一步操作必须是明确的，不能存在歧义；算法的每一步操作必须是明确的，不能存在歧义； 算法执行后一定能产生确定的结果算法执行后一定能产生确定的结果 其中，不正确的有其中，不正确的有 _. 解

9、析：解析：(1)选项选项 B 正确，例如：判断一个整数是否为偶数，结果正确，例如：判断一个整数是否为偶数，结果为为“是偶数是偶数”和和“不是偶数不是偶数”两种；选项两种；选项A，算法不能等同于，算法不能等同于解法；解法；选项选项 C，解决某一个具体问题算法不同，解决某一个具体问题算法不同， 但结果应相同；但结果应相同；选项选项 D，算法可以有很多步，但不可以无限步，算法可以有很多步，但不可以无限步 (2)由算法的不唯一性，知由算法的不唯一性，知不正确；由算法的有穷性，知不正确；由算法的有穷性，知正正确；由算法的确定性，知确；由算法的确定性，知和和正确正确 答案：答案：(1)B (2) 理解算法

10、的关键点理解算法的关键点 (1)算法实际上是解决问题的一种程序性方法，它通常解决一类算法实际上是解决问题的一种程序性方法，它通常解决一类问题，用算法解决问题，体现了从特殊到一般的数学思想问题，用算法解决问题，体现了从特殊到一般的数学思想 (2)判断一个问题是否有算法，关键看是否有解决某一类问题的判断一个问题是否有算法，关键看是否有解决某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成在有限步之内完成 1.(1)下列叙述不能称为算法的是下列叙述不能称为算法的是 ( ) A从北京到上海先乘汽车到飞机场，再乘飞机到

11、上海从北京到上海先乘汽车到飞机场，再乘飞机到上海 B解方程解方程 4x10 的过程是先移项再把的过程是先移项再把 x 的系数化成的系数化成 1 C利用公式利用公式 Sr 计算半径为计算半径为 2 的圆的面积得的圆的面积得 2 D解方程解方程 x 2x10 (2)算法的有穷性是指算法的有穷性是指 ( ) A算法必须包含输出算法必须包含输出 B算法中每个操作步骤都是可执行的算法中每个操作步骤都是可执行的 C算法的步骤必须有限算法的步骤必须有限 D以上说法均不正确以上说法均不正确 222解析：解析：(1)选选 D.选项选项 A，B 给出了解决问题的方法和步骤，是算给出了解决问题的方法和步骤，是算法；

12、法；选项选项 C 是利用公式计算也属于算法；是利用公式计算也属于算法； 选项选项 D 只提出问题没只提出问题没有给出解决的方法，不是算法有给出解决的方法，不是算法 (2)选选 C.算法的有穷性是指算法的步骤必须有限算法的有穷性是指算法的步骤必须有限 算法的设计算法的设计 ? ? ?2xy7， 给出求解方程组给出求解方程组? ? ?11的一个算法的一个算法 ? ?4x5y解：法一：解：法一：(代入消元法代入消元法) 1由由 2xy7 得得 y72x. 2将将 y72x 代入代入 4x5y11，得，得 4x5(72x)11，解得，解得x4. 3将将 x4 代入方程代入方程 y72x，解得，解得 y

13、1. ? ?4输出方程组的解为输出方程组的解为? ? ?x4，? ? ? ?y1.法二：法二：(加减消元法加减消元法) 1方程方程 2xy7 两边都乘以两边都乘以 5得，得，10x5y35. 2将第将第 1 步所得的方程与方程步所得的方程与方程 4x5y11作差，消去作差，消去 y得得 6x24，解得，解得 x4. 3将将 x4 代入方程代入方程 2xy7，解得，解得 y1. ? ? ?x4，4输出方程组的解为输出方程组的解为? ? ? ? ?y1. 设计一个具体算法的步骤设计一个具体算法的步骤 (1)认真分析问题，找出解决此问题的一般数学方法认真分析问题，找出解决此问题的一般数学方法 (2)

14、借助有关变量或参数对算法加以表述借助有关变量或参数对算法加以表述 (3)将解决问题的过程划分为若干步骤将解决问题的过程划分为若干步骤 (4)用简单的语言将步骤表示出来用简单的语言将步骤表示出来 注意注意 设计的算法要能重复使用设计的算法要能重复使用 2.(1)已知直角三角形两直角边长为已知直角三角形两直角边长为a，b，求斜，求斜边长边长 c的一个算法分下列三步：的一个算法分下列三步： 计算计算 ca2b2； 输入直角三角形两直角边长输入直角三角形两直角边长 a，b的值；的值； 输出斜边长输出斜边长 c的值的值 其中正确的顺序是其中正确的顺序是 ( ) A B C D (2)写出一个算法，求经过

15、点写出一个算法，求经过点 M(2，1)，N(2，坐标轴围成的三角形的面积坐标轴围成的三角形的面积 3)的直线与两的直线与两解：解：(1)选选 D.明确各步骤间的关系即可知明确各步骤间的关系即可知 D 选项正确选项正确 (2)算法步骤如下：算法步骤如下： 1取取 x12，y11，x22，y23. yy1xx12得直线方程得直线方程. y2y1x2x13在第在第 2 步所得的方程中，令步所得的方程中，令 x0，得，得 y的值为的值为 1，从而得直，从而得直线与线与 y轴的交点为轴的交点为 B(0，1) 4在第在第 2 步所得的方程中，令步所得的方程中，令 y0，得，得 x 的值为的值为1，从而得，

16、从而得直线与直线与 x 轴的交点为轴的交点为 A(1，0) 115根据三角形的面积公式得根据三角形的面积公式得 S |1|1| . 226输出运算结果输出运算结果 实际生活问题的算法设计实际生活问题的算法设计 某商场举办优惠促销活动，某商场举办优惠促销活动，若购物金额在若购物金额在 800元以上元以上(不不含含 800元元)，打，打 7 折；若购物金额在折；若购物金额在 400元以上元以上(不含不含 400元元)，800元以下元以下(含含 800元元)，打，打 8 折；否则，不打折请为商场收银折；否则，不打折请为商场收银员设计一个算法，要求输入购物金额员设计一个算法，要求输入购物金额 x，输出

17、实际交款额，输出实际交款额 y. 解：算法步骤如下：解：算法步骤如下： 1输入购物金额输入购物金额 x(x0) 2判断判断“x800”是否成立，是否成立，若是，若是，则则 y0.7x，转第转第 4 步；步；否则，否则，执行第执行第 3 步步 3判断判断“x400”是否成立，若是，则是否成立，若是，则 y0.8x；否则，；否则，yx. 4输出输出 y，结束算法，结束算法 实际问题算法的设计技巧实际问题算法的设计技巧 (1)弄清题目中所给要求弄清题目中所给要求 (2)建立过程模型建立过程模型 (3)根据过程模型建立算法步骤，必要时由变量进行判断根据过程模型建立算法步骤，必要时由变量进行判断 3.(

18、1)已知一个学生的语文成绩为已知一个学生的语文成绩为89，数学成绩，数学成绩为为 96，外语成绩为，外语成绩为 99，求他的总分和平均分的一个算法如下，求他的总分和平均分的一个算法如下，请将其补充完整：请将其补充完整： 1取取 A89，B96，C99. 2_. 3_. 4输出计算结果输出计算结果 (2)有两个大人和两个小孩一起渡河，渡口只有一条小船，每次有两个大人和两个小孩一起渡河，渡口只有一条小船，每次最多只能渡一个大人或两个小孩他们四人都会划船，但都不最多只能渡一个大人或两个小孩他们四人都会划船，但都不会游泳，请你为他们设计一个渡河的算法会游泳，请你为他们设计一个渡河的算法 解：解：(1)

19、因为该算法的功能是求他的总分和平均分，所以因为该算法的功能是求他的总分和平均分，所以“第第2步步”应为计算总分应为计算总分 DABC， “第第 3 步步”应为计算平均分应为计算平均分 (2)1.两个小孩同船渡过河去两个小孩同船渡过河去 2一个小孩划船回来，另一个小孩留在对岸一个小孩划船回来，另一个小孩留在对岸 3一个大人划船渡过河去一个大人划船渡过河去 4对岸的小孩划船回来对岸的小孩划船回来 5两个小孩再次同船渡过河去两个小孩再次同船渡过河去 6一个小孩划船回来，另一个小孩留在对岸一个小孩划船回来，另一个小孩留在对岸 7另一个大人划船渡过河去另一个大人划船渡过河去 8对岸的小孩划船回来对岸的小

20、孩划船回来 9两个小孩同船渡过河去两个小孩同船渡过河去 思想方法思想方法 算法设计中的分类讨论思想算法设计中的分类讨论思想 2 给出解方程给出解方程 ax bxc0(a， b， c为实数为实数)的一个算法的一个算法 【解】【解】 算法步骤如下：算法步骤如下： 1当当 a0，b0，c0 时，解集为全体实数时，解集为全体实数 2当当 a0，b0，c0 时，原方程无实数根时，原方程无实数根 c3当当 a0，b0 时，原方程的解为时，原方程的解为 xb. 4当当 a0 且且 b 4ac0 时，方程有两个不等实根，时，方程有两个不等实根，x1bb 4acbb 4ac，x2. 2a2a5当当 a0 且且

21、b 4ac0 时，方程有两个相等实根，时，方程有两个相等实根， x1x2b. 2a6当当 a0 且且 b 4ac2，则执行，则执行步骤步骤 3； 3依次从依次从 2 到到(n1)检验能不能整除检验能不能整除 n，若不能整除，若不能整除 n，则输，则输出出 n；若能，则输出；若能，则输出“不满足条件不满足条件” 这个算法如果能输出这个算法如果能输出 n 的值，那么这个的值，那么这个 n 是是( ) A素数素数 B奇数奇数 C偶数偶数 D2 解析：解析： 选选 A.输出的数是大于输出的数是大于 1的自然数中，的自然数中， 除了除了 1和它本身外，和它本身外，再无法被其他自然数整除的数，这样的数是素

22、数再无法被其他自然数整除的数，这样的数是素数 3给出下面的算法：给出下面的算法： 1输入输入 x. 2判断判断 x 是否小于是否小于 0，若是，则输出，若是，则输出 x2，否则执行第，否则执行第 3 步步 3输出输出 x1. 当输入的当输入的x 的值分别为的值分别为 1，0，1 时，输出的结果分别为时，输出的结果分别为_ 、_ 、_ 解析：该算法实际上是分段函数解析：该算法实际上是分段函数 ? ?f(x)? ? ?x1，x0，? ?2，x0， ? ?x所以所以 f(1)121，f(1)110. 答案：答案：1 1 0 f(0)011， 4写出求二次函数写出求二次函数 y2x 4x1 的最大值的算法的最大值的算法 2解：算法如下：解：算法如下： 4acb4（2）141计算计算 m3. 4a4（2）2判断判断 a20，故，故 ymax3. 3输出二次函数的最大值输出二次函数的最大值 3. 22