算法的基本思想3

算法的基本思想演示文稿现在是1页\一共有19页\编辑于星期日算法的基本思想现在是2页\一共有19页\编辑于星期日算法的基本思想现在是3页\一共有19页\编辑于星期日【例1】在电视台的某个娱乐节目中，要求参与者快速猜出物品的价格。主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或者正确。在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜。下面是主持人和参与者的一段对话：….如果你是参与者，你接下来会怎么猜？800元！高了400元！600元！低了高了参与者主持人：李咏现在是4页\一共有19页\编辑于星期日例2：给定素数表，设计算法，将936分解成素因数的乘积。判断936是否为素数：确定936的最小素因数：确定468的最小素因数：判断468是否为素数：判断234是否为素数：确定234的最小素因数：否2936＝468×2936＝234×22936＝117×23否2否2现在是5页\一共有19页\编辑于星期日判断117是否为素数：否确定117的最小素因数：936＝39×23×33判断39是否为素数：否确定39的最小素因数：3936＝13×23×32判断13是否为素数：是结束分解结果为：936＝13×23×32936468234117392223133现在是6页\一共有19页\编辑于星期日练习：将下列两个数分解素因数

（1）840（2）1764现在是7页\一共有19页\编辑于星期日例3：设计一个算法，求840与1764的最大公因数。解：算法步骤如下：1.先将840进行素因数分解：840=23×3×5×7；3.确定它们公共素因数：2,3,7；4.确定公共素因数的指数：公共素因数2，3,7的指数分别为2,1,1；2.先将1764进行素因数分解:1764=22×32×72；5.最大公因数为：22×31×71=84现在是8页\一共有19页\编辑于星期日写算法的要求写出的算法，必须能解决一类问题（如求两个正整数的最大公因数），并且能重复使用。算法过程要一步一步执行，每一步执行的操作必须明确，不能含混不清，而且在有限步骤内能得出结果。算法要简洁，清晰可读，不能搞得繁杂。算法不同于求解一个具体问题的方法，是这种方法的高度概括。一个好的算法有如下要求：现在是9页\一共有19页\编辑于星期日算法是什么算法可以理解为由基本运算及规定的运算顺序构成的一个完整的解题步骤，或看成是按要求设计好的有限的、确切的计算步骤，并且这样的步骤能解决一类问题。现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤。现在是10页\一共有19页\编辑于星期日“韩信点兵”问题现在是11页\一共有19页\编辑于星期日现在是12页\一共有19页\编辑于星期日思考以下问题的算法：一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？现在是13页\一共有19页\编辑于星期日现在是14页\一共有19页\编辑于星期日解:

2．先将两组分别放在天平的两边。如果天平不平衡，那边假银元就放在轻的那一组；如果天平左右平衡，则假银元就在末称的第3组里。3．取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则末称的那一枚就是假银元。1.把银元分成3组，每组3枚。现在是15页\一共有19页\编辑于星期日现在是16页\一共有19页\编辑于星期日说明：1算法实际上就是解决某一类问题的步骤和方法，在解决问题时形成的规律性的东西，按照算法描述的规则与步骤，一步一步地去做，最终便能解决问题。2算法的基本思想就是我们分析问题时的想法。由于想法不同思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分。3从熟悉的问题出发，体会算法的程序化思想，学会用自然语言来描述算法现在是17页\一共有19页\编辑于星期日算法的特点：有限性：一个算法的步骤必须是有限的，必须在有限操作之后停止，不能是无限的.确定性：算法中的每一步应该是确定的并且能有效地执行且得到确定的结果，而不应当是模棱两可.普遍性：一个算法通常设计成能解决一类问题，不不唯一性：求解某一个问题的解法不一定是唯一的，对于一个问题可以有不同的算法.是仅仅解决一