数学优化训练：算法的基本思想

学必求其心得，业必贵于专精学必求其心得，业必贵于专精学必求其心得，业必贵于专精第二章算法初步§1算法的基本思想1。1算法案例分析1。2排序问题与算法的多样性5分钟训练（预习类训练，可用于课前）1.以下对算法的描述中，正确的有(）①对一类问题都有效②对个别问题有效③计算可以一步步地进行,每一步都有唯一的结果④是一种通法，只要按部就班地做，总能得到结果A.1个B。2个C.3个D。4个答案:C解析:算法通常是指按照某种机械程序步骤，一定可以得到结果的解决问题的程序或步骤,算法往往是为了解决一类问题而编制的,其中①③④是对的.2.使用计算机解题的步骤，以下描述正确的是（）A。正确理解题意→设计正确算法→寻找解题方法→编写程序→调试运行B.寻找解题方法→正确理解题意→设计正确算法→编写程序→调试运行C.正确理解题意→寻找解题方法→设计正确算法→编写程序→调试运行D。寻找解题方法→设计正确算法→正确理解题意→编写程序→调试运行答案：C3.480和900的最大公因数是()A.60B。12C.48答案:A解析：∵480的素因数分解为480=25×3×5,900的素因数分解为900=22×32×52，其公共素因数2，3，5的指数分别为2，1,1，∴最大公因数为22×31×51=60.4.已知一个学生的语文成绩为98,数学成绩为87，外语成绩为92，以下是他的总分和平均成绩的一个算法：（在横线上填入算法中缺的两个步骤）1。取A=98，B=87,C=92;2。____________________；3。____________________；4.输出计算的结果。答案：计算总分D=A+B+C计算平均成绩E=解析：两步分别是求总分和平均成绩的两步，此算法通过输入任意分数，便可输出总分和平均分。5.已知一组有序列：｛10，12,45，78，96，100，156，189，200}，现在要将100这个数插入这组数中，但要保持原有的从小到大的排列顺序。用“直接插入排序法”插入时，100要插到___________个位置，插入时要进行___________次比较。答案:第七四解析:用“直接插入排序法”插入时，进行比较是从最后一个开始，一直向前,直到要插入的数大于等于某个数为止，然后插到这个数之后。10分钟训练（强化类训练，可用于课中）1。以下关于算法的几种说法，其中正确的是(）A.算法就是某一个问题的解题方法B.对于给定的一个问题，其算法不一定是唯一的C。一个算法可以不产生确定的结果D。算法的步骤可以无限地执行下去，不停止答案:B解析:算法是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确的和有效的,而且能够在有限步之内完成的，但是解决某一类问题的算法未必唯一.因此B项正确.2.早上从起床到出门需要洗脸刷牙（5min）、刷水壶（2min）、烧水（8min）、泡面（3min)、吃饭(10min）、听广播（8min）几个步骤，下列选项中最好的一种算法是（)A。1.洗脸刷牙、2。刷水壶、3.烧水、4。泡面、5.吃饭、6。听广播B.1.刷水壶、2。烧水同时洗脸刷牙、3.泡面、4.吃饭、5。听广播C。1。刷水壶、2.烧水的同时洗脸刷牙、3.泡面、4.吃饭同时听广播D.1.吃饭同时听广播、2。泡面、3。烧水同时洗脸刷牙、4。刷水壶答案：C3。有一堆形状、大小相同的珠子，其中只有一粒重量比其他的轻.某同学利用科学算法，最多两次利用天平找出了这颗最轻的珠子，则这堆珠子最多的粒数是（)A。4B.5C。6答案：D解析：最多是7粒,第一次是天平每边3粒，若平衡，则剩余的为所求；若不平衡，则在轻的一边选出两粒,再放在天平的两边，这样就可以得到最轻的珠子.4。把1800写成素因数的积为（）A.1800=2×9×100B。1800=2×3×5×60C。1800=23×32×52D。都不对答案：C解析：素因数必须是不能再分解的整数，显然9、100、60都不是素数，而2、3、5是不能再分解的整数.5。写出“解方程ax+b=0(a≠0)”的一个算法的过程，1。将不含x的常数项移到方程右边，并改变常数项的符号，2._________________.答案：方程两边同除以a6。写出将70用“折半插入排序法”插入有序列｛4,20，28,45,73，99}中的一个算法。解：其算法步骤如下:1.设a1=4,a2=20,a3=28，a4=45,a5=73，a6=99；2.将70与a3比较，∵70＞a3=28，∴70应该插在其右侧；3.将70与a5比较，∵70＜a5=73，∴70应该插在其左侧；4.将70与a4比较，∵70＞a4=45，∴70应该插在其右侧；5。将70插在a4与a5中间，得到一个新的有序列{4,20,28，45，70，73,99}.30分钟训练(巩固类训练，可用于课后）1。下列对算法的理解不正确的是（)A.算法有一个共同特点就是对一类问题都有效(而不是个别问题）B。算法要求必须在有穷步内结束C.算法一般是机械的，有时要进行大量重复的计算，它的优点是一种通法D。任何问题都可以用算法来解决答案：D2。下列结果中,叙述不正确的是（）A.算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤B.算法可以看成按要求设计好的有限的确切的计算序列，并且这样的步骤或序列能够解决一类问题C.算法只是在计算机产生之后才有的D。描述算法有不同的方式，可以用日常语言和数学语言答案：C解析：A、B两个选项正确地说明了算法的形式和功能,正确.算法的描述，可以采用日常语言和数学语言的形式,也可以采用程序设计语言和伪代码等形式,D项正确.算法在很早的时候就产生了，我们在小学、中学学到的方程求解、不定式的求解、作图方法等都是算法，它们很早就由数学家提出来了。而计算机的产生只是最近五六十年的事情。但由于计算机强大的计算功能，我们如果能将算法转换成计算机所能识别的语言,就能借助计算机极大地提高解决问题的速度。3。写出8840和21658的最大公因数(）A.26B。442C。34答案:B解析：8840=23×5×13×17，21658=2×72×13×17,因此8840与21658的最大公因数为2×13×17=442。4。写出360与512的最小公倍数（）A.1024B.142C。23040答案：C解析：求两个数的最小公倍数,先用这两个数公有的质因数连续去除（一般从最小的开始），一直除到所得的商是互质数为止，然后把所有的除数和最后的两个商连乘起来.360=23×32×5，512=29，因此360与512的最小公倍数为29×32×5=23040。5.在一个长度为n的顺序表中,在第i个元素（1≤i≤n+1）之前插入一个新元素时需向后移动的元素个数是()A。n—iB.n-i+1C。n—i-1答案：B解析：第i个元素前插入一个新元素,则从第i个元素到第n个元素都要往后移动一个单位，所以，移动的元素个数是n-i+1个。6。已知一组有序列：{8,12，56，78,96，100，111,156，189，201},现在要将一个数插入这组数中，但要保持原有的从小到大的排列顺序.用“直接插入排序法”插入时,最少比较_________次，最多比较_________次.如果已知序列有n个数，结果是____________________。答案:110最少1次，最多n次解析:比较次数最少时，就是插入的数是最大的一个数;比较次数最多时,就是这个数为最小的一个数.7。840、936和1764这三个数的最大公因数是_________.答案：12解析：因为840，936和1764这三个数可以分解为840=23×3×5×7，936=23×32×13，1764=22×32×72，所以这三个数的最大公因数为22×3=12。8.写出判断直线Ax+By+C=0（A、B不能同时为零）和圆(x—x0）2+(y—y0)2=r2位置关系的算法。解:判断直线与圆的位置关系，其算法步骤如下：1.输入圆心的坐标(x0,y0），直线方程的系数A、B、C和半径r;2。计算d=；3。如果d＞r则相离，如果d=r则相切,如果d＜r则相交.9。在一堂物理课上，老师要求学生只用50g和5g两个砝码以及天平将现有495g食盐平均分成三份.现在请你为他们设计一个算法，使称量的次数最少.试问需称量多少次。解：算法如下:1.先计算出：495g食盐如果平均分成三份，每一份应该是165g；2。165g中有3个5g和3个50g；3。用5g砝码称出5g食盐；4.用5g砝码和5g食盐共同称出10g食盐;5.再用50g砝码称出50g食盐；6。用50g砝码和50g食盐共同称出100g食盐；7.把5g、10g、50g、100g食盐混合,构成165g食盐,也就是一份的质量;8.用这一份食盐再称出165g。此时全部食盐被平均分成三份，按照以上算法共需要称量5次.10.用二分法设计一个求方程x2—2=0的近似根的算法.（精度为0。005）解：其算法步骤如下：1。令f(x）=x2-2。∵f（1)=—1＜0,f（2）=2＞0,∴取初始区间为［1,2］，精度2-1=1＞0.005;2。取[1，2]的区间中点为1。5；3。计算f(1.5）=0.25；4.由于f(1。5)·f(1）＜0,可得新的有解区间为[1，1.5］，精度1。5-1=0.5＞0.005；5。取［1，1.5]的区间中点1.25;6.计算f(1。25