數(shù)學(xué)三同步訓(xùn)練：算法的基本思想（附答案）

學(xué)必求其心得，業(yè)必貴于專精學(xué)必求其心得，業(yè)必貴于專精學(xué)必求其心得，業(yè)必貴于專精第二章算法初步§1算法的基本思想1．以下對算法的描述中，正確的有()①對一類問題都有效②對個別問題有效③計(jì)算可以一步步地進(jìn)行，每一步都有唯一的結(jié)果④是一種通法，只要按部就班地做,總能得到結(jié)果A．1個B．2個C．3個D．4個2．使用計(jì)算機(jī)解題的步驟，以下描述正確的是(）A．正確理解題意→設(shè)計(jì)正確算法→尋找解題方法→編寫程序→調(diào)試運(yùn)行B．尋找解題方法→正確理解題意→設(shè)計(jì)正確算法→編寫程序→調(diào)試運(yùn)行C．正確理解題意→尋找解題方法→設(shè)計(jì)正確算法→編寫程序→調(diào)試運(yùn)行D．尋找解題方法→設(shè)計(jì)正確算法→正確理解題意→編寫程序→調(diào)試運(yùn)行3．480和900的最大公因數(shù)是（）A．60B．12C．48D．1204．已知一組有序列：{10，12，45，78，96，100,156,189，200｝，現(xiàn)在要將100這個數(shù)插入這組數(shù)中，但要保持原有的從小到大的排列順序．用“直接插入排序法”插入時，100要插到________個位置，插入時要進(jìn)行________次比較．5．已知A(x1，y1)、B（x2，y2）,寫出求直線AB斜率的一個算法．答案：1．C算法通常是指按照某種機(jī)械程序步驟,一定可以得到結(jié)果的解決問題的程序或步驟，算法往往是為了解決一類問題而編制的,其中①③④是對的．2．C3．A∵480的素因數(shù)分解為480＝25×3×5，900的素因數(shù)分解為900＝22×32×52，其公共素因數(shù)2，3，5的指數(shù)分別為2,1,1,∴最大公因數(shù)為22×31×51＝60.4．第七四用“直接插入排序法”插入時，進(jìn)行比較是從最后一個開始，一直向前,直到要插入的數(shù)大于等于某個數(shù)為止,然后插到這個數(shù)之后，即100之后．5．解：1。輸入兩點(diǎn)坐標(biāo)x1，y1，x2,y2.2．計(jì)算Δx＝x2－x1，Δy＝y(tǒng)2－y1。3．如果Δx＝0，則判定“斜率k不存在”．4．如果Δx≠0，計(jì)算k＝eq\f（Δy,Δx）。5．輸出斜率k.1．下列對算法的理解不正確的是(）A．算法有一個共同特點(diǎn)就是對一類問題都有效（而不是個別問題)B．算法要求必須在有窮步內(nèi)結(jié)束C．算法一般是機(jī)械的，有時要進(jìn)行大量重復(fù)的計(jì)算,它的優(yōu)點(diǎn)是一種通法D．任何問題都可以用算法來解決2．把1800寫成素因數(shù)的積為（)A．1800＝2×9×100B．1800＝2×3×5×60C．1800＝23×32×52D．都不對3．有一堆形狀、大小相同的珠子，其中只有一粒重量比其他的輕．某同學(xué)利用科學(xué)算法，最多兩次利用天平找出了這顆最輕的珠子，則這堆珠子最多的粒數(shù)是()A．4B．5C．6D．74．寫出“解方程：ax＋b＝0（a≠0)”的一個算法的過程：1.將不含x的常數(shù)項(xiàng)移到方程右邊，并改變常數(shù)項(xiàng)的符號.2。__________.5．寫出判斷直線Ax＋By＋C＝0（A、B不能同時為零）和圓（x－x0)2＋（y－y0)2＝r2位置關(guān)系的算法．6．寫出將70用“折半插入排序法"插入有序列｛4,20，28,45，73,99}中的一個算法．答案：1．D2．C素因數(shù)必須是不能再分解的整數(shù)，顯然9、100、60都不是素?cái)?shù)，而2、3、5是不能再分解的整數(shù)．3．D最多是7粒，第一次是天平每邊3粒，若平衡,則余下的一粒為所求;若不平衡，則在輕的一邊選出兩粒,再放在天平的兩邊，若平衡，則余下的一粒為所求；若不平衡，則輕的一邊為所求．這樣即可得到最輕的珠子．4．方程兩邊同除以a5．解：判斷直線與圓的位置關(guān)系,其算法步驟如下:1．輸入圓心的坐標(biāo)（x0，y0），半徑r及直線方程的系數(shù)A、B、C.2．計(jì)算d＝eq\f(｜Ax0＋By0＋C｜,\r（A2＋B2））。3．如果d＞r則相離;如果d＝r則相切;如果d＜r則相交．6．解:其算法步驟如下:1．設(shè)a1＝4，a2＝20，a3＝28,a4＝45，a5＝73，a6＝99;2．將70與a3比較，∵70＞a3＝28，∴70應(yīng)該插在其右側(cè);3．將70與a5比較，∵70＜a5＝73,∴70應(yīng)該插在其左側(cè)；4．將70與a4比較,∵70＞a4＝45,∴70應(yīng)該插在其右側(cè)；5．將70插在a4與a5中間，得到一個新的有序列｛4，20，28，45,70,73，99}．1．下列結(jié)果中,敘述不正確的是()A．算法可以理解為由基本運(yùn)算及規(guī)定的運(yùn)算順序構(gòu)成的完整的解題步驟B．算法可以看成按要求設(shè)計(jì)好的有限的確切的計(jì)算序列,并且這樣的步驟或序列能夠解決一類問題C.算法只是在計(jì)算機(jī)產(chǎn)生之后才有的D．描述算法有不同的方式,可以用日常語言和數(shù)學(xué)語言答案：CA、B兩個選項(xiàng)正確地說明了算法的形式和功能，正確；算法的描述,可以采用日常語言和數(shù)學(xué)語言的形式，也可以采用程序設(shè)計(jì)語言形式，D項(xiàng)正確．算法在很早的時候就產(chǎn)生了，我們在小學(xué)、中學(xué)學(xué)到的方程求解、不定式的求解、作圖方法等都是算法,它們很早就由數(shù)學(xué)家提出來了，而計(jì)算機(jī)的產(chǎn)生只是最近五六十年的事情．但由于計(jì)算機(jī)強(qiáng)大的計(jì)算功能，我們?nèi)绻軐⑺惴ㄞD(zhuǎn)換成計(jì)算機(jī)所能識別的語言，就能借助計(jì)算機(jī)極大地提高解決問題的速度．2．寫出8840和21658的最大公因數(shù)(）A．26B．442C．34D．221答案:B8840＝23×5×13×17，21658＝2×72×13×17，∴8840與21658的最大公因數(shù)為2×13×17＝442。3．寫出360與512的最小公倍數(shù)（）A．1024B．142C．23040D．568答案：C360＝23×32×5,512＝29，∴360與512的最小公倍數(shù)為29×32×5＝23040。4．在一個長度為n的順序表中，在第i個元素(1≤i≤n＋1)之前插入一個新元素時需向后移動的元素個數(shù)是（)A．n－iB．n－i＋1C．n－i－1D．i答案：B第i個元素前插入一個新元素，則從第i個元素到第n個元素都要往后移動一個單位，所以，移動的元素個數(shù)是n－i＋1個．5．(易錯題)下列關(guān)于算法的說法中，正確的是(）A．算法是關(guān)于某個問題的解題過程B．算法執(zhí)行后可以產(chǎn)生不確定的結(jié)果C．解決某類問題的算法不是唯一的D．算法可以無限地操作下去不停止答案：C算法可以解決一類問題，且不唯一；同時必須通過有限步得出正確結(jié)果．∴C正確．點(diǎn)評:(1）對于算法，通常有以下幾個特性:①概括性:寫出的算法必須能解決一類問題并且能重復(fù)使用;②有窮性：算法中執(zhí)行的步驟總是有限次數(shù)的，不能無休止地執(zhí)行下去；③確定性：算法中的每一步操作的內(nèi)容和順序必須含義確切；④可行性：算法中的每一步都必須可執(zhí)行,也就是說算法中的每一步操作都能通過手工和機(jī)器在有限的時間內(nèi)完成，這稱之為有效性;⑤輸入和輸出：一個算法中有零個或多個輸入，有一個或多個輸出．(2）對此類問題，只有理解算法的特性與基本思想，才能判斷準(zhǔn)確，選擇恰當(dāng)，否則很容易錯解．6．對于算法：第一步輸入n；第二步判斷n是否等于2，若n＝2，則n滿足條件；若n＞2，則執(zhí)行第三步；第三步依次從2到n－1檢驗(yàn)?zāi)懿荒苷齨，若不能整除n，則執(zhí)行第四步；若能整除n,則執(zhí)行第一步;第四步輸出n.滿足條件的n是（）A．質(zhì)數(shù)B．奇數(shù)C．偶數(shù)D．約數(shù)答案：A這個算法通過對2到n－1逐個驗(yàn)證，看是否有其他的約數(shù),依次來判斷其是否為質(zhì)數(shù)．7．252，420,936這三個數(shù)的最大公因數(shù)是______．答案：12∵252，420和936這三個數(shù)可以分解為252＝22×32×7，420＝22×3×5×7,936＝23×32×23，∴這三個數(shù)的最大公因數(shù)為22×3＝12。8．已知一組有序列:{8,12，56，78，96,100，111，156,189,201}，現(xiàn)在要將一個數(shù)插入這組數(shù)中,但要保持原有的從小到大的排列順序．用“直接插入排序法”插入時，最少比較________次，最多比較________次．如果已知序列有n個數(shù)，結(jié)果是__________________．答案:110最少1次，最多n次比較次數(shù)最少時,就是插入的數(shù)是最大的一個數(shù)；比較次數(shù)最多時，就是這個數(shù)為最小的一個數(shù)．9．2008年5月12日在四川汶川發(fā)生特大地震，損失慘重，某學(xué)校學(xué)生會舉辦了為地震災(zāi)區(qū)捐款的活動，各同學(xué)踴躍捐款，并把捐款數(shù)額輸入電腦．現(xiàn)有一電視臺記者要在全校找一個捐款最多的學(xué)生作為典型進(jìn)行采訪，如何設(shè)計(jì)一個算法？解：1.先假定序列中的第一個數(shù)為“最大值”；2．將序列中的下一個數(shù)值與“最大值”比較，如果它大于此“最大值"，這時就假定“最大值”是這個數(shù)；3．重復(fù)第2步；4．在序列中一直到?jīng)]有可比的數(shù)為止,這時假定的“最大值”就是這次捐款的最大值10．(原創(chuàng)題)已知樣本數(shù)據(jù)為a1，a2，a3，…,an,試寫出一個求其標(biāo)準(zhǔn)差的算法．解：1.輸入數(shù)據(jù)x1＝a1，x2＝a2，…，xn＝an；2．計(jì)算eq\x\to(x)＝eq\f（x1＋x2＋…＋xn,n);3．計(jì)算S2＝eq\f(1,n）[（x1－eq\x\to(x))2＋（x2－eq\x\to(x））2＋…＋（xn－eq\x\to（x)）2］;4．計(jì)算S＝eq\r(S2)；5．輸出S.11．在一堂物理課上,老師要求學(xué)生只用50g和5g兩個砝碼以及天平將現(xiàn)有495g食鹽平均分成三份．現(xiàn)在請你為他們設(shè)計(jì)一個算法,使稱量的次數(shù)最少，試問需稱量多少次?解:算法如下：1．先計(jì)算出：495g食鹽如果平均分成三份，每一份應(yīng)該是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食鹽混合,構(gòu)成165g食鹽，也就是一份的質(zhì)量;8．用這一份食鹽再稱出165g.此時全部食鹽被平均分成三份,按照以上算法共需要稱量5次．12．用二分法設(shè)計(jì)一個求方程x2－2＝0在區(qū)間［1,2］上的近似根的算法（精度為0.005）．解:其算法步驟如下：1．令f(x）＝x2－2。f（1)＝－1＜0，f（2）＝2＞0,精度2－1＝1＞0。005；2．?。?,2]的區(qū)間中點(diǎn)為1.5;3．計(jì)算f(1。5)＝0。25；4．由于f(1。5）·f(1）＜0,可得新的有解區(qū)間為［1,1.5]，精度1。5－1＝0。5＞0。005；5．?。?,1。5]的區(qū)間中點(diǎn)1.25；6．計(jì)算f（1