算法案例3二分法課件資料講解

算法案例(3)二分法求近似解

現(xiàn)有一商品，價(jià)格在0～8000元之間，采取怎樣的策略才能在較短的時(shí)間內(nèi)猜出正確的答案？第一步：報(bào)“4000”；第二步：若主持人說(shuō)“高了”（說(shuō)明答案在1～4000之間），就報(bào)“2000”，否則（答數(shù)在4000～8000之間）報(bào)“6000”；第三步：重復(fù)第二步的報(bào)數(shù)方法，直至得到正確結(jié)果。如何賦值從第二步算法分析：答案x*肯定在兩個(gè)端點(diǎn)a,b之間，只是這兩個(gè)端點(diǎn)a,b不斷變化，我們可以用賦值的手法使兩個(gè)端點(diǎn)a,b相對(duì)固定,則x*=（a+b）/2例1．寫(xiě)出用二分法求方程x3-x-1=0在區(qū)間[1,1.5]內(nèi)的一個(gè)近似解（誤差不超過(guò)0.001）的一個(gè)算法．算法步驟：S1取[a,b]的中點(diǎn)x0=(a+b)/2,將區(qū)間一分為二；S2若f(x0)=0,則x0就是根；否則判別根x*在x0的左側(cè)還是在右側(cè)；若f(a)*fx0)>0，則x*∈(x0,b),以x0代替a；若f(a)*f(x0)<0，則x*∈(a,x0),以x0代替b；S3若|a-b|<c,計(jì)算終止,此時(shí)x*≈x0，否則轉(zhuǎn)S1流程圖與偽代碼10Renda,b,c20x0←(a+b)/230f(a)←a3-a-140f(x0)←x03-x0-150Iff(x0)=0ThenGoTo12060Iff(a)f(x0)<0Then70b←x080Else90a←x0100EndIf110If|a-b|≧cThenGoTo20120Printx0輸入a,b,c輸出x0b←x0a←x0f(a)←a3-a-1f(x0)←x03-x0-1X0←(a+b)/2|a-b|<cf(a)f(x0)<0f(x0)=0YNYNY數(shù)學(xué)理論用二分法設(shè)計(jì)求方程f(x)＝0的近似根算法的基本步驟：1．確定近似根所在的基礎(chǔ)區(qū)間[a,b]和近似根的精確度c；2.求有根區(qū)間的中點(diǎn),判斷是否滿足精度要求；3．求區(qū)間端點(diǎn)的函數(shù)值，f(a),f(b)4.判斷f(a)f(b)的符號(hào)，改變有根區(qū)間的下限或上限5．循環(huán)求近似根6．輸出根的近似值鞏固運(yùn)用例2將以二分法求方程x2-2＝0的近似根（精確度為0.005）的一個(gè)算法補(bǔ)充完整．解：Sl令f(m)＝x2-2，因?yàn)閒(1)<0，f(2)>0，所以設(shè)x1＝l，x2＝2．S2令m＝

，判斷f(m)是否為0。若是，則m為所求；若否，則繼續(xù)判斷

S3若

，則x1←m；否則令x2←m．S4判定

<0.005是否成立。若是，則x1,x2之間的任意取值均為滿足條什的近似根，若否，則

例3仟意給定一個(gè)大于１的正整數(shù)ｎ，設(shè)計(jì)一個(gè)算法求ｎ的所有因數(shù)．Ｓ１依次以２～（ｎ－１）為除數(shù)去除ｎ，檢查