算法的基本思想（一）.docxVIP

算法的基本思想（一） 咸阳渭城中学朱庆刚 作为家里的一员，在平时分担一些力所能及的事是 我们应尽的义务，你每天都帮家里做事吗？你会烧 开水吗？请写出你在家中烧开水的过程 1、 往壶内注水； 2、 点火加热； 3观察：如果水开，则停止烧火，否则继续烧火； 4、如果水未开，重复“3”直至水开。 总结： “1”其实大部分事情都是按照一定的程序执行，因此要理清事情的每一步。 “2”判断水是否烧开与是否继续烧火的过程是一个反馈与判断过程，因此有 必要不断重复过程“3” 事实上，我们完成任何事，都要有一个 步骤，合理安排步骤，会达到事半功倍 的效果。在我们数学的意义来讲，在解 决某些问题时，需要设计出一系列可操 作或可计算的步骤，通过实施这些步骤 来解决问题，我们通常把这些步骤称为 解决问题的一种算法。这种描述不是算 法的定义，但反映了算法的基本思想。 中国古代数学以算法为主要特征， 这可以从中国古代数学家的著作中 看出端倪，其中最具代表性的就是 《九章算术》，就其成就来说堪称 是世界数学名著，其内容按类分章点京 以数学问题的形式出现，包括分数k 四则运算，开平方和开立方（包括二次方程数值的解 法），盈不足术，各种面积和体积的计算公式，线性 方程组解法，正负数运算的加减法法则，勾股形解法 等。另外还有贾宪的《黄帝九章算法细草》、刘益 IS《议古根源》、秦九韶的《数书九章》，杨辉的《详 解九章算法》和《杨辉算法》等。 IS 随着计算科学和信息 技术的飞速发展，算法的思 想已经渗透到社会的方方面。 在以前的学习中，虽然没有 出现算法这个名词，但实际 上在数学教学中己经渗透了 大量的算法思想，如四则运 算的过程、求解方程的步骤 等等。完成这些工作都需要 三_== 一系列程序化的步骤，这就 是算法的思想。 【例1】在中央电视台的《幸运52》节目中，要求参 与者快速猜出物品的价格。主持人出示某件物品，参 与者每次估算出一个价格，主持人只能回答高了、低=1 与者每次估算出一个价格，主持人只能回答高了、低 =1 了或者正确。在某次节目中，主持人出示了一台价值 在1000元以内的随身听，并开始了竞猜。下面是主 持人和参与者的一段对话: 如果你是参与者, 你接下来会怎么猜？主持人李咏 在给定素数表的条件下，请你设计一个算法, 将936分成素因数的乘积. 解 算法步骤如下： 判断936是否为素数：否。 确定936的最小素因数：2o 936=2X468 判断468是否为素数：否。 确定468的最小素因数：2o 936=2X2X234。 判断234是否为素数：否。 确定234的最小素因数：2。936=2X2X2X 117。 判断117是否为素数：否。 确定117的最小素因数：3« 936=2X2X2X3X39。 判断39是否为素数：否。 确定39的最小素因数：30 936=2X2X2X3X3X 13。 判断13是否为素数：13是素数，所以分解结束。 分解结果是：936=2X2X2X3X3X13 现代意义上的「算法』通常是 指可以用计算机来解决的某一 类问题的程序或步骤。 算法是什么算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤，或看成按要求设计好的有限的、确切的计算序列，并且这样的步骤或序列能解决一类问题。 写算法的要求 算法不同于求解一个具体问题的方法，是这种 方法的高度概括。一个好的算法有如下要求: 方法的高度概括。一个好的算法有如下要求: =J #写出的算法，必须能解决一类问题（如一元二 次方程求根公式），并且能重复使用。 #算法过程要能一步一步执行，每一步执行的操 #算法过程要能一步一步执行，每一步执行的操 [€1 作，必须确切，不能含混不清，而且在有限步 能得出结果。 #算法要简洁，要清晰可读，不能弄搞繁杂，以 以致于易程序化。 840 = 23X3X5X71764 = 22X32X72倒 840 = 23X3X5X7 1764 = 22X32X72 先将840进行素因数分解: 将1764进行素因数分解: 3.确定它们的公共素因数： 2, 3, 7 4.确定它们的公共素因数的指数：2, 1, 1 5.最大公因数为: 5.最大公因数为: 22x3x7 = 84 小结:求x,y的最大公因数及最小公倍数的方法 1、 先把x,y这两个数分解素因数 x = 2ax3hx5c ••• y = 2ax3bx5c ••• 2、 最大公约数取x和y的公共的且次数最小 的素因数相乘 3、 最小公倍数取x和y的公共的且次数最大 的素因数相乘，再乘以不公共的质因数 比如求12和30的最大公约数和最小公倍数： 12=22X3,30=2X3X5 I=J最大公约数=2X3=6, 最小公倍数=22X3X5=60 I=J 练习1给出求1+2+3+4+5的一