算法初步課件

1、1.1算法與程序框圖,1.1.1算法的概念,先去括號(hào),再乘除,后加減,1,什么是算法呢,要把大象裝冰箱，分幾步,答：分三步,第一步：打開冰箱門,第二步：把大象裝冰箱,第三步：關(guān)上冰箱門,問,簡單地說，算法就是解決問題的程序或步驟,什么是算法呢,第一步,第二步,第三步,消元,解一元一次方程,2，得,解得,代入求解,將 代入,得,寫一寫,寫出解第二個(gè)方程組的算法,第一步,第二步,第三步,解，得,將代入得,變一變,在數(shù)學(xué)上，通常是按照一定規(guī)則解決某一類問題的明確有限的步驟,算法的定義,例1,1)設(shè)計(jì)一個(gè)算法,判斷7是否為質(zhì)數(shù),2)設(shè)計(jì)一個(gè)算法,判斷35是否為質(zhì)數(shù),算法,探究,你能寫出”判斷整數(shù)n(n

2、2) 是否為質(zhì)數(shù)”的算法嗎,第一步,給定大于2的整數(shù)n,第二步,令i=2,算法的基本特點(diǎn),1、有窮性,一個(gè)算法應(yīng)包括有限的操作步驟，能在執(zhí)行有窮的操作步驟之后結(jié)束,2、確定性,算法的計(jì)算規(guī)則及相應(yīng)的計(jì)算步驟必須是唯一確定的，既不能含糊其詞，也不能有二義性,3、邏輯性,算法中從開始的“第一步”到“最后一步”之間做到 環(huán)環(huán)相扣，分工明確，“前一步”是“后一步”的前提，“后一步”是“前一步”的繼續(xù),算法1,第二步：計(jì)算10150,第三步：寫出運(yùn)算結(jié)果,算法2,第一步：取n=100,第二步：計(jì)算,第三步：寫出運(yùn)算結(jié)果,寫出求1+2+3+ +100的一個(gè)算法,1+100)+(2+99)+ +(50+51

3、,第一步：將原式變形為,你會(huì)了嗎,2.任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積,第一步:輸入任意一個(gè)正實(shí)數(shù)r0,第二步:計(jì)算圓的面積: S=r2,第三步:輸出圓的面積S,1.1.2程序框圖,程序框圖,程序框圖又稱流程圖，是一種用程序框、流程線及文字說明來表示算法的圖形,在程序框圖中，一個(gè)或幾個(gè)程序框的組合表示算法中的一個(gè)步驟；帶有方向箭頭的流程線將程序框連接起來，表示算法步驟的執(zhí)行順序,例 用程序框圖表示“判斷整數(shù)n（n2）是否為質(zhì)數(shù)”的算法,設(shè)n是一個(gè)大于2的整數(shù),一般用i=i+1表示,i=i+1,說明:i表示從2(n-1)的所有正整數(shù),用以判斷例1步驟2是否終止,i是一個(gè)

4、計(jì)數(shù)變量,有了這個(gè)變量,算法才能依次執(zhí)行.逐步考察從2(n-1)的所有正整數(shù)中是否有n的因數(shù)存在,畫程序框圖的規(guī)則,1）使用標(biāo)準(zhǔn)的圖形符號(hào),2）框圖一般按從上到下，從左到右的方向畫,3）除判斷框外，大多數(shù)流程圖符號(hào)只有一個(gè)進(jìn)入點(diǎn)和一個(gè)退出點(diǎn)。判斷框具有超過一個(gè)退出點(diǎn)的唯一符號(hào),4）判斷框分兩大類，一類判斷框“是”與“否”兩分支的判斷，而且又且僅有兩個(gè)結(jié)果；另一類是多分支判斷，有幾種不同的結(jié)果,5）在圖形符號(hào)內(nèi)描述的語言要非常簡練清楚,算法的基本邏輯結(jié)構(gòu),順序結(jié)構(gòu),用程序框圖來表示算法，有三種不同的基本邏輯結(jié)構(gòu),條件結(jié)構(gòu),循環(huán)結(jié)構(gòu),三種基本結(jié)構(gòu)（表示一個(gè)良好算法的基本單元,順序結(jié)構(gòu),條件結(jié)構(gòu)（選

5、擇結(jié)構(gòu),循環(huán)結(jié)構(gòu),While（當(dāng)型）循環(huán),Until（直到型）循環(huán),順序結(jié)構(gòu),順序結(jié)構(gòu)是由若干個(gè)依次執(zhí)行的步驟組成的。這是任何一個(gè)算法都離不開的基本結(jié)構(gòu),例1 已知一個(gè)三角形的三邊邊長分別為a、b、c，利用 海倫-秦九韶公式設(shè)計(jì)一個(gè)算法，求出它的面積，畫出 它的程序框圖,程序框圖,習(xí)題1 設(shè)計(jì)一算法：輸入圓的半徑,輸出圓的面積，并畫出流程圖,算法分析,第一步：輸入圓的半徑,第二步：利用公式“圓的面積=圓周率（半徑的平方）”計(jì)算圓的面積,第三步：輸出圓的面積,思考：整個(gè)程序框圖有什么特點(diǎn),條件結(jié)構(gòu)（選擇結(jié)構(gòu),算法的流程根據(jù)條件是否成立有不同的流向。條件結(jié)構(gòu)就是處理這種過程的結(jié)構(gòu),例2 任意給定3

6、個(gè)正實(shí)數(shù)，設(shè)計(jì)一個(gè)算法，判斷分別以這3個(gè)數(shù)為三邊邊長的三角形是否存在.畫出這個(gè)算法的程序框圖,解：算法如下。 S1 輸入x S2 若x為奇數(shù)，則輸出A=3x+2；否則輸出A=5x S3 算法結(jié)束,習(xí)題2 設(shè)x為一個(gè)正整數(shù)，規(guī)定如下運(yùn)算：若x為奇數(shù)，則求3x+2；若x為偶數(shù)，則為5x，寫出算法，并畫出程序框圖,循環(huán)結(jié)構(gòu),在一些算法中，從否處開始，按照一定條件，反復(fù)執(zhí)行 某一處理步驟的情況，這就是循環(huán)結(jié)構(gòu)。反復(fù)執(zhí)行的處 理步驟稱為循環(huán)體,在循環(huán)結(jié)構(gòu)中，通常都有一個(gè)起到循環(huán)計(jì)數(shù)作用的變量， 這個(gè)變量的取值一般都含在執(zhí)行或中止循環(huán)體的條件中,例3 設(shè)計(jì)一個(gè)計(jì)算1+2+3+100的值的算法，并畫出程序框

7、圖,算法分析： 需要一個(gè)累加變量和一個(gè)計(jì)數(shù)變量，將累加變量的初始值 設(shè)為0，計(jì)數(shù)變量的值可以從1到100,1.2,基本算法語句,第一章 算法初步,探究新知】 我們知道，順序結(jié)構(gòu)是任何一個(gè)算法都離不開的基本結(jié)構(gòu),輸入、輸出語句和賦值語句基本上對應(yīng)于算法中的順序結(jié)構(gòu),計(jì)算機(jī)從上而下按照語句排列的順序執(zhí)行這些語句,輸入語句和輸出語句分別用來實(shí)現(xiàn)算法的輸入信息,輸出結(jié)果的功能,如右圖,輸入語句和輸出語句分別用來實(shí)現(xiàn)算法的輸入信息，輸出結(jié)果的功能,例1 用描點(diǎn)法作函數(shù)yx33x224x30的圖象時(shí),需要求出自變量和函數(shù)的一組對應(yīng)值.編寫程序,分別計(jì)算當(dāng) x5，4，3，2，1，0，1，2，3，4，5 時(shí)的

8、函數(shù)值,INPUT “x=”;x y=x3+3*x2-24*x+30 PRINT x PRINT y END,程序,輸入語句,賦值語句,打印語句,打印語句,表示結(jié)束,輸出語句,輸出語句,一.輸入語句,INPUT “提示內(nèi)容”；變量,輸入語句的一般格式,說明: (1)輸入語句的作用是實(shí)現(xiàn)算法的輸入信息功能； (2)“提示內(nèi)容”提示用戶輸入什么樣的信息， 變量是指程序在運(yùn)行時(shí)其值是可以變化的量； (3)輸入語句要求輸入的值只能是具體的常數(shù)， 不能是函數(shù)、變量或表達(dá)式； (4)提示內(nèi)容與變量之間用分號(hào)“；”隔開， 若輸入多個(gè)變量，變量與變量之間用逗號(hào)“，”隔開,例如,輸入一個(gè)學(xué)生數(shù)學(xué),語文,英語三門

9、課的成績, 可以寫成,INPUT “數(shù)學(xué)，語文，英語”；a，b，c,注意: INPUT語句不但可以給單個(gè)變量賦值,還可以給多個(gè)變量賦值,其格式為,INPUT “提示內(nèi)容1，提示內(nèi)容2，提示內(nèi)容3，”；變量1，變量2，變量3,練一練:請你用輸入語句表達(dá)課本P5和P9頁程序框圖中輸入框中的內(nèi)容,P7頁,INPUT “n=”; n,P9頁,INPUT a, b, c,二.輸出語句,PRINT “提示內(nèi)容”；表達(dá)式,說明: (1)“提示內(nèi)容”提示用戶輸出什么樣的信息,表 達(dá)式是指程序要輸出的數(shù)據(jù),輸出常量，變量的值和字符串等系統(tǒng)信息。 輸出數(shù)值計(jì)算的結(jié)果,2)輸出語句的用途,輸出語句的一般格式,3)同

10、輸入語句一樣，表達(dá)式前也可以有“提示內(nèi)容,思考:在課本P7頁圖1.1-2程序框圖中的輸出框的內(nèi)容怎樣用輸出語句來表達(dá),參考答案： 輸出框： PRINT “n is a prime number .” PRINT “n is not a prime number.,PRINT “S=”; S,三.賦值語句,1)賦值語句的一般格式,變量表達(dá)式,2)賦值語句的作用是:先計(jì)算出賦值號(hào)右邊表達(dá) 式的值,然后把這個(gè)值賦給左邊的變量,使該變量的 值等于表達(dá)式的值。 (3)賦值語句中的“”稱作賦值號(hào),與數(shù)學(xué)中的等 號(hào)的意義是不同的.賦值號(hào)的左右兩邊不能對換. (4)賦值語句左邊只能是變量名字而不是表達(dá)式, 如

11、:2=x是錯(cuò)誤的;右邊表達(dá)式可以是一個(gè)數(shù)據(jù)、 常量或算式；不能利用賦值語句進(jìn)行代數(shù)式的 演算。（如化簡、因式分解、解方程等） （5）對于一個(gè)變量可以多次賦值,例題解析】 例2：編寫程序，計(jì)算一個(gè)學(xué)生數(shù)學(xué)、語文、 英語三門課的平均成績,分析：先寫出算法，畫出程序框圖，再進(jìn)行編程,結(jié)束,程序框圖,INPUT “Maths,Chinese,English”；a,b,c y=(a+b+c)/3 PRINT “y=”；y END,程序,例3：給一個(gè)變量重復(fù)賦值,程序,A=10 A=A+15 PRINT A END,A的輸出值是多少,分析:此程序給變量A賦了兩次值.A的初值為10,第二次賦值后,初值被“覆

12、蓋”,A的值變?yōu)?5,因此輸出值是25,變式引申:在此程序的基礎(chǔ)上，設(shè)計(jì)一個(gè)程序， 要求最后A的輸出值是30,A=10 A=A+15 PRINT A A=A+5 PRINT A END,程序,例3：給一個(gè)變量重復(fù)賦值,程序,A=10 A=A+15 PRINT A END,例4交換兩個(gè)變量A和B的值,并輸出交換前后 的值,分析：引入一個(gè)中間變量X,將A的值賦予X,又將B 的值賦予A，再將X的值賦予B，從而達(dá)到交換A， B的值.（比如交換裝滿水的兩個(gè)水桶里的水需要 再找一個(gè)空桶,INPUT A INPUT B PRINT A，B X=A A=B B=X PRINT A，B END,程序,不能,練習(xí)

13、1:編寫一個(gè)程序,要求輸入一個(gè)圓的半徑, 便能輸出該圓的周長和面積.（ 取3.14,分析:設(shè)圓的半徑為R,則圓的周長C=2R,面積S=R2,可以利用順序結(jié)構(gòu)中的INPUT語句,PRINT語句和賦值語句設(shè)計(jì)程序,INPUT “R=”；R C=2*3.14*R S=3.14*R2 PRINT “C=”；C PRINT “S=”； S END,算法中的條件結(jié)構(gòu)是由條件語句來表達(dá)的,條件語句是處理?xiàng)l件分支邏輯結(jié)構(gòu)的算法語句,條件語句的一般格式,只含一個(gè)“分支”的條件結(jié)構(gòu),寫成條件語句為,當(dāng)計(jì)算機(jī)執(zhí)行這種形式的條件語句時(shí)，首先對IF后的條件進(jìn)行判斷，如果條件符合，就執(zhí)行THEN后的語句體，否則執(zhí)行END

14、 IF之后的語句,含兩個(gè)“分支”的條件結(jié)構(gòu),寫成條件語句為,當(dāng)計(jì)算機(jī)執(zhí)行上述語句時(shí)，首先對IF后的條件進(jìn)行判斷，如果條件符合，就執(zhí)行THEN后的語句體1，否則執(zhí)行ELSE后的語句體2,條件語句的作用 在程序執(zhí)行過程中，根據(jù)判斷是否滿足約定的條件而決定是否需要轉(zhuǎn)換到何處去。需要計(jì)算機(jī)按條件進(jìn)行分析、比較、判斷，并按判斷后的不同情況進(jìn)行不同的處理,1、編寫一個(gè)程序，求任意實(shí)數(shù)的絕對值,程序如下,程序框圖,開始,y=-x,y=x,輸出 y,結(jié)束,x0,是,否,例題解析,例題解析,例6：編寫程序，輸入一元二次方程ax2+bx+c=0的系數(shù)，輸出它的實(shí)數(shù)根,算法分析,一元二次方程的根有三種不同情況,設(shè)判

15、別式=b2-4ac,1)當(dāng)0時(shí),一元二次方程有兩個(gè)不等的實(shí)數(shù)根,2)當(dāng)=0時(shí),一元二次方程有兩個(gè)相等的實(shí)數(shù)根,3)當(dāng)0時(shí),一元二次方程沒有實(shí)數(shù)根,程序,INPUT “ a，b，c =”;a，b，c d=b*b-4*a*c IF d=0 THEN p=-b/(2*a) q=SQR(d)/(2*a) IF d=0 THEN PRINT “One real root:”；p ELSE x1=p+q x2=p-q PRINT “Two real roots:“；x1,x2 END IF ELSE PRINT “No real root!” END IF END,例7：編寫程序，使得任意輸入的3個(gè)整數(shù)按

16、從大到小的順序輸出,算法分析：用a，b，c表示輸入的3個(gè)整數(shù)；為了節(jié)約變量，把它們重新排列后，仍用a，b，c表示，并使abc.具體操作步驟如下。 第一步：輸入3個(gè)整數(shù)a，b，c. 第二步：將a與b比較，并把小者賦給b，大者賦給a. 第三步：將a與c比較. 并把小者賦給c，大者賦給a，此時(shí)a已是三者中最大的。 第四步：將b與c比較，并把小者賦給c，大者賦給b，此時(shí)a，b，c已按從大到小的順序排列好。 第五步：按順序輸出a，b，c,程序,INPUT “a，b，c =”;a，b，c IF ba THEN t=a a=b b=t END IF IF ca THEN t=a a=c c=t END IF

17、,IF cb THEN t=b b=c c=t END IF PRINT a，b，c END,算法中的循環(huán)結(jié)構(gòu)是由循環(huán)語句來實(shí)現(xiàn)的,循環(huán)結(jié)構(gòu)有兩種-當(dāng)型與直到型,當(dāng)型循環(huán)結(jié)構(gòu)(當(dāng)條件滿足時(shí)反復(fù)執(zhí)行循環(huán)體,直到型循環(huán)結(jié)構(gòu)(反復(fù)執(zhí)行循環(huán)體直到條件滿足,對應(yīng)于程序框圖中的兩種循環(huán)結(jié)構(gòu)，一般程序設(shè)計(jì)語言中也有當(dāng)型（WHILE型）和直到型（UNTIL型）兩種語句結(jié)構(gòu),即WHILE語句和UNTIL語句,1)WHILE語句的一般格式是,WHILE 條件 循環(huán)體 WEND,其中循環(huán)體是由計(jì)算機(jī)反復(fù)執(zhí)行的一組語句構(gòu)成的。WHLIE后面的“條件”是用于控制計(jì)算機(jī)執(zhí)行循環(huán)體或跳出循環(huán)體的,WHILE當(dāng) 時(shí)候,WEN

18、D朝方向 行走,1)WHILE語句的一般格式是,WHILE 條件 循環(huán)體 WEND,當(dāng)計(jì)算機(jī)遇到WHILE語句時(shí), 先判斷條件的真假,如果條件 符合,就執(zhí)行WHILE與WEND之間的循環(huán)體;然后再檢查上述條件,如果條件仍符合,再次執(zhí)行循環(huán)體,這個(gè)過程反復(fù)進(jìn)行,直到某一次條件不符合為止.這時(shí),計(jì)算機(jī)將不執(zhí)行循環(huán)體,直接跳到WEND語句后,接著執(zhí)行WEND之后的語句,2)UNTIL語句的一般格式是,DO 循環(huán)體 LOOP UNTIL 條件,DO做什么,LOOP UNTIL繞環(huán)回線走,直到達(dá)到某種 條件為止,思考:參照其直到型循環(huán)結(jié)構(gòu)對應(yīng)的程序框圖,說說 計(jì)算機(jī)是按怎樣的順序執(zhí)行UNTIL語句的,2

19、)UNTIL語句的一般格式是,DO 循環(huán)體 LOOP UNTIL 條件,從UNTIL型循環(huán)結(jié)構(gòu)分析,計(jì)算機(jī)執(zhí)行該語句時(shí),先 執(zhí)行一次循環(huán)體,然后進(jìn)行條件的判斷,如果條件不 滿足,繼續(xù)返回執(zhí)行循環(huán)體,然后再進(jìn)行條件的判斷, 這個(gè)過程反復(fù)進(jìn)行,直到某一次條件滿足時(shí),不再執(zhí) 行循環(huán)體,跳到LOOP UNTIL語句后執(zhí)行其他語句, 是先執(zhí)行循環(huán)體后進(jìn)行條件判斷的循環(huán)語句,提問:通過對照,大家覺得WHILE型語句與UNTIL型 語句之間有什么區(qū)別呢,區(qū)別：在WHILE語句中,是當(dāng)條件滿足時(shí)執(zhí)行循環(huán) 體,而在UNTIL語句中,是當(dāng)條件不滿足時(shí)執(zhí)行循環(huán) 體,例1.編寫程序, 計(jì)算自然數(shù)1+2+3+99+10

20、0的和,分析:這是一個(gè)累加問題.我們可以用WHILE型語句,也可以用UNTIL型語句,i=1 S=0,WHLIE i=100,S=S+i,i=i+1,WEND,PRINT S,END,i=1 S=0,DO,S=S+i i=i+1,LOOP UNTIL,i100,PRINT S,END,變式訓(xùn)練(1): 編寫程序求:n!=12345n的值,如何修改,WHILE語句,i=1 S=0,WHLIE i=100,S=S+i,i=i+1,WEND,PRINT S,END,INPUT “n=”;n,S=1,S=Si,in,S=1,n,S=Si,變式訓(xùn)練(2): 編寫程序求:1357101的值,如何修改,UN

21、ITL語句,i=1 S=0,DO,S=S+i,i=i+1,LOOP UNTIL i100,PRINT S,END,S=1,101,S=Si,i=i+2,直到型,S=1,S=Si,i=i+2,i101,算法案例,1.3,輾轉(zhuǎn)相除法更相減損術(shù),1.1.1,1、求兩個(gè)正整數(shù)的最大公約數(shù),1）求25和35的最大公約數(shù) （2）求225和135的最大公約數(shù),2、求8251和6105的最大公約數(shù),所以，25和35的最大公約數(shù)為5,所以，225和135的最大公約數(shù)為533=45,課前復(fù)習(xí),3,15,9,知識(shí)回顧：先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來,3,3,5

22、,輾轉(zhuǎn)相除法（歐幾里得算法,觀察用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)的過程,第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146,結(jié)論： 8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了,第二步 對6105和2146重復(fù)第一步的做法6105=21462+1813同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù),思考：從上述的過程你體會(huì)到了什么,完整的過程,8251=61051+2146,6105=21462+1813,2146=18131+333,181

23、3=3335+148,333=1482+37,148=374+0,例2 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù),225=1351+90,135=901+45,90=452,顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù),顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù),思考1：從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么,S1：用大數(shù)除以小數(shù),S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù),S3：重復(fù)S1，直到余數(shù)為0,第一步,給定兩個(gè)正數(shù)m、n 第二步,計(jì)算m除以n所得到余數(shù)r 第三步,m=n；n=r 第四步,若r=0,則m、n的最大公約數(shù)等于m; 否則返回第二

24、步,輾轉(zhuǎn)相除法求最大公約數(shù)算法,輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu),否,開始,輸入兩個(gè)正數(shù)m,n,mn,r=m MOD n,r0,輸出n,結(jié)束,m=x,m=n,n=r,否,是,是,x=n,n=m,更相減損術(shù),算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之,第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是，則執(zhí)行第二步,第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)或這個(gè)等數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù),

25、例1、用更相減損術(shù)求98與63的最大公約數(shù),解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減,即：986335; 633528; 35287; 28721; 21714; 1477,所以，98與63的最大公約數(shù)是7,二者算理相似，有異曲同工之妙 1、都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。 2、從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到（差為0,輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別,秦九韶算法,1.3.2,問題1設(shè)計(jì)求

26、多項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時(shí)的值的算法,并寫出程序,點(diǎn)評(píng):上述算法一共做了15次乘法運(yùn)算,5次加法運(yùn)算.優(yōu)點(diǎn)是簡單,易懂;缺點(diǎn)是不通用,不能解決任意多項(xiàng)多求值問題,而且計(jì)算效率不高,這析計(jì)算上述多項(xiàng)式的值,一共需要9次乘法運(yùn)算,5次加法運(yùn)算,問題2有沒有更高效的算法,分析:計(jì)算x的冪時(shí),可以利用前面的計(jì)算結(jié)果,以減少計(jì)算量,即先計(jì)算x2,然后依次計(jì)算,的值,第二種做法與第一種做法相比,乘法的運(yùn)算次數(shù)減少了,因而能提高運(yùn)算效率.而且對于計(jì)算機(jī)來說,做一次乘法所需的運(yùn)算時(shí)間比做一次加法要長得多,因此第二種做法能更快地得到結(jié)果,問題3能否探索更好的算法,來解決任

27、意多項(xiàng)式的求值問題,f(x)=2x5-5x4-4x3+3x2-6x+7 =(2x4-5x3-4x2+3x-6)x+7 =(2x3-5x2-4x+3)x-6)x+7 =(2x2-5x-4)x+3)x-6)x+7 =(2x-5)x-4)x+3)x-6)x+7,v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677,這種求多項(xiàng)式值的方法就叫秦九韶算法,f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0,我們可以改寫成如下形式,求多項(xiàng)式的值時(shí),

28、首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值,即,v1=anx+an-1,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即,一般地,對于一個(gè)n次多項(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)式的值.這種算法稱為秦九韶算法,f(x)=(anx+an-1)x+an-2)x+a1)x+a0,秦九韶算法,點(diǎn)評(píng):秦九韶算法是求一元多項(xiàng)式的值的一種方法. 它的特點(diǎn)是:把求一個(gè)n次多項(xiàng)式的值轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值,通過這種轉(zhuǎn)化,把運(yùn)算的次數(shù)由至多n(n+1)/2次乘法運(yùn)算和n次加法運(yùn)算,減少為n次乘法運(yùn)算和n次加法運(yùn)算,大大提高了運(yùn)算效率

29、,v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3,vn=vn-1x+a0,觀察上述秦九韶算法中的n個(gè)一次式,可見vk的計(jì)算要用到vk-1的值,若令v0=an,得,這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟,因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn),問題畫出程序框圖,表示用秦九韶算法求5次多項(xiàng)式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0當(dāng)x=x0 (x0是任意實(shí)數(shù))時(shí)的值的過程,然后寫出程序,算法步驟如下： 第一步，輸入多項(xiàng)式次數(shù)n、最高次項(xiàng)的系數(shù)an和x的值. 第二步，將v的值初始化為an，將i的值初始化為n-1. 第三步，輸入i次項(xiàng)的系數(shù)ai. 第四步，v=vx+ai，i

30、=i-1. 第五步，判斷i是否大于或等于0，若是，則返回第三步；否則，輸出多項(xiàng)式的值v,否,程序框圖,開始,輸入n,an,x的值,i0,i=n-1,v=an,v=vx+ai,i=i-1,輸出v,結(jié)束,是,輸入ai,進(jìn)位制,1.3.3,問題1我們常見的數(shù)字都是十進(jìn)制的,但是并不是生活中的每一種數(shù)字都是十進(jìn)制的.比如時(shí)間和角度的單位用六十進(jìn)位制,電子計(jì)算機(jī)用的是二進(jìn)制.那么什么是進(jìn)位制?不同的進(jìn)位制之間又有什么聯(lián)系呢,進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算的方便而約定的一種記數(shù)系統(tǒng)，約定滿二進(jìn)一,就是二進(jìn)制;滿十進(jìn)一,就是十進(jìn)制;滿十六進(jìn)一,就是十六進(jìn)制;等等,滿幾進(jìn)一”,就是幾進(jìn)制,幾進(jìn)制的基數(shù)就是幾,可使

31、用數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù).基數(shù)都是大于1的整數(shù),例如：二進(jìn)制可使用的數(shù)字有0和1,基數(shù)是2; 十進(jìn)制可使用的數(shù)字有0,1,2,8,9等十個(gè)數(shù)字,基數(shù)是10; 十六進(jìn)制可使用的數(shù)字或符號(hào)有09等10個(gè)數(shù)字以及AF等6個(gè)字母(規(guī)定字母AF對應(yīng)1015),十六進(jìn)制的基數(shù)是16,注意:為了區(qū)分不同的進(jìn)位制,常在數(shù)字的右下腳標(biāo)明基數(shù),如111001(2)表示二進(jìn)制數(shù),34(5)表示5進(jìn)制數(shù),十進(jìn)制數(shù)一般不標(biāo)注基數(shù),問題2十進(jìn)制數(shù)3721中的3表示3個(gè)千,7表示7個(gè)百,2表示2個(gè)十,1表示1個(gè)一,從而它可以寫成下面的形式,3721=3103+7102+2101+1100,想一想二進(jìn)制數(shù)1011(2)可以類

32、似的寫成什么形式,1011(2)=123+022+121+120,同理,3421(5)=353+452+251+150,C7A16(16)=12164+7163+10162 +1161+6160,一般地,若k是一個(gè)大于1的整數(shù),那么以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式,anan-1a1a0(k) (0ank,0an-1,a1,a0k,意思是:(1)第一個(gè)數(shù)字an不能等于0; (2)每一個(gè)數(shù)字an,an-1,a1,a0都須小于k,k進(jìn)制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)k的冪的乘積之和的形式,即,anan-1a1a0(k)=ankn+an-1kn-1 +a1k1+a0k0,注意

33、這是一個(gè)n+1位數(shù),問題3二進(jìn)制只用0和1兩個(gè)數(shù)字,這正好與電路的通和斷兩種狀態(tài)相對應(yīng),因此計(jì)算機(jī)內(nèi)部都使用二進(jìn)制.計(jì)算機(jī)在進(jìn)行數(shù)的運(yùn)算時(shí),先把接受到的數(shù)轉(zhuǎn)化成二進(jìn)制數(shù)進(jìn)行運(yùn)算,再把運(yùn)算結(jié)果轉(zhuǎn)化為十進(jìn)制數(shù)輸出.那么二進(jìn)制數(shù)與十進(jìn)制數(shù)之間是如何轉(zhuǎn)化的呢,例1:把二進(jìn)制數(shù)110011(2)化為十進(jìn)制數(shù),分析:先把二進(jìn)制數(shù)寫成不同位上數(shù)字與2的冪的乘積之和的形式,再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計(jì)算出結(jié)果,解:110011(2)=125+124+023+022+121+120=132+116+12+1=51,問題4你會(huì)把三進(jìn)制數(shù)10221(3)化為十進(jìn)制數(shù)嗎,解:10221(3)=134+033+232+231+130 =81+18+6+1=106,總結(jié)： k進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)的方法,先把k進(jìn)制的數(shù)表示成不同位上數(shù)字與基數(shù)k的冪的乘積之和的形式,即,anan-1a1a0(k) =ankn+an-1kn-1+a1k1+a0k0,再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計(jì)算出結(jié)果,例 設(shè)計(jì)一個(gè)算法,把k進(jìn)制數(shù)a(共有n位)化為十進(jìn)制數(shù)b,算法步驟如下,開始,輸入a,k,n,b=0,i=1,把a(bǔ)的右數(shù)第i位數(shù)字賦給t,i=i+1,in,輸出b,結(jié)束,否,是,INPUT a,k,n i=1 b=0 t=a MOD 10 DO b=b+t*k(i-1) a=a10