高中算法初步

./109004算法初步[考綱要求]1．了解算法的含義,了解算法的思想．2．理解算法框圖的三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)．[把脈考情]從近兩年的高考試題來(lái)看,循環(huán)結(jié)構(gòu)與條件結(jié)構(gòu)是考查的熱點(diǎn),題型以選擇、填空題為主,屬容易題．本節(jié)內(nèi)容常考的類型有：功能判斷型、結(jié)果輸出型、判斷條件型,同時(shí)注意算法思想的應(yīng)用,預(yù)測(cè)2012年仍為考查的熱點(diǎn)．[要點(diǎn)梳理]一、算法的概念1．算法的定義：是指按照一定規(guī)則解決某一類問(wèn)題的明確和有限的步驟．2．算法的特征:<1>概括性：寫出的算法必須能解決某一類問(wèn)題,并且能夠重復(fù)使用．<2>邏輯性：算法從初始步驟開(kāi)始,分為若干明確的步驟,前一步是后一步的前提,只有執(zhí)行完前一步才能進(jìn)行下一步,而且每一步都是正確無(wú)誤的,從而組成了一個(gè)有著很強(qiáng)邏輯性的步驟序列．<3>有窮性：算法有一個(gè)清晰的起始步,終止步是表示問(wèn)題得到解答或指出問(wèn)題沒(méi)有解答,所有序列必須在有限個(gè)步驟之內(nèi)完成,不能無(wú)停止地執(zhí)行下去．<4>不唯一性：求解某一個(gè)問(wèn)題的算法不一定只有唯一的一個(gè),可以有不同的算法,當(dāng)然這些算法有簡(jiǎn)繁之分、優(yōu)劣之別．<5>普遍性：很多具體的問(wèn)題,都可以設(shè)計(jì)合理的算法去解決．二、程序框圖1．程序框圖基本概念：〔一程序構(gòu)圖的概念：程序框圖又稱流程圖,是一種用規(guī)定的圖形、指向線及文字說(shuō)明來(lái)準(zhǔn)確、直觀地表示算法的圖形。一個(gè)程序框圖包括以下幾部分：表示相應(yīng)操作的程序框；帶箭頭的流程線；程序框外必要文字說(shuō)明?！捕?gòu)成程序框的圖形符號(hào)及其作用程序框名稱功能終端框〔起止框表示一個(gè)算法的起始和結(jié)束,是任何流程圖不可少的。輸入、輸出框表示一個(gè)算法輸入和輸出的信息,可用在算法中任何需要輸入、輸出的位置。處理框〔執(zhí)行框賦值、計(jì)算,算法中處理數(shù)據(jù)需要的算式、公式等分別寫在不同的用以處理數(shù)據(jù)的處理框內(nèi)。判斷框判斷某一條件是否成立,成立時(shí)在出口處標(biāo)明"是"或"Y"；不成立時(shí)標(biāo)明"否"或"N"。流程線連接程序框,Ο連接點(diǎn)連接程序框圖的兩部分學(xué)習(xí)這部分知識(shí)的時(shí)候,要掌握各個(gè)圖形的形狀、作用及使用規(guī)則,畫程序框圖的規(guī)則如下：〔1使用標(biāo)準(zhǔn)的圖形符號(hào)?！?框圖一般按從上到下、從左到右的方向畫?！?除判斷框外,大多數(shù)流程圖符號(hào)只有一個(gè)進(jìn)入點(diǎn)和一個(gè)退出點(diǎn)。判斷框具有超過(guò)一個(gè)退出點(diǎn)的唯一符號(hào)。〔4判斷框分兩大類,一類判斷框"是"與"否"兩分支的判斷,而且有且僅有兩個(gè)結(jié)果；另一類是多分支判斷,有幾種不同的結(jié)果?！?在圖形符號(hào)內(nèi)描述的語(yǔ)言要非常簡(jiǎn)練清楚。〔三算法的三種基本邏輯結(jié)構(gòu)：順序結(jié)構(gòu)、條件結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。AB〔1順序結(jié)構(gòu)：順序結(jié)構(gòu)是最簡(jiǎn)單的算法結(jié)構(gòu),語(yǔ)句與語(yǔ)句之間,框與框之間是按從上到下的順序進(jìn)行的,它是由若干個(gè)依次執(zhí)行AB順序結(jié)構(gòu)在程序框圖中的體現(xiàn)就是用流程線將程序框自上而下地連接起來(lái),按順序執(zhí)行算法步驟。如在示意圖中,A框和B框是依次執(zhí)行的,只有在執(zhí)行完A框指定的操作后,才能接著執(zhí)行B框所指定的操作。〔2條件結(jié)構(gòu)：條件結(jié)構(gòu)是指在算法中通過(guò)對(duì)條件的判斷根據(jù)條件是否成立而選擇不同流向的算法結(jié)構(gòu)。條件P是否成立而選擇執(zhí)行A框或B框。無(wú)論P(yáng)條件是否成立,只能執(zhí)行A框或B框之一,不可能同時(shí)執(zhí)行A框和B框,也不可能A框、B框都不執(zhí)行。一個(gè)判斷結(jié)構(gòu)可以有多個(gè)判斷框。條件結(jié)構(gòu)的典型問(wèn)題就是分段函數(shù)的求值問(wèn)題及有關(guān)分類的其他問(wèn)題．在程序框圖設(shè)計(jì)中,程序的流向要多次根據(jù)判斷做出選擇時(shí),一般要用到條件結(jié)構(gòu)的"嵌套"．所謂條件結(jié)構(gòu)的"嵌套",就是在條件結(jié)構(gòu)的一支<或兩支>內(nèi)的步驟中又要用到條件結(jié)構(gòu)．這類問(wèn)題一般比較復(fù)雜,設(shè)計(jì)時(shí)要注意每一個(gè)處理框執(zhí)行時(shí)對(duì)應(yīng)的條件．〔3循環(huán)結(jié)構(gòu)：在一些算法中,經(jīng)常會(huì)出現(xiàn)從某處開(kāi)始,按照一定條件,反復(fù)執(zhí)行某一處理步驟的情況,這就是循環(huán)結(jié)構(gòu),反復(fù)執(zhí)行的處理步驟為循環(huán)體,顯然,循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu)。循環(huán)結(jié)構(gòu)又稱重復(fù)結(jié)構(gòu),循環(huán)結(jié)構(gòu)可細(xì)分為兩類：①一類是當(dāng)型循環(huán)結(jié)構(gòu),如下左圖所示,它的功能是當(dāng)給定的條件P成立時(shí),執(zhí)行A框,A框執(zhí)行完畢后,再判斷條件P是否成立,如果仍然成立,再執(zhí)行A框,如此反復(fù)執(zhí)行A框,直到某一次條件P不成立為止,此時(shí)不再執(zhí)行A框,離開(kāi)循環(huán)結(jié)構(gòu)。不成立P不成立P成立AAA成立不成立P當(dāng)型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)注意：1循環(huán)結(jié)構(gòu)要在某個(gè)條件下終止循環(huán),這就需要條件結(jié)構(gòu)來(lái)判斷。因此,循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu),但不允許"死循環(huán)"。2在循環(huán)結(jié)構(gòu)中都有一個(gè)計(jì)數(shù)變量和累加變量。計(jì)數(shù)變量用于記錄循環(huán)次數(shù),累加變量用于輸出結(jié)果。計(jì)數(shù)變量和累加變量一般是同步執(zhí)行的,累加一次,計(jì)數(shù)一次。順序結(jié)構(gòu)條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)定義由若干個(gè)依次執(zhí)行的步驟組成的,這是任何一個(gè)算法都離不開(kāi)的基本結(jié)構(gòu)算法的流程根據(jù)條件是否成立有不同的流向,條件結(jié)構(gòu)就是處理這種過(guò)程的結(jié)構(gòu)從某處開(kāi)始,按照一定的條件反復(fù)執(zhí)行某些步驟的情況,反復(fù)執(zhí)行的步驟稱為循環(huán)體程序框圖直到型當(dāng)型[究疑點(diǎn)]三種基本邏輯結(jié)構(gòu)的共同點(diǎn)是什么？提示：三種邏輯結(jié)構(gòu)的共同點(diǎn)即只有一個(gè)入口和一個(gè)出口,每一個(gè)基本邏輯結(jié)構(gòu)的每一部分都有機(jī)會(huì)被執(zhí)行到,而且結(jié)構(gòu)內(nèi)不存在死循環(huán)．三、程序語(yǔ)言1．輸入語(yǔ)句〔1輸入語(yǔ)句的一般格式：eq\x<Input"提示內(nèi)容"；變量>.〔2輸入語(yǔ)句與程序框圖中的輸入框?qū)?yīng),作用是實(shí)現(xiàn)算法的輸入信息功能；〔3"提示內(nèi)容"提示用戶輸入什么樣的信息,變量是指程序在運(yùn)行時(shí)其值是可以變化的量；〔4輸入語(yǔ)句要求輸入的值只能是具體的常數(shù),不能是函數(shù)、變量或表達(dá)式；〔5提示內(nèi)容與變量之間用分號(hào)"；"隔開(kāi),若輸入多個(gè)變量,變量與變量之間用逗號(hào)","隔開(kāi)。2．輸出語(yǔ)句〔1輸出語(yǔ)句的一般格式：eq\x<Print"提示內(nèi)容"；表達(dá)式>.〔2輸出語(yǔ)句的作用是實(shí)現(xiàn)算法的輸出結(jié)果功能；〔3"提示內(nèi)容"提示用戶輸入什么樣的信息,表達(dá)式是指程序要輸出的數(shù)據(jù)；〔4輸出語(yǔ)句可以輸出常量、變量或表達(dá)式的值以及字符。3．賦值語(yǔ)句〔1賦值語(yǔ)句的一般格式：eq\x<變量＝表達(dá)式>〔2賦值語(yǔ)句的作用是將表達(dá)式所代表的值賦給變量；〔3賦值語(yǔ)句中的"＝"稱作賦值號(hào),與數(shù)學(xué)中的等號(hào)的意義是不同的。賦值號(hào)的左右兩邊不能對(duì)換,它將賦值號(hào)右邊的表達(dá)式的值賦給賦值號(hào)左邊的變量；〔4賦值語(yǔ)句左邊只能是變量名字,而不是表達(dá)式,右邊表達(dá)式可以是一個(gè)數(shù)據(jù)、常量或算式；〔5對(duì)于一個(gè)變量可以多次賦值。注意：①賦值號(hào)左邊只能是變量名字,而不能是表達(dá)式。如：2=X是錯(cuò)誤的。②賦值號(hào)左右不能對(duì)換。如"A=B""B=A"的含義運(yùn)行結(jié)果是不同的。③不能利用賦值語(yǔ)句進(jìn)行代數(shù)式的演算?！踩缁?jiǎn)、因式分解、解方程等④賦值號(hào)"="與數(shù)學(xué)中的等號(hào)意義不同。4．條件語(yǔ)句〔1條件語(yǔ)句的一般格式有兩種：①IF—THEN—ELSE語(yǔ)句；②IF—THEN語(yǔ)句?！?IF—THEN—ELSE語(yǔ)句IF—THEN—ELSE語(yǔ)句的一般格式為圖1,對(duì)應(yīng)的程序框圖為圖2。否是否是滿足條件？語(yǔ)句1語(yǔ)句2IF條件THEN語(yǔ)句1ELSE語(yǔ)句2ENDIF圖1圖2分析：在IF—THEN—ELSE語(yǔ)句中,"條件"表示判斷的條件,"語(yǔ)句1"表示滿足條件時(shí)執(zhí)行的操作內(nèi)容；"語(yǔ)句2"表示不滿足條件時(shí)執(zhí)行的操作內(nèi)容；ENDIF表示條件語(yǔ)句的結(jié)束。計(jì)算機(jī)在執(zhí)行時(shí),首先對(duì)IF后的條件進(jìn)行判斷,如果條件符合,則執(zhí)行THEN后面的語(yǔ)句1；若條件不符合,則執(zhí)行ELSE后面的語(yǔ)句2?！?IF—THEN語(yǔ)句滿足條件？語(yǔ)句滿足條件？語(yǔ)句是否〔圖4IFIF條件THEN語(yǔ)句ENDIF〔圖3補(bǔ)充：條件語(yǔ)句嵌套的形式在有些復(fù)雜的算法中,有時(shí)需要按條件執(zhí)行的某一語(yǔ)句繼續(xù)按照另一個(gè)要求進(jìn)行判斷,這時(shí)可以再利用一個(gè)條件語(yǔ)句進(jìn)行判斷,這就形成了條件語(yǔ)句的嵌套．<1>一般形式：<2>在編寫條件語(yǔ)句的嵌套中的"條件"時(shí),要注意"If"與"EndIf"的配對(duì),有時(shí)可以利用文字的縮進(jìn)來(lái)表示嵌套的層次,以幫助對(duì)程序的閱讀和理解．<3>對(duì)于條件語(yǔ)句的嵌套,一定要分清內(nèi)層條件語(yǔ)句和外層條件語(yǔ)句,內(nèi)層的條件結(jié)構(gòu)是外層的條件結(jié)構(gòu)的一個(gè)分支．<4>當(dāng)條件結(jié)構(gòu)的嵌套中的"條件"是并列的,則為條件語(yǔ)句的疊加．5．循環(huán)語(yǔ)句循環(huán)結(jié)構(gòu)是由循環(huán)語(yǔ)句來(lái)實(shí)現(xiàn)的。對(duì)應(yīng)于程序框圖中的兩種循環(huán)結(jié)構(gòu),一般程序設(shè)計(jì)語(yǔ)言中也有當(dāng)型〔WHILE型和直到型〔UNTIL型兩種語(yǔ)句結(jié)構(gòu)。即WHILE語(yǔ)句和UNTIL語(yǔ)句?！?WHILE語(yǔ)句滿足條件？循環(huán)體滿足條件？循環(huán)體否是WHILE條件WHILE條件循環(huán)體WEND②當(dāng)計(jì)算機(jī)遇到WHILE語(yǔ)句時(shí),先判斷條件的真假,如果條件符合,就執(zhí)行WHILE與WEND之間的循環(huán)體；然后再檢查上述條件,如果條件仍符合,再次執(zhí)行循環(huán)體,這個(gè)過(guò)程反復(fù)進(jìn)行,直到某一次條件不符合為止。這時(shí),計(jì)算機(jī)將不執(zhí)行循環(huán)體,直接跳到WEND語(yǔ)句后,接著執(zhí)行WEND之后的語(yǔ)句。因此,當(dāng)型循環(huán)有時(shí)也稱為"前測(cè)試型"循環(huán)?！?UNTIL語(yǔ)句滿足條件？循環(huán)體滿足條件？循環(huán)體是否DODO循環(huán)體LOOPUNTIL條件②直到型循環(huán)又稱為"后測(cè)試型"循環(huán),從UNTIL型循環(huán)結(jié)構(gòu)分析,計(jì)算機(jī)執(zhí)行該語(yǔ)句時(shí),先執(zhí)行一次循環(huán)體,然后進(jìn)行條件的判斷,如果條件不滿足,繼續(xù)返回執(zhí)行循環(huán)體,然后再進(jìn)行條件的判斷,這個(gè)過(guò)程反復(fù)進(jìn)行,直到某一次條件滿足時(shí),不再執(zhí)行循環(huán)體,跳到LOOPUNTIL語(yǔ)句后執(zhí)行其他語(yǔ)句,是先執(zhí)行循環(huán)體后進(jìn)行條件判斷的循環(huán)語(yǔ)句。分析：當(dāng)型循環(huán)與直到型循環(huán)的區(qū)別與聯(lián)系：<1>聯(lián)系：兩種語(yǔ)句都可以實(shí)現(xiàn)計(jì)算機(jī)反復(fù)執(zhí)行循環(huán)體的目的,只是表達(dá)形式不同；一般來(lái)講,While語(yǔ)句與Until語(yǔ)句可以相互轉(zhuǎn)化．<2>區(qū)別：①計(jì)算機(jī)執(zhí)行的順序不同：While先條件,Until先循環(huán)．②條件的內(nèi)容不同：While滿足就循環(huán),Until滿足就停止．③對(duì)循環(huán)體的執(zhí)行次數(shù)不同：在While語(yǔ)句中,循環(huán)體可以一次不執(zhí)行就退出循環(huán)結(jié)構(gòu)；而在任何Until語(yǔ)句中,循環(huán)體至少要執(zhí)行一次．應(yīng)用循環(huán)語(yǔ)句編寫程序應(yīng)注意的幾個(gè)問(wèn)題：<1>循環(huán)語(yǔ)句中的變量,一般需要進(jìn)行一定的初始化操作．<2>循環(huán)語(yǔ)句在循環(huán)的過(guò)程中需要有"結(jié)束"的語(yǔ)句,程序中最忌"死循環(huán)",所謂"死循環(huán)"就是指該循環(huán)條件永遠(yuǎn)成立,沒(méi)有跳出循環(huán)體的機(jī)會(huì)．<3>在循環(huán)中要改變循環(huán)體條件的成立因素．程序每執(zhí)行一次循環(huán)體,循環(huán)條件中涉及的變量就會(huì)發(fā)生改變,正在步步逼近滿足跳出循環(huán)體的條件循環(huán)結(jié)構(gòu)中幾個(gè)常用變量：<1>計(jì)數(shù)變量：用來(lái)記錄某個(gè)事件發(fā)生的次數(shù),如i＝i＋1；<2>累加變量：用來(lái)計(jì)算數(shù)據(jù)之和,如s＝s＋i；<3>累乘變量：用來(lái)計(jì)算數(shù)據(jù)之積,如p＝p×i.處理循環(huán)結(jié)構(gòu)的框圖問(wèn)題,關(guān)鍵是理解認(rèn)清終止循環(huán)結(jié)構(gòu)的條件及循環(huán)次數(shù).補(bǔ)充：常用的程序符號(hào)與數(shù)學(xué)符號(hào)對(duì)照表：注："/"表示取商運(yùn)算,"Mod"表示求余運(yùn)算．四、算法案例1．輾轉(zhuǎn)相除法與更相減損術(shù)〔1輾轉(zhuǎn)相除法。輾轉(zhuǎn)相除法<歐幾里得算法>：對(duì)于給定的兩個(gè)數(shù),用較大的數(shù)除以較小的數(shù),若余數(shù)不為零,則將余數(shù)和較小的數(shù)構(gòu)成一對(duì)新數(shù),繼續(xù)上面的除法,直到余數(shù)為零,此時(shí)的除數(shù)就是所求兩數(shù)的最大公約數(shù)．〔2更相減損術(shù)更相減損術(shù)<等值算法>：對(duì)于給定的兩個(gè)數(shù),先判斷它們是否都是偶數(shù),若是,用2約簡(jiǎn)；若不是,執(zhí)行后面步驟．再以其中較大的數(shù)減去較小的數(shù),然后將差和較小的數(shù)構(gòu)成一對(duì)新數(shù),再用較大的數(shù)減去較小的數(shù),反復(fù)執(zhí)行以上步驟,直到被減數(shù)與較小的數(shù)相等為止,此時(shí)相等的這個(gè)數(shù)與約簡(jiǎn)數(shù)的乘積即為所求的最大公約數(shù)．輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：名稱輾轉(zhuǎn)相除法更相減損術(shù)區(qū)別①以除法為主②兩個(gè)整數(shù)差值較大時(shí),運(yùn)算次數(shù)較少③相除余數(shù)為零時(shí)得結(jié)果①以減法為主②兩個(gè)整數(shù)差值較大時(shí),運(yùn)算次數(shù)較多③相減,兩數(shù)相等得結(jié)果聯(lián)系①都是求最大公約數(shù)的方法②二者的實(shí)質(zhì)都是遞歸的過(guò)程③二者都要用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn)程序求正整數(shù)a,b<a>b>的最大公約數(shù)2．秦九韶算法與排序〔1秦九韶算法概念：把一個(gè)多項(xiàng)式f<x>＝anxn＋an－1xn－1＋…＋a1x＋a0改寫成如下形式：f<x>＝anxn＋an－1xn－1＋…＋a1x＋a0＝<<<anx＋an－1>x＋an－2>x＋…＋a1>x＋a0.求多項(xiàng)式的值時(shí),首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值,即v1＝anx＋an－1,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即v2＝v1x＋an－2,v3＝v2x＋an－3,…,vn＝vn－1x＋a0.這樣,求n次多項(xiàng)式f<x>的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值,這就是秦九韶算法．秦九韶算法的特點(diǎn)在于把求一個(gè)n次多項(xiàng)式的值轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值,即把求f<x>＝anxn＋an－1xn－1＋…＋a1x＋a0的值轉(zhuǎn)化為求遞推公式：eq\b\lc\{\rc\<\a\vs4\al\co1<v0＝an,,vk＝vk－1x＋an－k>><k＝1,2,…,n>．這樣可以最多計(jì)算n次乘法和n次加法即可得多項(xiàng)式的值,和直接代入多項(xiàng)式相比減少了乘法的運(yùn)算次數(shù)<通常求多項(xiàng)式f<x>＝anxn＋an－1xn－1＋…＋a1x＋a0的值時(shí),計(jì)算anxn,需n次乘法；計(jì)算an－1xn－1,需n－1次乘法……共需n＋<n－1>＋…＋1＝次乘法,還需n次加法,總共進(jìn)行＋n次運(yùn)算>,提高了運(yùn)算效率．〔2兩種排序方法：①直接插入排序基本思想：插入排序的思想就是讀一個(gè),排一個(gè)。將第１個(gè)數(shù)放入數(shù)組的第１個(gè)元素中,以后讀入的數(shù)與已存入數(shù)組的數(shù)進(jìn)行比較,確定它在從大到小的排列中應(yīng)處的位置．將該位置以及以后的元素向后推移一個(gè)位置,將讀入的新數(shù)填入空出的位置中．〔由于算法簡(jiǎn)單,可以舉例說(shuō)明②冒泡排序基本思想：依次比較相鄰的兩個(gè)數(shù),把大的放前面,小的放后面.即首先比較第1個(gè)數(shù)和第2個(gè)數(shù),大數(shù)放前,小數(shù)放后.然后比較第2個(gè)數(shù)和第3個(gè)數(shù)直到比較最后兩個(gè)數(shù).第一趟結(jié)束,最小的一定沉到最后.重復(fù)上過(guò)程,仍從第1個(gè)數(shù)開(kāi)始,到最后第2個(gè)數(shù)由于在排序過(guò)程中總是大數(shù)往前,小數(shù)往后,相當(dāng)氣泡上升,所以叫冒泡排序.五、進(jìn)位制1．概念：為了計(jì)數(shù)或運(yùn)算方便而約定的記數(shù)系統(tǒng),"滿足k進(jìn)一"就是k進(jìn)制,k是基數(shù)<其中k是大于1的整數(shù)>．k進(jìn)制的數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式為：anan－1…a1a0<k><0<an<k,0≤an－1,…,a1,a0<k>．2．不同進(jìn)制之間的轉(zhuǎn)化<1>k進(jìn)制轉(zhuǎn)化為十進(jìn)制數(shù)：先把k進(jìn)制數(shù)寫成不同數(shù)位上的數(shù)字與基數(shù)的冪的乘積之和的形式,再按十進(jìn)制數(shù)的運(yùn)算法則計(jì)算出結(jié)果即可．<2>十進(jìn)制數(shù)轉(zhuǎn)化為k進(jìn)制數(shù)：用k進(jìn)制數(shù)的基數(shù)k去除十進(jìn)制數(shù),再用k去除所得的商,反復(fù)進(jìn)行,直至商為0,然后將各步所得的余數(shù)倒序?qū)懗?即為相應(yīng)的k進(jìn)制．這種方法叫"除k取余法"．<3>兩個(gè)非十進(jìn)制數(shù)之間的轉(zhuǎn)化：若是將k1進(jìn)制數(shù)轉(zhuǎn)化為k2進(jìn)制數(shù),則先將將k1進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù),再將所得十進(jìn)制數(shù)化為k2進(jìn)制數(shù)．[考點(diǎn)突破]〖考點(diǎn)1〗對(duì)算法概念的理解1.下面關(guān)于算法的說(shuō)法正確的是〔DA.算法就是某個(gè)問(wèn)題的解決方法B.一個(gè)算法不產(chǎn)生確定的結(jié)果C.算法的步驟可以無(wú)限地執(zhí)行下去不停止D.對(duì)于一個(gè)給定的問(wèn)題,其算法不一定唯一〖考點(diǎn)2〗對(duì)程序框的認(rèn)識(shí)1．以下是給出的對(duì)程序框圖的幾種說(shuō)法：①任何一個(gè)程序框圖都必須有起、止框；②輸入框只能放在開(kāi)始框后,輸出框只能放在結(jié)束框前；③判斷框是唯一具有超過(guò)一個(gè)退出點(diǎn)的符號(hào)；④對(duì)于一個(gè)程序來(lái)說(shuō),判斷框內(nèi)的條件表達(dá)方法不是唯一的．⑤程序框圖是描述算法的語(yǔ)言；⑥由于算法設(shè)計(jì)時(shí)要求返回執(zhí)行的結(jié)果,故必須有輸出框,對(duì)于變量的賦值可以通過(guò)處理框完成,故算法設(shè)計(jì)時(shí)不一定要用輸入框；其中正確說(shuō)法的個(gè)數(shù)是<D>A．3 B．4C．5 D．62．有下列說(shuō)法：①任何一個(gè)算法都包含順序結(jié)構(gòu)；②條件結(jié)構(gòu)中一定包含循環(huán)結(jié)構(gòu)；③循環(huán)結(jié)構(gòu)一定包含條件結(jié)構(gòu)；④當(dāng)型循環(huán)結(jié)構(gòu)是先執(zhí)行一次循環(huán)體再判斷條件；⑤直到型循環(huán)結(jié)構(gòu)是直到條件成立時(shí)停止循環(huán)．其中正確的個(gè)數(shù)是<>CA．1B．2C．3D．4解：①③⑤正確；②④不正確．故選C.3.下列關(guān)于條件結(jié)構(gòu)的描述,不正確的是〔CA.條件結(jié)構(gòu)的出口有兩個(gè),但在執(zhí)行時(shí),只有一個(gè)出口是有效的B.條件結(jié)構(gòu)的判斷條件可以不只一個(gè)C.雙選擇條件結(jié)構(gòu)有兩個(gè)出口,單選擇條件只有一個(gè)出口D.條件結(jié)構(gòu)的"嵌套",就是在條件結(jié)構(gòu)的一支<或兩支>內(nèi)的步驟中又要用到條件結(jié)構(gòu)．〖考點(diǎn)3〗對(duì)算法語(yǔ)言的理解1．〔1下列賦值語(yǔ)句正確的是<>BA．S＝S＋i2B．A＝－AC．x＝2x＋1D．P＝eq\r<x>解：在程序語(yǔ)句中乘方用^表示,∴A不正確；乘號(hào)不能省略,∴C不正確；D中應(yīng)用SQR<x>表示,∴D不正確；B中是將變量A的相反數(shù)賦給變量A.〔2下列賦值語(yǔ)句正確的是〔DA.3=BB.x+y=0C.A=B=-2D.T=T*T評(píng)：賦值語(yǔ)句在程序運(yùn)行的過(guò)程中給變量賦值,具有計(jì)算功能,使用賦值語(yǔ)句時(shí)要注意以下幾點(diǎn)：①"＝"的右側(cè)必須為表達(dá)式或常量,左側(cè)必須為變量,如A＝3正確,而3＝A則錯(cuò)誤．②一個(gè)賦值語(yǔ)句只能給一個(gè)變量賦值,如A＝B＝5就是錯(cuò)誤的,可寫成A＝5,B＝5.2.判斷以下給出的輸入、輸出語(yǔ)句是否正確？為什么？<1>輸入語(yǔ)句Inputa；b；c<2>輸入語(yǔ)句Inputx＝3<3>輸出語(yǔ)句PrintA＝4<4>輸出語(yǔ)句Print20,3*2解:<1>不正確,變量之間應(yīng)用","隔開(kāi)．<2>不正確,Input語(yǔ)句中只能是變量,而不能是表達(dá)式．<3>不正確,Print語(yǔ)句中不能再用賦值號(hào)．<4>正確,Print語(yǔ)句可以輸出常量、表達(dá)式值．評(píng)：<1>輸入、輸出語(yǔ)句中,"提示內(nèi)容"與變量<或表達(dá)式>之間必須用"；"分開(kāi)；<2>輸入、輸出語(yǔ)句中,"提示內(nèi)容"連同它后面的"；"可省略；<3>輸出語(yǔ)句中可以只輸出"提示內(nèi)容",而不要后面的表達(dá)式,輸入語(yǔ)句則不能．〖考點(diǎn)4〗讀圖1．給出如圖程序框圖,其功能是<C>A．求a－b的值B．求b－a的值C．求|a－b|的值D．以上都不對(duì)2．下面程序運(yùn)行后,輸出的值是<>A．42B.43C．44D．45[解析]由于442＜2000,452＞2000,根據(jù)算法語(yǔ)句需輸出44.[答案]C3．程序若輸入a＝3,執(zhí)行上述程序后輸出的結(jié)果是<>A．9B．3C．10D．6[解析]該程序反映的算法是求分段函數(shù)y＝eq\b\lc\{\rc\<\a\vs4\al\co1<2a<a＜10>,a2<a≥10>>>的函數(shù)值．故a＝3時(shí),y＝2×3＝6.[答案]D4．某程序框圖如圖所示,該程序運(yùn)行后輸出的倒數(shù)第二個(gè)數(shù)是<>A.eq\f<17,16>B.eq\f<9,8>C.eq\f<5,4>D.eq\f<3,2>[解析]依次運(yùn)行程序得：第一次,n＝2,a＝2；第二次,n＝3,a＝eq\f<3,2>；第三次,n＝4,a＝eq\f<5,4>；再運(yùn)行第四次即結(jié)束,故倒數(shù)第二次輸出的數(shù)是eq\f<5,4>.[答案]C5．讀程序當(dāng)輸出的值y的范圍大于1時(shí),則輸入的x值的取值范圍是<>A．<－∞,－1>B．<1,＋∞>C．<－∞,－1>∪<1,＋∞>D．<－∞,0>∪<0,＋∞>[解析]由程序可得y＝eq\b\lc\{\rc\<\a\vs4\al\co1<\r<x><x＞0>,\b\lc\<\rc\><\a\vs4\al\co1<\f<1,2>>>x－1<x≤0>>>,∵y＞1,∴①當(dāng)x≤0時(shí),eq\b\lc\<\rc\><\a\vs4\al\co1<\f<1,2>>>x－1＞1,即2－x＞2,∴－x＞1,∴x＜－1.②當(dāng)x＞0時(shí),eq\r<x>＞1,x＞1,故輸入的x值的范圍為<－∞,－1>∪<1,＋∞>．[答案]C6．有編號(hào)為1,2,…,700的產(chǎn)品,現(xiàn)需從中抽取所有編號(hào)能被7整除的產(chǎn)品作為樣品進(jìn)行檢驗(yàn)．下面是四位同學(xué)設(shè)計(jì)的程序框圖,其中正確的是<B>解析：選項(xiàng)A、C中的程序框圖會(huì)輸出0,故排除A、C；選項(xiàng)D中的程序框圖不能輸出700,故排除D.答案：B7．如下圖所示的程序框圖輸出的結(jié)果為<>A．b＝0B．b＝1C．b＝4D．b＝5[答案]D[解析]根據(jù)程序執(zhí)行的過(guò)程a＝1,b＝1＋3＝4,b＝4＋1＝5.故選D.8．輸入－5,按下圖中所示程序框圖運(yùn)行后,輸出的結(jié)果是<>A．－5B．0C．－1D．1[答案]D[解析]此算法的功能是求分段函數(shù)f<x>＝eq\b\lc\{\rc\<\a\vs4\al\co1<－1,x>0,,0,x＝0,,1,x<0>>的函數(shù)值,f<－5>＝1.故選D.9．如圖所示的程序框圖輸出的結(jié)果是<>A.eq\f<3,4>B.eq\f<4,5>C.eq\f<5,6>D.eq\f<6,7>[答案]C[解析]第一次執(zhí)行循環(huán)體,A＝eq\f<1,2－\f<1,2>>＝eq\f<2,3>,i＝2；第二次執(zhí)行循環(huán)體,A＝eq\f<1,2－\f<2,3>>＝eq\f<3,4>,i＝3,第三次執(zhí)行循環(huán)體,A＝eq\f<1,2－\f<3,4>>＝eq\f<4,5>,i＝4,第四次執(zhí)行循環(huán)體,A＝eq\f<1,2－\f<4,5>>＝eq\f<5,6>,i＝5,結(jié)束循環(huán)．故選C.10．在如圖所示的算法流程圖中,若f<x>＝2x,g<x>＝x2,則h<2>的值為<>A．9B．8C．6D．4[答案]D[解析]h<x>＝max{f<x>,g<x>},∴h<2>＝4.故選D.11．如圖1所示的程序框圖所進(jìn)行的求和運(yùn)算是<>A.eq\f<1,2>＋eq\f<1,4>＋eq\f<1,6>＋…＋eq\f<1,20>B．1＋eq\f<1,3>＋eq\f<1,5>＋…＋eq\f<1,19>C．1＋eq\f<1,2>＋eq\f<1,4>＋…＋eq\f<1,18>D.eq\f<1,2>＋eq\f<1,22>＋eq\f<1,23>＋…＋eq\f<1,210>[答案]A[解析]初始值i＝2,每循環(huán)一次加2,s從eq\f<1,2>一直累加到eq\f<1,20>.故選A.12．為確保信息安全,信息需加密傳輸,發(fā)送方由明文→密文<加密>,接收方由密文→明文<解密>,已知加密規(guī)則如圖2所示,例如,明文1,2,3,4對(duì)應(yīng)密文5,7,18,16.當(dāng)接收方收到密文14,9,23,28時(shí),則解密得到的明文為<>圖1圖2A．4,6,1,7B．7,6,1,4C．6,4,1,7D．1,6,4,7[答案]C[解析]程序框圖給出的加密規(guī)則是：m＝a＋2b,n＝2b＋c,p＝2c＋3d,q＝4d.因此接收到密文14,9,23,28時(shí),有a＋2b＝14,2b＋c＝9,2c＋3d＝23,4d＝28,∴a＝6,b＝4,c＝1,d＝7.∴解密得到的明文為6,4,1,7.故選C.13．某流程圖如圖所示,現(xiàn)輸入如下四個(gè)函數(shù),則可以輸出的函數(shù)是<C>A．f<x>＝x2B．f<x>＝eq\f<|x|,x>C．f<x>＝eq\f<ex－e－x,ex＋e－x>D．f<x>＝eq\f<1＋sinx＋cosx,1＋sinx－cosx>解析：根據(jù)流程圖可知輸出的函數(shù)為奇函數(shù),并且存在零點(diǎn)．經(jīng)驗(yàn)證：選項(xiàng)A,f<x>＝x2為偶函數(shù)；選項(xiàng)B,f<x>＝eq\f<|x|,x>不存在零點(diǎn)；選項(xiàng)C,f<x>的定義域?yàn)槿w實(shí)數(shù),f<－x>＝eq\f<e－x－ex,e－x＋ex>＝－f<x>,因此為奇函數(shù),并且由f<x>＝eq\f<ex－e－x,ex＋e－x>＝0可得x＝0,存在零點(diǎn)；選項(xiàng)D,f<x>＝eq\f<1＋sinx＋cosx,1＋sinx－cosx>不具有奇偶性．答案：C14．執(zhí)行如下程序,結(jié)果是。[解析]循環(huán)10次,S=1+3+5+……+19=100.[答案]10015．下面程序表達(dá)的是求函數(shù)________的值．[解析]根據(jù)所給的程序語(yǔ)句可知,這是條件語(yǔ)句輸入x后隨著x取不同的值輸出的y的結(jié)果也不相同,故所求的是一個(gè)分段函數(shù)y＝eq\b\lc\{\rc\<\a\vs4\al\co1<1<x＞0>,0<x＝0>,－1<x＜0>>>的值．[答案]y＝eq\b\lc\{\rc\<\a\vs4\al\co1<1<x＞0>,0<x＝0>,－1<x＜0>>>16．如圖4是一個(gè)算法的程序框圖,當(dāng)輸入的值x為5時(shí),則其輸出的結(jié)果是______．2圖4解：第一次執(zhí)行循環(huán)體,x＝2；第二次執(zhí)行循環(huán)體,x＝－1,結(jié)束循環(huán),y＝0.5－1＝2.17．如果執(zhí)行右面的框圖,輸入N＝5,則輸出數(shù)等于 <D>A.eq\f<5,4> B.eq\f<4,5>C.eq\f<6,5> D.eq\f<5,6>18．如圖所示的程序,如果n＝6,則輸出的結(jié)果為<>A．6B．720C．120D．1[答案]B[解析]S＝1×2×3×4×5×6＝720.故選B.19．在如下程序框圖中,輸入f0<x>＝sinx,則輸出的是________．[解析]由已知可得：f1<x>＝f′0<x>＝cosx,f2<x>＝f′1<x>＝－sinx,f3<x>＝f′2<x>＝－cosx,f4<x>＝f′3<x>＝sinx,f5<x>＝f′4<x>＝cosx,即fn<x>＝fn＋4<x>,周期為4,故由算法框圖可知f2009<x>＝f1<x>＝cosx.[答案]cosx19．某城市缺水問(wèn)題比較突出,為了制定節(jié)水管理辦法,對(duì)全市居民某年的月均用水量進(jìn)行了抽樣調(diào)查,其中4位居民的月均用水量分別為x1,…,x4<單位：噸>．根據(jù)如圖所示的程序框圖,若x1,x2,x3,x4分別為1,1.5,1.5,2,則輸出的結(jié)果s為_(kāi)____．1.520．<本題滿分12分>按如圖所示的程序框圖運(yùn)算：<1>若輸入x＝8,求輸出的結(jié)果；<2>若輸出k＝2,求輸入的x的取值范圍．[解析]<1>當(dāng)輸入x＝8時(shí),第1次執(zhí)行循環(huán)體x＝17,k＝1；第2次執(zhí)行循環(huán)體x＝35,k＝2；第3次執(zhí)行循環(huán)體x＝71,k＝3；第4次執(zhí)行循環(huán)體x＝143>115,k＝4.結(jié)束循環(huán)．∴k＝4.<2>若輸出k＝2,則2x＋1≤115且2<2x＋1>＋1>115,即28<x≤57.∴x的取值范圍是<28,57]．〖考點(diǎn)5〗補(bǔ)圖1．如果下邊程序執(zhí)行后輸出的結(jié)果是132,那么在程序while后面的"條件"應(yīng)為<>BA．i＞11B．i＞＝11C．i＜＝11D．i＜11[解析]因?yàn)檩敵龅慕Y(jié)果是132,即s＝1×12×11,需執(zhí)行2次,則在程序while后面的"條件"應(yīng)為i＞＝11.2．現(xiàn)欲求1＋eq\f<1,3>＋eq\f<1,5>＋…＋eq\f<1,2n－1>的和<其中n的值由鍵盤輸入>,已給出了其程序框圖,請(qǐng)將其補(bǔ)序完整并設(shè)計(jì)出程序．[解析]這是一個(gè)利用循環(huán)結(jié)構(gòu)來(lái)解決的求和問(wèn)題,故①i＝i＋1,②S＝S＋eq\f<1,2i－1>.程序：N＝input<"n＝">；S＝0；i＝0；whilei＜ni＝i＋1；S＝S＋1/<2*i-1>;endPrint<%io<2>;S>;3．某籃球隊(duì)6名主力隊(duì)員在最近三場(chǎng)比賽中投進(jìn)的三分球個(gè)數(shù)如下表所示：隊(duì)員i123456三分球個(gè)數(shù)a1a2a3a4a5a6下圖是統(tǒng)計(jì)該6名隊(duì)員在最近三場(chǎng)比賽中投進(jìn)的三分球總數(shù)的程序框圖,則圖中判斷框應(yīng)填__________,輸出的s＝__________________.[答案]i≤6a1＋a2＋…＋a6[解析]圖中判斷框應(yīng)填i≤6,輸出的s＝a1＋a2＋…＋a6.4．如圖所示的程序框圖運(yùn)行的結(jié)果為s＝132,那么判斷框中應(yīng)填入的關(guān)于k的判斷條件是___．[答案]k≤10？<k<11？>[解析]∵s＝1×12×11＝132,循環(huán)執(zhí)行了兩次,驗(yàn)證后可確定k≤10<或k<11>．5.右圖是求x1,x2,…,x10的乘積S的程序框圖,圖中空白框中應(yīng)填入的內(nèi)容為<D>A．S＝S*<n＋1>B．S＝S*xn＋1C．S＝S*nD．S＝S*xn6．以下圖給出的是計(jì)算eq\f<1,2>＋eq\f<1,4>＋…＋eq\f<1,20>值的一個(gè)程序框圖,其中判斷框內(nèi)應(yīng)填入的條件是<>A．i>10B．i<10C．i>20D．i<20[答案]A7．根據(jù)條件把程序框圖補(bǔ)充完整,求1到1000內(nèi)<包括1000>的所有奇數(shù)的和,<1>處填______,<2>處填________．[答案]s＝s＋ii＝i＋2[解析]根據(jù)題意,此程序框圖為當(dāng)型結(jié)構(gòu),先判斷再計(jì)算,∴<1>處應(yīng)填s＝s＋i,<2>處應(yīng)填i＝i＋2.〖考點(diǎn)8〗畫圖、編程1．畫出求一個(gè)數(shù)的絕對(duì)值的程序框圖,只需用<>DA．順序結(jié)構(gòu)B．條件結(jié)構(gòu)C．循環(huán)結(jié)構(gòu)D．順序結(jié)構(gòu)和條件結(jié)構(gòu)解：求一個(gè)數(shù)的絕對(duì)值,需要對(duì)數(shù)的正負(fù)進(jìn)行判斷,所以程序框圖中需用條件結(jié)構(gòu),又順序結(jié)構(gòu)是任何一個(gè)算法都離不開(kāi)的基本結(jié)構(gòu)．故選D.2．直到型循環(huán)結(jié)構(gòu)的框圖為<>B解：在執(zhí)行了一次循環(huán)體后,對(duì)條件進(jìn)行判斷,如果條件不滿足,就繼續(xù)執(zhí)行循環(huán)體,直到條件滿足時(shí)終止循環(huán)．故選B.4．畫出計(jì)算S＝1·22＋2·23＋3·24＋…＋10·211的值的程序框圖．解：如圖所示：3．編寫程序,對(duì)于輸入的x值,輸出相應(yīng)的y值.解：4．某商場(chǎng)實(shí)行優(yōu)惠措施,若購(gòu)物金額x在800元以上<含800元>打8折；若購(gòu)物金額在500元以上<含500元>打9折,否則不打折．請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法程序框圖,要求輸入購(gòu)物金額x,能輸出實(shí)際交款額,并寫出程序．解：程序框圖程序：〖考點(diǎn)9〗輾轉(zhuǎn)相除法1.設(shè)計(jì)程序框圖,用秦九韶算法求多項(xiàng)式的值,主要用哪種結(jié)構(gòu)實(shí)現(xiàn)〔CA.順序結(jié)構(gòu)B.條件結(jié)構(gòu)C.循環(huán)結(jié)構(gòu)D.條件、順序結(jié)構(gòu)2.用輾轉(zhuǎn)相除法求某兩個(gè)正整數(shù)的最大公約數(shù)時(shí),已知某步為,則下一步應(yīng)為〔CA.B.C.D.沒(méi)有下一步即結(jié)束3.用輾轉(zhuǎn)相除法求1457與188的最大公