第1部分第二章§11.1算法案例分析ppt课件

1、知识点二知识点二第第二二章章算算法法初初步步1 1算算法法的的根根本本思思想想知识点一知识点一了解教材新知了解教材新知运用创新演练运用创新演练考点一考点一把握热点考向把握热点考向考点二考点二考点三考点三1.11.1算算法法案案例例分分析析返回返回返回11算法案例分析算法案例分析返回返回返回返回 (1)算法是处理某类问题的一系列算法是处理某类问题的一系列 或或 ，只需，只需按照这些按照这些 执行，都能使问题得到处理执行，都能使问题得到处理 (2)在处理某些问题时，需求设计出一系列可操作或可计算在处理某些问题时，需求设计出一系列可操作或可计算的步骤，经过实施这些步骤来处理问题，通常把这些的步骤，经

2、过实施这些步骤来处理问题，通常把这些 称为称为处理这些问题的算法这种描画不是算法的严厉定义，但是反处理这些问题的算法这种描画不是算法的严厉定义，但是反映了算法的根本思想映了算法的根本思想步骤步骤程序程序步骤步骤步骤步骤返回 现代算法的作用之一是使计算机能替代人完成某些任务现代算法的作用之一是使计算机能替代人完成某些任务 算法的主要特征：算法的主要特征： (1)有穷性：一个算法的步骤是有限的，它应在有限有穷性：一个算法的步骤是有限的，它应在有限步操作之后停顿，而不能是无限的步操作之后停顿，而不能是无限的 (2)确定性：算法中的每一步应该是确定的并且能有确定性：算法中的每一步应该是确定的并且能有效

3、地执行和得到确定的结果，而不该当模棱两可，比如效地执行和得到确定的结果，而不该当模棱两可，比如让学生求让学生求 的近似值却没有要求近似的准确度，不同的的近似值却没有要求近似的准确度，不同的学生会得到不同的结果，或者说该问题根本不能求解学生会得到不同的结果，或者说该问题根本不能求解返回 (3)有序性：算法从初始步骤开场，分为假设干明确有序性：算法从初始步骤开场，分为假设干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只需执行完前一步才干进展下一步，并是后一步的前提，只需执行完前一步才干进展下一步，并且每一步都要准确无误，才

4、干处理问题且每一步都要准确无误，才干处理问题 (4)不独一性：求解某一个问题的算法不是独一的，不独一性：求解某一个问题的算法不是独一的，对于一个问题可以有不同的算法对于一个问题可以有不同的算法 (5)普遍性：很多详细的问题都可以设计合理的算法普遍性：很多详细的问题都可以设计合理的算法去处理，如心算、计算器计算都要经过有限的、事先设计去处理，如心算、计算器计算都要经过有限的、事先设计好的步骤加以处理好的步骤加以处理返回返回 例例1以下对算法的了解不正确的选项是以下对算法的了解不正确的选项是 () A一个算法应包含有限的步骤，而不能是无限的一个算法应包含有限的步骤，而不能是无限的 B算法可以了解为

5、由根本运算及规定的运算顺序构算法可以了解为由根本运算及规定的运算顺序构成的完好的解题步骤成的完好的解题步骤 C算法中的每一步都该当有效地执行，并得到确定的算法中的每一步都该当有效地执行，并得到确定的结果结果 D一个问题只能设计出一个算法一个问题只能设计出一个算法 思绪点拨思绪点拨先正确了解算法的概念及其特点，然后先正确了解算法的概念及其特点，然后逐一验证每个选项能否正确逐一验证每个选项能否正确. .返回精解详析精解详析选项选项判断判断原因分析原因分析A算法的有限性指包含的步骤是有限的算法的有限性指包含的步骤是有限的B算法的明确性是指每一步都是确定的算法的明确性是指每一步都是确定的C算法的每一步

6、都是确定的，且每一步都应算法的每一步都是确定的，且每一步都应有确定的结果有确定的结果D对于同一个问题可以有不同的算法对于同一个问题可以有不同的算法答案答案 D返回 一点通一点通解答这类问题的方法为特征判别法，主要从解答这类问题的方法为特征判别法，主要从以下三方面判别：以下三方面判别： (1)看能否满足顺序性算法实践上就是顺序化的解题过看能否满足顺序性算法实践上就是顺序化的解题过程，是指可以用计算机来处理某一类问题的程序或步骤程，是指可以用计算机来处理某一类问题的程序或步骤 (2)看能否满足明确性算法的每一步都是确定的，而不看能否满足明确性算法的每一步都是确定的，而不是模糊的、模棱两可的是模糊的

7、、模棱两可的 (3)看能否满足有限性一个算法必需在有限步后终看能否满足有限性一个算法必需在有限步后终了假设一个解题步骤永远不能终了，那么就永远得不到答了假设一个解题步骤永远不能终了，那么就永远得不到答案因此，有始无终的解题步骤不是算法案因此，有始无终的解题步骤不是算法 此外，算法的不独一性也要思索到此外，算法的不独一性也要思索到返回1以下表达能称为算法的个数为以下表达能称为算法的个数为 ()植树需求运苗、挖坑、栽苗、浇水这些步骤植树需求运苗、挖坑、栽苗、浇水这些步骤顺序进展以下运算：顺序进展以下运算：112,213,314，991100.3xx1.求一切能被求一切能被3整除的正数，即整除的正数

8、，即3,6,9,12，.A1 B2C3 D4返回解析：根据算法的含义和特征：都是算法不是解析：根据算法的含义和特征：都是算法不是算法其中，算法其中，3xx1不是一个明确的逻辑步骤，不符不是一个明确的逻辑步骤，不符合逻辑性；的步骤是无穷的，与算法的有穷性矛盾合逻辑性；的步骤是无穷的，与算法的有穷性矛盾答案：答案： B返回2有关算法的描画有以下几种说法：有关算法的描画有以下几种说法：对一类问题都有效；对一类问题都有效；对个别问题有效；对个别问题有效；计算可以一步一步地进展，每一步都有独一的结果；计算可以一步一步地进展，每一步都有独一的结果；是一种通法，只需按部就班地做，总能得到结果是一种通法，只需

9、按部就班地做，总能得到结果其中说法正确的选项是其中说法正确的选项是_解析：算法通常是指可以用计算机来处理的某一类问题解析：算法通常是指可以用计算机来处理的某一类问题的程序或步骤，所以正确，错误由于程序必需是的程序或步骤，所以正确，错误由于程序必需是明确的，有效的，而且在有限步之内完成，故正明确的，有效的，而且在有限步之内完成，故正确综上知，正确确综上知，正确答案：答案：返回 例例2写出解方程写出解方程x22x30的一个算法的一个算法 思绪点拨思绪点拨此题是一个求一元二次方程的解的问题，此题是一个求一元二次方程的解的问题，方法很多，可用配方法，也可用判别式法方法很多，可用配方法，也可用判别式法

10、精解详析精解详析法一：算法步骤如下：法一：算法步骤如下： 1移项，得移项，得x22x3. 2两边同加两边同加1并配方，得并配方，得(x1)24. 3式两边开方，得式两边开方，得x12. 4解，得解，得x3或或x1.返回 一点通一点通对于数值型计算问题的算法，可以借助对于数值型计算问题的算法，可以借助数学公式采用数学计算的方法，将过程分解成明晰的步数学公式采用数学计算的方法，将过程分解成明晰的步骤，使之条理化即可，但应留意多个数进展四那么运算骤，使之条理化即可，但应留意多个数进展四那么运算时应分步计算，依次进展，直到算出结果时应分步计算，依次进展，直到算出结果返回3求过求过P(a1，b1)，Q(

11、a2，b2)两点的直线斜率有如下的两点的直线斜率有如下的算算法，请在横线上填上适当步骤：法，请在横线上填上适当步骤：1取取x1a1，y1b1，x2a2，y2b2.2判别判别“x1x2能否成立，假设是，那么输出能否成立，假设是，那么输出“斜率不斜率不存在；否那么，进展下一步存在；否那么，进展下一步3_.4输出输出k.返回返回4写出求写出求123456的一个算法的一个算法解：算法一：解：算法一：1计算计算12得得3；2将第一步中的运算结果将第一步中的运算结果3与与3相加得到相加得到6；3将第二步中的运算结果将第二步中的运算结果6与与4相加得到相加得到10；4将第三步中的运算结果将第三步中的运算结果

12、10与与5相加得到相加得到15；5将第四步中的运算结果将第四步中的运算结果15与与6相加得到相加得到21.返回算法二：算法二：1将原式变形为将原式变形为(16)(25)(34)37；2计算计算37；3得到运算结果得到运算结果.返回 例例3一个人带着三只狼和三只羚羊过河，只需一一个人带着三只狼和三只羚羊过河，只需一条船，该船最多可包容一个人和两只动物没有人在的时条船，该船最多可包容一个人和两只动物没有人在的时候，假设狼的数量不少于羚羊的数量，狼就会吃羚羊此候，假设狼的数量不少于羚羊的数量，狼就会吃羚羊此人如何才干将动物平安转移过河？请设计一个算法人如何才干将动物平安转移过河？请设计一个算法 思绪

13、点拨思绪点拨人和动物同船不用思索狼会吃羚羊但需人和动物同船不用思索狼会吃羚羊但需思索承载的数量，另外还应思索到两岸的动物都得保证狼思索承载的数量，另外还应思索到两岸的动物都得保证狼的数量要小于羚羊的数量，故在算法的设计中应尽能够保的数量要小于羚羊的数量，故在算法的设计中应尽能够保证船里面有狼，这样才干使得两岸的羚羊数量占到优势证船里面有狼，这样才干使得两岸的羚羊数量占到优势 返回精解详析精解详析详细算法步骤如下：详细算法步骤如下：1人带两只狼过河，并本人前往人带两只狼过河，并本人前往2人带一只狼过河，并本人前往人带一只狼过河，并本人前往3人带两只羚羊过河，并带两只狼前往人带两只羚羊过河，并带两

14、只狼前往4人带一只羚羊过河，并本人前往人带一只羚羊过河，并本人前往5人带两只狼过河人带两只狼过河返回 一点通一点通处理此类问题需先建立过程模型，经过处理此类问题需先建立过程模型，经过模型进展算法设计与描画，设计详细的数学问题的算法，模型进展算法设计与描画，设计详细的数学问题的算法，实践上就是寻求一类问题的算法，它可以经过计算机来完实践上就是寻求一类问题的算法，它可以经过计算机来完成设计算法的关键是把过程分解成假设干个明确的步骤，成设计算法的关键是把过程分解成假设干个明确的步骤，然后用计算机能接受的然后用计算机能接受的“言语准确地描画出来言语准确地描画出来返回5早上从起床到出门需求洗脸刷牙早上从

15、起床到出门需求洗脸刷牙(5 min)、刷水壶、刷水壶(2 min)、烧水烧水(8 min)、泡面、泡面(3 min)、吃饭、吃饭(10 min)、听广播、听广播(8 min)几个几个步骤从以下选项中选出较好的一种算法步骤从以下选项中选出较好的一种算法 ()A第一步洗脸刷牙、第二步刷水壶、第三步烧水、第四第一步洗脸刷牙、第二步刷水壶、第三步烧水、第四步泡面、第五步吃饭、第六步听广播步泡面、第五步吃饭、第六步听广播B第一步刷水壶、第二步烧水同时洗脸刷牙、第三步泡第一步刷水壶、第二步烧水同时洗脸刷牙、第三步泡面、第四步吃饭、第五步听广播面、第四步吃饭、第五步听广播返回C第一步刷水壶、第二步烧水同时洗

16、脸刷牙、第三步泡面、第一步刷水壶、第二步烧水同时洗脸刷牙、第三步泡面、第四步吃饭同时听广播第四步吃饭同时听广播D第一步吃饭同时听广播、第二步泡面、第三步烧水同时第一步吃饭同时听广播、第二步泡面、第三步烧水同时洗脸刷牙、第四步刷水壶洗脸刷牙、第四步刷水壶解析：完成这个过程用时最少的是最好的算法，因此我们可以解析：完成这个过程用时最少的是最好的算法，因此我们可以从四个答案所给出的步骤能否合理，需求破费多少时间入手从四个答案所给出的步骤能否合理，需求破费多少时间入手答案：答案：C返回6有蓝和黑两个墨水瓶，但如今却错把蓝墨水装在有蓝和黑两个墨水瓶，但如今却错把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换回来，请设计一个算法处理这个问题换回来，请设计一个算法处理这个问题解：算法步骤如下：解：算法步骤如下：1取一只空的墨水瓶，设其为白色；取一只空的墨水瓶，设其为白色；2将黑墨水瓶中的蓝墨水装入白瓶中；将黑墨水瓶中的蓝墨水装入白瓶中；3将蓝墨水瓶中的黑墨水装入黑墨水瓶中；将蓝墨水瓶中的黑墨水装入黑墨水瓶中；4将白瓶中的蓝墨水装入蓝墨水瓶中；将白瓶中的蓝墨水装入蓝墨水瓶中；5交换终了交换终了返回1