復(fù)數(shù) 算法初步 課件

新課標(biāo)高中一輪總復(fù)習(xí)第八單元復(fù)數(shù)、算法初步第58講基本算法語(yǔ)句與算法案例1.理解輸入語(yǔ)句、輸出語(yǔ)句、賦值語(yǔ)句、條件語(yǔ)句、循環(huán)語(yǔ)句這五種算法語(yǔ)句的含義.2.能準(zhǔn)確地實(shí)現(xiàn)程序框圖與算法語(yǔ)句的互相轉(zhuǎn)化。3.了解秦九韶算法、輾轉(zhuǎn)相除法與更相減損術(shù)等特殊案例的算法思想和算法語(yǔ)句.1.某一程序中先后相鄰的兩個(gè)語(yǔ)句是:x=3*5,x=x+1,那么下列說法中正確的是（）①x=3*5的意思是x=3×5=15，此式與算術(shù)式中的意義是一樣的；②x=3*5是將數(shù)值15賦給x；③x=3*5也可以寫為3*5=x；④x=x+1在執(zhí)行時(shí)，賦值號(hào)右邊的x值是15，執(zhí)行后左邊的x值是16.BA.①③B.②④C.①④D.②③2.運(yùn)行如圖所示的程序后,輸出的結(jié)果為()Ci=1WHILEi<7i=i+1S=2*i-1i=i+2WENDPRINTS，iENDA.13,7B.7,4C.9,7D.9,5

由程序知該算法循環(huán)了兩次，第一次，S=2×2-1=3，i=4；第二次，S=2×5-1=9，i=7.因?yàn)閕≥7，循環(huán)結(jié)束，輸出S=9，i=7.3.把二進(jìn)制數(shù)1011001(2)化為五進(jìn)制數(shù)是

.324(5)1011001(2)=1×26+1×24+1×23+1=89,所以89=324(5).4.程序如下：以上程序輸出的結(jié)果是

.t=1i=2WHILEi≤4t=t*ii=i+1WENDPRINTtEND24

由題意可知，它表示計(jì)算1×2×3×…×n的算法，所以輸出的結(jié)果為1×2×3×4=24.一、基本算法語(yǔ)句1.輸入、輸出語(yǔ)句和賦值語(yǔ)句：輸入語(yǔ)句格式:①

;輸出語(yǔ)句格式:②

;賦值語(yǔ)句格式:③

.2.條件語(yǔ)句：(1)框圖：INPUT“提示內(nèi)容”;變量PRINT“提示內(nèi)容”;表達(dá)式變量名=表達(dá)式(2)條件語(yǔ)句格式：IF條件THEN

語(yǔ)句1ELSE

語(yǔ)句2ENDIF條件語(yǔ)句的嵌套:條件語(yǔ)句④

,當(dāng)出現(xiàn)3個(gè)或3個(gè)以上的判斷點(diǎn)時(shí),就要用到⑤

,其一般格式為：主要用于實(shí)現(xiàn)算法中的條件結(jié)構(gòu)程序嵌套IF表達(dá)式1THEN

語(yǔ)句序列1；ELSEIF表達(dá)式2THEN

語(yǔ)句序列2ELSE

語(yǔ)句序列3ENDIFENDIF3.循環(huán)語(yǔ)句：(1)WHILE語(yǔ)句的結(jié)構(gòu)WHILE語(yǔ)句的一般格式：WHILE條件循環(huán)體END(2)UNTIL語(yǔ)句的結(jié)構(gòu)：UNTIL語(yǔ)句的一般格式：DO循環(huán)體LOOPUNTIL條件

二、算法案例

1.輾轉(zhuǎn)相除法與更相減損術(shù).(1)輾轉(zhuǎn)相除法:⑥.

.

,反復(fù)操作，直到余數(shù)為0為止,即m=nt+r(0≤r≤n).因此要用“后測(cè)試型”循環(huán)語(yǔ)句表示，其程序如下：求兩個(gè)正整數(shù)的最大公約數(shù)的方法.用較大的數(shù)m除以較小的數(shù)n得到余數(shù)rINPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND(2)更相減損術(shù)是⑦

.

.

用較大數(shù)減去較小數(shù)，再用差數(shù)和較小數(shù)構(gòu)成一對(duì)新數(shù)，再用大數(shù)減去小數(shù)，以同樣的操作一直做下去，直到所得的數(shù)相等為止.這一過程可由循環(huán)語(yǔ)句表達(dá)算法，其程序如下:求兩個(gè)正整數(shù)的最大公約數(shù)的算法INPUTa,bWHILEa<>bIFa＞=bTHENa=a-bELSEb=b-aENDIFWENDPRINTa,bEND2.秦九韶算法.n次多項(xiàng)式f(x)=anxn+an-1xn-1+…+a1x+a0=(anxn-1+an-1xn-2+…+a1)x+a0…=(((…(anx+an-1)x+an-2)x+…+a1)x+a0得到遞推公式v0=an且vk=vk-1x+an-k,其中k=1,2,…,n.其算法可用循環(huán)語(yǔ)句來實(shí)現(xiàn).3.排序.

直接插入排序法:⑧.

..

冒泡法的排序算法步驟：第一步:用第1個(gè)數(shù)與第2個(gè)數(shù)比較，若前者小則兩個(gè)數(shù)不變，否則調(diào)整兩數(shù)位置.

第二步：按同樣的規(guī)則，比較第2個(gè)數(shù)與第3個(gè)數(shù)，……直到比較完最后兩數(shù)，這個(gè)過程稱為“一趟”.從第一個(gè)數(shù)開始,依次把每個(gè)數(shù)插入到已排好序的適當(dāng)位置,直到完成對(duì)最后一個(gè)數(shù)的操作

第三步：如果前一趟比較中交換次數(shù)為0，說明排序已完成，否則返回第二步.4.進(jìn)位制.(1)將十進(jìn)制數(shù)化為二進(jìn)制數(shù)的算法稱為⑨

；將十進(jìn)制數(shù)化為k進(jìn)制數(shù)的算法稱為⑩

.(2)將k進(jìn)制數(shù)化為十進(jìn)制數(shù)的算法步驟為：第一步:從左到右依次取k進(jìn)制數(shù)anan-1…

a1a0(k)各位上的數(shù)字乘以k次冪,k從n開始取值，每次遞減1，遞減到0，即an·kn,an-1·kn-1,…,a1·k,

a0·k0;

第二步:把所有積加起來,就得到十進(jìn)制數(shù).除2取余法除k取余法題型一基本算法語(yǔ)句及應(yīng)用例1

高一（2）班共有54名同學(xué)參加數(shù)學(xué)競(jìng)賽，現(xiàn)已有這54名同學(xué)的競(jìng)賽分?jǐn)?shù)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序，求成績(jī)優(yōu)秀同學(xué)的平均分（規(guī)定90分以上為優(yōu)秀）.由于涉及54名同學(xué)的分?jǐn)?shù)，因此，可以使用循環(huán)結(jié)構(gòu)控制輸入分?jǐn)?shù)，用條件結(jié)構(gòu)來判斷分?jǐn)?shù)是否高于90分，同時(shí)統(tǒng)計(jì)高于90分的成績(jī)的總和和人數(shù)，從而求平均分.S=0M=0i=1WHILEi≤54INPUTxIFx>90THENS=S+xM=M+1ENDIFi=i+1WENDP=S/MPRINTPEND

程序設(shè)計(jì)如下:

在解決實(shí)際問題時(shí)，要正確理解其中的算法思想，根據(jù)題目寫出其關(guān)系式，再寫出相應(yīng)的算法.在循環(huán)語(yǔ)句中，也可能嵌套條件語(yǔ)句，甚至是循環(huán)語(yǔ)句，此時(shí)需要注意嵌套這些語(yǔ)句需要保證語(yǔ)句完整性，否則就會(huì)造成程序無法執(zhí)行.

因慶期間，某超市實(shí)行購(gòu)物優(yōu)惠活動(dòng)，規(guī)定一次購(gòu)物付款總額：①若不超過200元，則不予優(yōu)惠；②若超過200元，但不超過500元，則按標(biāo)價(jià)價(jià)格給予9折優(yōu)惠；③如果超過500元，500元的部分按②優(yōu)惠，超過500元的部分給予7折優(yōu)惠.編寫一個(gè)收款的相應(yīng)程序.

程序如下:INPUTxIFx≤200THENPRINTxELSEIFx>200ANDx≤500THENy=0.9*xPRINTyELSEy=0.9*500+0.7*(x-500)PRINTyENDIFENDIFEND題型二程序框圖與程序的相互轉(zhuǎn)化例2

某商場(chǎng)購(gòu)物實(shí)行優(yōu)惠措施，若購(gòu)物金額x在800元以上打8折；購(gòu)物金額x在500元以上打9折，否則不打折.請(qǐng)?jiān)O(shè)計(jì)程序框圖，并根據(jù)框圖編寫程序，要求輸入金額x，輸出實(shí)際交款額.

根據(jù)題意，實(shí)際交款額y（元）與購(gòu)物金額x（元）的函數(shù)關(guān)系如下：

x(0<x≤500)0.9x(500＜x≤800)0.8x(x＞800).程序框圖如下：y=程序如下：INPUTxIFx>800THENy=0.8*xELSEIFx>500THENy=0.9*xELSEy=xENDIFENDIFPRINTyEND

解決分段函數(shù)的求值問題時(shí)，一般采用條件結(jié)構(gòu)設(shè)計(jì)算法.如果變量分為三級(jí)（或以上），就需要用到條件結(jié)構(gòu)的嵌套.另外，不能忽視結(jié)果中“是”和“否”的書寫，否則不知執(zhí)行哪一條路徑.

現(xiàn)給出某班50名同學(xué)的數(shù)學(xué)成績(jī)，60分以上為及格.要求統(tǒng)計(jì)及格人數(shù)和全班同學(xué)的平均分，畫出程序框圖，并寫出程序語(yǔ)句.

程序框圖如右圖所示.程序如下:i=1S=0t=0DOINPUTxS=S+xIFx＞=60THENt=t+1ENDIFi=i+1LOOPUNTILi＞50p=S/50PRINTpPRINTtEND

該題主要運(yùn)用算法的條件結(jié)構(gòu)及條件語(yǔ)句正確表達(dá)算法，關(guān)鍵是理解變量x的作用，用x來表示某學(xué)生的分?jǐn)?shù)，每循環(huán)一次輸入一個(gè)x的值，表示及格人數(shù)的變量t與表示學(xué)生人數(shù)的變量i均加1.題型三算法案例例3

用秦九韶算法求多項(xiàng)式f(x)=8x7+5x6+3x4+2x+1當(dāng)x=2時(shí)的值.

利用秦九韶算法一步一步地代入運(yùn)算，注意本題中有幾項(xiàng)不存在，此時(shí)在計(jì)算時(shí)，我們應(yīng)該將這些項(xiàng)加上，比如含有x3的這一項(xiàng)可看做0·x3.

根據(jù)秦九韶算法,把多項(xiàng)式寫成如下形式:f(x)=8x7+5x6+0·x5+3x4+0·x3+0·x2+2x+1=((((((8x+5)x+0)x+3)x+0)x+0)x+2)x+1,v0=8v1=8×2+5=21，v2=21×2+0=42,v3=42×2+3=87，v4=87×2+0=174，v5=174×2+0=348，v6=348×2+2=698，v8=698×2+1=1397.所以當(dāng)x=2時(shí)，多項(xiàng)式的值為1397.

秦九韶算法是多項(xiàng)式求值的優(yōu)秀算法，其特點(diǎn)是：(1)化高次多項(xiàng)式求值為一次多項(xiàng)式求值；(2)減少了運(yùn)算次數(shù)，提高了效率；(3)步驟重復(fù)執(zhí)行，容易用計(jì)算機(jī)實(shí)現(xiàn).利用秦九韶算法計(jì)算多項(xiàng)式的值關(guān)鍵是能正確地將所給多項(xiàng)式改寫，然后由內(nèi)向外逐次計(jì)算,由于后項(xiàng)計(jì)算用到前項(xiàng)的結(jié)果，故應(yīng)認(rèn)真、細(xì)心,確保中間結(jié)果的準(zhǔn)確性，若在多項(xiàng)式中有幾項(xiàng)不存在,可將這些項(xiàng)的系數(shù)看成0,即把這些項(xiàng)看做0×xn.(1)將七進(jìn)制數(shù)235(7)轉(zhuǎn)化為十進(jìn)制的數(shù)；(2)把五進(jìn)制的數(shù)44(5)轉(zhuǎn)化為二進(jìn)制的數(shù).

（1）把七進(jìn)制數(shù)寫成各位上數(shù)字與7的冪的乘積之和的形式，再按十進(jìn)制的運(yùn)算得到結(jié)果；（2）先把五進(jìn)制的數(shù)化為十進(jìn)制的數(shù)，再化為二進(jìn)制的數(shù).

(1)235(7)=2×72+3×71+5×70=2×49+3×7+5=124.(2)44(5)=4×51+4×50=24.所以24=11000(2).(1)用輾轉(zhuǎn)相除法或更相減損術(shù)求三個(gè)數(shù)324，243，135的最大公約數(shù).(2)某工程的工序流程如圖所示，現(xiàn)已知工程總時(shí)數(shù)為10天，則工序c所需工時(shí)為多少天？

（1）(方法一)輾轉(zhuǎn)相除法：324=243×1+81，243=81×3＋0，則34與243的最大公約數(shù)是81.又135＝81×1＋54，

81＝54×1+27，

54＝27×2＋0，則81與135的最大公約數(shù)為27.故三個(gè)數(shù)34，243，135的最大公約數(shù)為27.(方法二)更相減損術(shù)：因?yàn)?324,243)→(243,81)→(162,81)→(81,81),又(135,81)→(81,54)→(54,27)→(27,27),所以324，243，135的最大公約數(shù)為27.(2)設(shè)工序c所需工時(shí)數(shù)為x天，由題意，a→c→e→g，需要工時(shí)數(shù)1+x+4+1=10，所以x=4,即工序c所需工時(shí)數(shù)為4天.1.關(guān)于條件語(yǔ)句.(1)“條件”是由一個(gè)關(guān)系表達(dá)式或邏輯表達(dá)式構(gòu)成的,其一般形式為“〈表達(dá)式〉〈關(guān)系運(yùn)算符〉〈表達(dá)式〉”，常用的運(yùn)算符有“>”（大于）、“<”（小于）、“>=”（大于或等于）、“<=”（小于或等于），表達(dá)式的結(jié)果可取兩個(gè)值,以“真”或“假”來表示，“真”表示條件滿足，“假”表示條件不滿足.(2)“語(yǔ)句”是由程序語(yǔ)言中所有語(yǔ)句構(gòu)成的程序段，即可以是語(yǔ)句組.(3)條件語(yǔ)句可以嵌套，即條件語(yǔ)句的THEN或ELSE后面還可以跟條件語(yǔ)句,其一般形式是：IF條件1THEN

語(yǔ)句1ELSEIF