【正文】 速度 ? 算法一：采用遞推循環(huán)的方式實(shí)現(xiàn)類似a**b的計算過程； ? 算法二：采用遞歸方式實(shí)現(xiàn)分治算法： a**b= (a*a)**(b/2) b=偶數(shù) a**b= a*(a**(b1)) b=奇數(shù) 72 分治法的計算效率 ? 以求 520為例，使用分治方法與不使用分治方法的遞歸算法比較，分治法可以節(jié)省近三分之二時間 73 分治方法乘冪運(yùn)算 流程圖 74 回溯策略 ? 如果問題的規(guī)模（數(shù)量）是按指數(shù)速度增加的，那么這些算法的能力將受到一定的限制 ? 在這種情況下，回溯法（ Backtracking）也許是一個更好的選擇 ? 回溯法也叫窮盡搜索法（ BruteForce Search），其基本思想是嘗試分步地去解決一個問題 75 ? 現(xiàn)有 n種物品，對 1=i=n，已知第 i種物品的重量為正整數(shù) Wi，價值為正整數(shù) Vi，背包能承受的最大載重量為正整數(shù) W ? 現(xiàn)要求找出這 n種物品的一個子集，使得子集中物品的總重量不超過 W且總價值盡量大 01背包問題的數(shù)學(xué)描述 )(m a x)()1}(1,0{11?????????????niiiiniiixvnixWxw76 ? 設(shè)有物件 n項(xiàng)，重量為 w(5,3,2), 價值 v(9,7,8)，如果背包只能裝 5斤，求可以放背包的物品最大價值。根據(jù)組合的性質(zhì)有如下公式成立： 1. C(n， m) = n!/(m!*(nm)!) ? 但： 13！ 是 6227020800會超出 32位機(jī)的字長 48 組合計算 ? 另， 用 C(n， m)表示從 n個元素中取出 m個元素的不同組合數(shù)，也可使用遞歸的形式定義： ? 2. C(n， m) = C(n1， m) + C(n1， m1) 49 求 n個數(shù)中取 m個數(shù)的所能產(chǎn)生組合形式的數(shù)量 ? 根據(jù)組合的遞歸形式的數(shù)學(xué)定義：公式（ 2）可知，從從 n個元素中取出 m個元素的基本案例和遞歸案例分別為： ? m=n， c=1 ? m=1， c=n ? mn ， c= C(n1， m) + C(n1， m1) 50 遞歸實(shí)現(xiàn) 組合數(shù) 51 迭代法 ? 迭代是數(shù)值計算中通過從一個初始估計出發(fā)尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程 ? 為實(shí)現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法（Iterative Method） 52 一個簡單的代數(shù)方程 ? 三種迭代法 012 ??? xx)(121 ??? nn xx)(111nn xx ???)(11 ??? nn xx53 三種迭代方法的比較 54 測試的目的 ? 迭代法是數(shù)值計算中求解非線性方程的基本思想方法，其構(gòu)造方法可以有多種多樣 ? 關(guān)鍵 —— 使迭代收斂且有較快收斂速度 ? 取定某個初始值，分別計算（ ） ~（ ）迭代結(jié)果，它們的收斂性如何？ ? 對三個迭代法中的某個，取不同的初始值進(jìn)行迭代，結(jié)果如何？ 55 牛頓迭代法求方程解 ? 請用牛頓迭代法（ ）求方程 ? 在區(qū)間 [3,3]上誤差不大于 109的根，分別取初值 X0=, X0=0, X0=1分別進(jìn)行計算，比較它們的迭代次數(shù) 013 ??? xx56 牛頓迭代法基本原理 0))(()()( ????? kkk xxxfxfxf0)( ?? kxf1?kx設(shè) ,令其解為 ,得： )(. . . . )3,2,1,0()( )(1 ????? kxf xfxxkkkk這稱為 f(x)=0的牛頓迭代格式， 給定初值 x0 , 迭代產(chǎn)生數(shù)列： X0， X1， X2,… … …,Xk,… … 57 牛頓迭代法的主要算法語句 ? 迭代語句： ? x1=x0(x0**3x01)/(3*x0**21) ? 決策語句 ? abs(x1x0)10**9 58 牛頓迭代法流程 ? 三個初值 ? 得到同樣的結(jié)果 ? 但迭代次數(shù) 有差異 59 ? End3 基本策略 ? 算法設(shè)計過程中，發(fā)現(xiàn)問題、分析問題及解決問題的思路、步驟與其他學(xué)科中的方法是一致的，就是 尋找規(guī)律 ? 計算機(jī)科學(xué)家在算法研究過程中總結(jié)了一些具有普遍意義的算法策略和一些可循的規(guī)律，能夠幫助我們較快地找到算法 61 基本策略 ? 貪心策略 ? 分治策略 ? 回溯策略 ? 動態(tài)規(guī)劃 ? 將遞歸算法轉(zhuǎn)成非遞歸實(shí)現(xiàn) 62 貪心策略 ? 貪心算法 在對問題求解時，總是做出在當(dāng)前看來是最好的選擇，因此它僅僅是某種意義上的 局部最優(yōu)解 ? 但在相當(dāng)廣泛范圍內(nèi)，對許多問題它能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解 ? “鼠目寸光” 是對貪心算法的最好描述 63 貪心算法的特點(diǎn) ? 以當(dāng)前情況為基礎(chǔ)根據(jù)某個偏好原則作最優(yōu)選擇，而不考慮各種可能的整體情況 ? 省去了為尋找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時間 ? 采用自頂向下 ,以迭代的方法做出相關(guān)的貪心選擇 ? 每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題 64 貪心算法的特點(diǎn) ? 通過每一步貪心選擇 ,可得到問題的一個 局部 最優(yōu)解 ? 但由此得到的全局解卻不一定都是是最優(yōu)的 65 求解數(shù)字三角形 ? 有任意一個數(shù)字三角形，只能自第一層 (頂層 )向下行走 ,且只能走下接的相鄰兩個結(jié)點(diǎn) ? 如第三層的 1只能走第四層的 3或 1 ? 問能否找到一條路徑，使得路徑上的權(quán)值之和最大？ 66 貪心法求解的算法設(shè)計 ? 使用 文件保存 三角形的層數(shù)和所有數(shù)據(jù) ? 描述一個 n層的三角形，需要 (n*（ n+1） )/2個數(shù)據(jù)和一個描述層次的數(shù)據(jù) 。 ? 因此它的計算效率，直接影響與數(shù)論相關(guān)的算法效率 46 一個測素子程序 ? 如何改善測素子程序的效率？ 47 組合計算 ? 計算一些物品在特定條件下分組方法的數(shù)目。 ? 而使用 遞推算法 求 斐波那契 數(shù)列 ，時間復(fù)雜度只是為 O（ n） 44 數(shù)論問題 ? 數(shù)論的本質(zhì)是對素數(shù)性質(zhì)的研究 ? 2022多年前，歐幾里得證明了有無窮個素數(shù)。 fib(n)=fib(n1)+fib(n2) （當(dāng) n1時） 42 斐波那契數(shù)列 的遞歸求解 43 遞歸的辨識 ? 斐波那契遞歸 實(shí)現(xiàn) ，調(diào)用一次產(chǎn)生二個新的遞歸，調(diào)用次數(shù)呈指數(shù)增長，時間復(fù)雜度為 O（ 2n）。 A柱子上按從小到大的順序堆放了 N個盤子，要把所有的盤子從A柱移動到 C柱，移動過程中如下要求： ? 一次只能移動一個盤子； ? 不允許把大盤放在小盤上面； ? 盤子只能放在三根柱子上 38 漢諾塔遞歸求解 ? N個盤子的移動過程分作 3大步： ? 把 A柱上面的 N1個盤子移動到 B柱； ? 把 A柱上剩下的一個盤子移動到 C柱； ? 把 B柱上面的 N1個盤子移動到 C柱； ? 其中 N1個盤子的移動過程又可按同樣的方法分為三大步，這樣就把移動過程轉(zhuǎn)化為一個遞歸的過程，直到最后只剩下一個盤子，按照移動一個盤子的方法移動，遞歸結(jié)束 39 漢諾塔遞歸 main子圖 40 漢諾塔遞歸子程序 41 斐波那契 (Fibonacci)數(shù)列 ? 一 些問題本身是遞歸定義的，但它并不適合用遞歸算法來求解 ? 如斐波那契 (Fibonacci)數(shù)列，它的遞歸定義為：斐波那契數(shù)列為： 0、 ?? ，即： fib(0)=0。當(dāng)然，可以實(shí)驗(yàn)一下，當(dāng) x取負(fù)值時結(jié)果 如何？ ? 這個算法沒有設(shè)計輸入和規(guī)范的輸出界面，例如輸入的提示，輸出內(nèi)容的 量綱 等 21 遞推法 ? 遞推法是利用問題本身所具有的一種遞推關(guān)系求解問題的一種方法 ? 所謂遞推，是指從已知的初始條件出發(fā)，依據(jù)某種遞推關(guān)系，逐次推出所要求的各中間結(jié)果及最后結(jié)果 ? 其中初始條件或是問題本身已經(jīng)給定，或是通過對問題的分析與化簡后確定 22 可遞推求解的問題特點(diǎn) ? 該類 題目一般有以下二個特點(diǎn)： ? 問題可以劃分成多個狀態(tài)； ? 除初始狀態(tài)外，其它各個狀態(tài)都可以用固定的遞推關(guān)系式來表示 ? 在實(shí)際解題中， 該類 題目 一般 不會直接給出遞推關(guān)系式，而是需要通過分析各種狀態(tài)，找出遞推關(guān)系式 23 猴子吃桃問題 ? 小猴子摘桃若干，立即吃了一半還覺得不過癮，又多吃了一個 ； ? 第二天接著吃剩下桃子的一半，仍覺得不過癮又多吃了一個，以后小猴子都是吃剩下的桃子一半多一個； ? 到第 10天小猴子再去吃桃子的時候，看到只剩下一個桃子 ； ? 則小猴子第一天共摘了多少桃子？ 24 遞推問題求解 ? 由題意可以得到 下 表 ： ? 分析后可知，猴子吃桃問題遞推關(guān)系為： ? Sn=1 （當(dāng) n=10時） ? Sn =2（ Sn+1+1）（當(dāng) 1≤ n＜ 10時） ? 在此基礎(chǔ)上，以第 10天的桃數(shù)作為基數(shù)，用以上歸納出來的遞推關(guān)系設(shè)計出一個循環(huán)過程，將第 1天的桃數(shù)推算出來 25 遞推流程圖 ? 為了加強(qiáng)交互性，增加了交互界面，可以輸入不同的天數(shù)進(jìn)行遞推 ? 算法使用了兩個變量，一個用于遞推的循環(huán)控制，另一個保存遞推得到的結(jié)果 ? 注意主要的循環(huán)控制變量是遞減的，與題意設(shè)計完全相同，便于理解?，F(xiàn)在，請編一個算法，算出如何能剛好用一百塊錢買一百只雞 ? 15 蠻力法求解 ? 三種雞的個數(shù)為窮舉對象 ? 分別設(shè)為 x， y， z ? 以三種雞的總數(shù)（ x+y+z）和買雞用去的錢的總數(shù) (x*5+y*3+z/3)為判定條件，窮舉各種雞的個數(shù) ? 由于三種雞的和是固定的，只要窮舉二種雞（ x， y），第三種雞就可以根據(jù)約束條件求得（ z=100xy），這樣就 縮小了窮舉范圍 16 求解流程圖 ? 如果需要解決的問題規(guī)模不大 ? 用蠻力法設(shè)計的算法其速度是可以接受的 17 分段函數(shù) ? 收費(fèi)問題與我們的生活息息相關(guān)，如水費(fèi)問題、電費(fèi)問題、話費(fèi)問題等 ? 這些收費(fèi)問題往往根據(jù)不同的用量，采用不同的收費(fèi)方式 ? 以收費(fèi)為題材的數(shù)學(xué)問題多以分段函數(shù)的形式出現(xiàn) 18 階梯電價問題 ? 為鼓勵節(jié)約用電，某市開始采取按月用電量分段收費(fèi)辦法，某戶居民每月應(yīng)交電費(fèi) y（元）與用電量 x（度）的函數(shù)如下： ? 請設(shè)計上述電費(fèi)的收費(fèi)算法。 10 ? 2end 學(xué)習(xí)目標(biāo) ? 什么是基本算法？ ? 哪些算法在計算問題求解中