算法案例分析.pptx

返回返回返回11算法案例分析算法案例分析返回返回返回返回 (1)算法是解决某类问题的一系列算法是解决某类问题的一系列 或或 ，只要，只要按照这些按照这些 执行，都能使问题得到解决执行，都能使问题得到解决 (2)在解决某些问题时，需要设计出一系列可操作或可计算在解决某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，通常把这些的步骤，通过实施这些步骤来解决问题，通常把这些 称为称为解决这些问题的算法这种描述不是算法的严格定义，但是反解决这些问题的算法这种描述不是算法的严格定义，但是反映了算法的基本思想映了算法的基本思想步骤步骤程序程序步骤步骤步骤步骤返回 现代算法的作用之一是使计算机能代替人完成某些工作现代算法的作用之一是使计算机能代替人完成某些工作 算法的主要特征：算法的主要特征：(1)有穷性：一个算法的步骤是有限的，它应在有限有穷性：一个算法的步骤是有限的，它应在有限步操作之后停止，而不能是无限的步操作之后停止，而不能是无限的 (2)确定性：算法中的每一步应该是确定的并且能有确定性：算法中的每一步应该是确定的并且能有效地执行和得到确定的结果，而不应当模棱两可，比如效地执行和得到确定的结果，而不应当模棱两可，比如让学生求让学生求 的近似值却没有要求近似的精确度，不同的的近似值却没有要求近似的精确度，不同的学生会得到不同的结果，或者说该问题根本不能求解学生会得到不同的结果，或者说该问题根本不能求解返回 (3)有序性：算法从初始步骤开始，分为若干明确的有序性：算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且后一步的前提，只有执行完前一步才能进行下一步，并且每一步都要准确无误，才能解决问题每一步都要准确无误，才能解决问题 (4)不唯一性：求解某一个问题的算法不是唯一的，对不唯一性：求解某一个问题的算法不是唯一的，对于一个问题可以有不同的算法于一个问题可以有不同的算法 (5)普遍性：很多具体的问题都可以设计合理的算法去普遍性：很多具体的问题都可以设计合理的算法去解决，如心算、计算器计算都要经过有限的、事先设计好解决，如心算、计算器计算都要经过有限的、事先设计好的步骤加以解决的步骤加以解决返回返回 例例1下列对算法的理解不正确的是下列对算法的理解不正确的是 ()A一个算法应包含有限的步骤，而不能是无限的一个算法应包含有限的步骤，而不能是无限的 B算法可以理解为由基本运算及规定的运算顺序构算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤成的完整的解题步骤 C算法中的每一步都应当有效地执行，并得到确定的算法中的每一步都应当有效地执行，并得到确定的结果结果 D一个问题只能设计出一个算法一个问题只能设计出一个算法 思路点拨思路点拨先正确理解算法的概念及其特点，然后先正确理解算法的概念及其特点，然后逐一验证每个选项是否正确逐一验证每个选项是否正确.返回精解详析精解详析选项选项判断判断原因分析原因分析A算法的有限性指包含的步骤是有限的算法的有限性指包含的步骤是有限的B算法的明确性是指每一步都是确定的算法的明确性是指每一步都是确定的C算法的每一步都是确定的，且每一步都应算法的每一步都是确定的，且每一步都应有确定的结果有确定的结果D对于同一个问题可以有不同的算法对于同一个问题可以有不同的算法答案答案 D返回 一点通一点通解答这类问题的方法为特征判断法，主要从解答这类问题的方法为特征判断法，主要从以下三方面判断：以下三方面判断：(1)看是否满足顺序性算法实际上就是顺序化的解题过看是否满足顺序性算法实际上就是顺序化的解题过程，是指可以用计算机来解决某一类问题的程序或步骤程，是指可以用计算机来解决某一类问题的程序或步骤 (2)看是否满足明确性算法的每一步都是确定的，而不看是否满足明确性算法的每一步都是确定的，而不是含糊的、模棱两可的是含糊的、模棱两可的 (3)看是否满足有限性一个算法必须在有限步后结束看是否满足有限性一个算法必须在有限步后结束如果一个解题步骤永远不能结束，那么就永远得不到答案如果一个解题步骤永远不能结束，那么就永远得不到答案因此，有始无终的解题步骤不是算法因此，有始无终的解题步骤不是算法 此外，算法的不唯一性也要考虑到此外，算法的不唯一性也要考虑到返回1下列叙述能称为算法的个数为下列叙述能称为算法的个数为 ()植树需要运苗、挖坑、栽苗、浇水这些步骤植树需要运苗、挖坑、栽苗、浇水这些步骤顺序进行下列运算：顺序进行下列运算：112,213,314，991100.3xx1.求所有能被求所有能被3整除的正数，即整除的正数，即3,6,9,12，.A1 B2C3 D4返回解析：解析：根据算法的含义和特征：根据算法的含义和特征：都是算法都是算法不是不是算法其中算法其中，3xx1不是一个明确的逻辑步骤，不符合不是一个明确的逻辑步骤，不符合逻辑性；逻辑性；的步骤是无穷的，与算法的有穷性矛盾的步骤是无穷的，与算法的有穷性矛盾答案：答案：B返回2有关算法的描述有下列几种说法：有关算法的描述有下列几种说法：对一类问题都有效；对一类问题都有效；对个别问题有效；对个别问题有效；计算可以一步一步地进行，每一步都有唯一的结果；计算可以一步一步地进行，每一步都有唯一的结果；是一种通法，只要按部就班地做，总能得到结果是一种通法，只要按部就班地做，总能得到结果其中说法正确的是其中说法正确的是_解析：解析：算法通常是指可以用计算机来解决的某一类问题算法通常是指可以用计算机来解决的某一类问题的程序或步骤，所以的程序或步骤，所以正确，正确，错误由于程序必须是错误由于程序必须是明确的，有效的，而且在有限步之内完成，故明确的，有效的，而且在有限步之内完成，故正确正确综上知，综上知，正确正确答案：答案：返回 例例2写出解方程写出解方程x22x30的一个算法的一个算法 思路点拨思路点拨本题是一个求一元二次方程的解的问题，本题是一个求一元二次方程的解的问题，方法很多，可用配方法，也可用判别式法方法很多，可用配方法，也可用判别式法 精解详析精解详析法一：法一：算法步骤如下：算法步骤如下：1移项，得移项，得x22x3.2两边同加两边同加1并配方，得并配方，得(x1)24.3式两边开方，得式两边开方，得x12.4解解，得，得x3或或x1.返回 一点通一点通对于数值型计算问题的算法，可以借助对于数值型计算问题的算法，可以借助数学公式采用数学计算的方法，将过程分解成清晰的步数学公式采用数学计算的方法，将过程分解成清晰的步骤，使之条理化即可，但应注意多个数进行四则运算时骤，使之条理化即可，但应注意多个数进行四则运算时应分步计算，依次进行，直到算出结果应分步计算，依次进行，直到算出结果返回3求过求过P(a1，b1)，Q(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将第三步中的运算结果将第三步中的运算结果10与与5相加得到相加得到15；5将第四步中的运算结果将第四步中的运算结果15与与6相加得到相加得到21.返回算法二：算法二：1将原式变形为将原式变形为(16)(25)(34)37；2计算计算37；3得到运算结果得到运算结果.返回 例例3一个人带着三只狼和三只羚羊过河，只有一一个人带着三只狼和三只羚羊过河，只有一条船，该船最多可容纳一个人和两只动物没有人在的时条船，该船最多可容纳一个人和两只动物没有人在的时候，如果狼的数量不少于羚羊的数量，狼就会吃羚羊此候，如果狼的数量不少于羚羊的数量，狼就会吃羚羊此人如何才能将动物平安转移过河？请设计一个算法人如何才能将动物平安转移过河？请设计一个算法 思路点拨思路点拨人和动物同船不用考虑狼会吃羚羊但需人和动物同船不用考虑狼会吃羚羊但需考虑承载的数量，另外还应考虑到两岸的动物都得保证狼考虑承载的数量，另外还应考虑到两岸的动物都得保证狼的数量要小于羚羊的数量，故在算法的设计中应尽可能保的数量要小于羚羊的数量，故在算法的设计中应尽可能保证船里面有狼，这样才能使得两岸的羚羊数量占到优势证船里面有狼，这样才能使得两岸的羚羊数量占到优势 返回精解详析精解详析具体算法步骤如下：具体算法步骤如下：1人带两只狼过河，并自己返回人带两只狼过河，并自己返回2人带一只狼过河，并自己返回人带一只狼过河，并自己返回3人带两只羚羊过河，并带两只狼返回人带两只羚羊过河，并带两只狼返回4人带一只羚羊过河，并自己返回人带一只羚羊过河，并自己返回5人带两只狼过河人带两只狼过河返回 一点通一点通解决此类问题需先建立过程模型，通过解决此类问题需先建立过程模型，通过模型进行算法设计与描述，设计具体的数学问题的算法，模型进行算法设计与描述，设计具体的数学问题的算法，实际上就是寻求一类问题的算法，它可以通过计算机来完实际上就是寻求一类问题的算法，它可以通过计算机来完成设计算法的关键是把过程分解成若干个明确的步骤，成设计算法的关键是把过程分解成若干个明确的步骤，然后用计算机能接受的然后用计算机能接受的“语言语言”准确地描述出来准确地描述出来返回5早上从起床到出门需要洗脸刷牙早上从起床到出门需要洗脸刷牙(5 min)、刷水壶、刷水壶(2 min)、烧水烧水(8 min)、泡面、泡面(3 min)、吃饭、吃饭(10 min)、听广播、听广播(8 min)几个步骤从下列选项中选出较好的一种算法几个步骤从下列选项中选出较好的一种算法 ()A第一步洗脸刷牙、第二步刷水壶、第三步烧水、第四第一步洗脸刷牙、第二步刷水壶、第三步烧水、第四步泡面、第五步吃饭、第六步听广播步泡面、第五步吃饭、第六步听广播B第一步刷水壶、第二步烧水同时洗脸刷牙、第三步泡第一步刷水壶、第二步烧水同时洗脸刷牙、第三步泡面、第四步吃饭、第五步听广播面、第四步吃饭、第五步听广播返回C第一步刷水壶、第二步烧水同时洗脸刷牙、第三步泡面、第一步刷水壶、第二步烧水同时洗脸刷牙、第三步泡面、第四步吃饭同时听广播第四步吃饭同时听广播D第一步吃饭同时听广播、第二步泡面、第三步烧水同时第一步吃饭同时听广播、第二步泡面、第三步烧水同时洗脸刷牙、第四步刷水壶洗脸刷牙、第四步刷水壶解析：解析：完成这个过程用时最少的是最好的算法，因此我们可以完成这个过程用时最少的是最好的算法，因此我们可以从四个答案所给出的步骤是否合理，需要花费多少时间入手从四个答案所给出的步骤是否合理，需要花费多少时间入手答案：答案：C返回6有蓝和黑两个墨水瓶，但现在却错把蓝墨水装在有蓝和黑两个墨水瓶，但现在却错把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换回来，请设计一个算法解决这个问题互换回来，请设计一个算法解决这个问题解：解：算法步骤如下：算法步骤如下：1取一只空的墨水瓶，设其为白色；取一只空的墨水瓶，设其为白色；2将黑墨水瓶中的蓝墨水装入白瓶中；将黑墨水瓶中的蓝墨水装入白瓶中；3将蓝墨水瓶中的黑墨水装入黑墨水瓶中；将蓝墨水瓶中的黑墨水装入黑墨水瓶中；4将白瓶中的蓝墨水装入蓝墨水瓶中；将白瓶中的蓝墨水装入蓝墨水瓶中；5交换结束交换结束返回1写一个算法应遵循由粗到细的处理问题的方法，先确定写一个算法应遵循由粗到细的处理问题的方法，先确定大的框架，再根据情况具体化，这是设计算法时普遍采大的框架，再根据情况具体化，这是设计算法时普遍采用的方法用的方法2给出一个问题，设计算法时要注意：给出一个问题，设计算法时要注意：(1)认真分析问题，联系解决此问题的一般数学方法；认真分析问题，联系解决此问题的一般数学方法；(2)综合考虑此类问题中可能涉及的各种情况；综合考虑此类问题中可能涉及的各种情况；(3)将解决问题的过程划分为若干个步骤将解决问题的过程划分为若干个步骤返回