算法的基本思想

《算法的基本思想》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章算法初步§1算法的基本思想1.了解算法的含义，形成算法的初步印象，体会算法是解决问题的“机械”程序，并能在有限步内解决问题；2.能够用自然语言叙述算法；3.掌握正确的算法应满足的条件；4.会写出简单问题的算法.作为家里的一员，在平时分担一些力所能及的事是我们应尽的义务，你每天都帮家里做家务吗？你会烧开水吗？请写出你在家中烧开水的过程.1、往壶内注水；2、点火加热；3、观察：如果水开，则停止烧火，否则继续烧火；4、如果水未开，重复过程“3”，直至水开.2、判断水是否烧开与是否继续烧火的过程是一个反馈与判断的过程，因此有必要不断重复过程“3”.小结：1、其实大部分事情都是按照一

2、定的程序执行的，因此要理清事情的每一步.事实上，我们完成任何事，都要有步骤，合理安排步骤，会达到事半功倍的效果.从我们数学的意义来讲，在解决某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，我们通常把这些步骤称为解决问题的一种算法.这种描述不是算法的定义，但反映了算法的基本思想.随着计算科学和信息技术的飞速发展，算法的思想已经渗透到社会的方方面面.在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想，如四则运算的过程、求解方程的步骤等等.完成这些工作都需要一系列程序化的步骤，这就是算法的思想.例1在电视台的某个娱乐节目

3、中，要求参与者快速猜出物品的价格.主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或者正确.在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜.下面是主持人和参与者的一段对话：……如果你是参与者，你接下来会怎么猜？800元！高了!400元！600元！低了!低了!参与者主持人实际上，可以把过程概括如下：例2：给定素数表，设计算法，将936分解成素因数的乘积。判断936是否为素数：确定936的最小素因数：确定468的最小素因数：判断468是否为素数：判断234是否为素数：确定234的最小素因数：否2936＝468×2936＝234×2293

4、6＝117×23否2否2判断117是否为素数：否确定117的最小素因数：936＝39×23×33判断39是否为素数：否确定39的最小素因数：3936＝13×23×32判断13是否为素数：是结束分解结果为：936＝13×23×32936468234117392223133练习：将下列两个数分解素因数（1）840（2）1764例3设计一个算法，求840与1764的最大公因数.1.先将840进行素因数分解：；2.然后将1764进行素因数分解：；3.确定他们的公共素因数2,3,7；4.确定公共素因数的指数：公共素因数2,3,7的指数分别为2,1,1;5.最大公约数为:.解：算法步骤如下：

5、探索：求x,y的最大公因数及最小公倍数的方法。1、先把x,y这两个数分解素因数2、最大公约数取x和y的公共的且次数最小的素因数相乘3、最小公倍数取x和y的公共的且次数最大的素因数相乘,再乘以不公共的质因数比如求12和30的最大公约数和最小公倍数:12=22×3,30=2×3×5最大公约数=2×3=6,最小公倍数=22×3×5=60例4“韩信点兵”问题.韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为建立汉朝立下了汗马功劳.据说他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，采用下述点兵的方法：先令士兵从1～3报数，结果最后一个士兵报2；再令士兵从1～5报数，结果

6、最后一个士兵报3；又令士兵从1～7报数，结果最后一个士兵报4.这样，韩信很快就算出了自己部队的总人数.请设计一个算法，求出士兵至少有多少人?分析：从报数情况分析，总人数除以3余2；总人数除以5余3；总人数除以7余4.算法的第一步是将所有的除以3余2的正整数找出来，按从小到大排成一列.第二步是从第一步的数列中找出除以5余3的一列数，按从小到大排成一列.最后在满足前两个条件的第二步数列中再找出除以7余4的一列数，这列数中最小的数，即为我们所求的数.（1）首先确定最小的满足除以3余2的正整数：2.解：具体算法步骤如下：（5）在第4步得到的一列数中，找出满足除以7余4的最小数：53.这就

7、是我们要求的数.（4）然后依次加上15，得到8，23，38，53……，显然这些数既满足除以3余2，又满足除以5余3.（3）在上列数中确定最小的满足除以5余3的正整数：8.（2）依次加3就得到所有除以3余2的正整数：2，5，8，11，14，17，20，23，26，29，32，35，38，41，44，47，50，53，56……3、算法要简洁，要清晰可读，不能繁杂，易程序化.算法不同于求解一个具体问题的方法，是这种方法的高度概括.一个好的算法有如下要求：1、写出的算法，必须能解决一类问