計(jì)算思維導(dǎo)論（第2版）課件：算法基礎(chǔ)

算法基礎(chǔ)對(duì)算法的認(rèn)識(shí)算法是計(jì)算機(jī)科學(xué)研究的一個(gè)重要領(lǐng)域，也是許多其他計(jì)算機(jī)科學(xué)技術(shù)的基礎(chǔ)。所謂的算法，不只是數(shù)學(xué)，也不限于計(jì)算機(jī)，它是指可復(fù)制的，解決問(wèn)題的一系列步驟?！耙暣a如詩(shī)詞，勿要做無(wú)所謂的堆砌?！薄晾麃啞ざ酄柭↖lyaDorman）“寫(xiě)代碼時(shí)，每次都要告訴自己：最后負(fù)責(zé)維護(hù)代碼的，會(huì)是一個(gè)知道你住在哪的變態(tài)暴力狂?！薄s翰·伍德（JohnWoods）Algorithm問(wèn)題求解發(fā)現(xiàn)問(wèn)題數(shù)學(xué)模型數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)編程實(shí)現(xiàn)231454.1算法和算法描述算法：解決問(wèn)題的方法和步驟數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)組織方式

尼古拉斯·沃斯瑞士蘇黎世大學(xué)Pascal之父數(shù)據(jù)結(jié)構(gòu)

+算法=程序數(shù)據(jù)結(jié)構(gòu)：描述數(shù)據(jù)算法：對(duì)數(shù)據(jù)進(jìn)行操作#include<stdio.h>intmain(){return0;}“程序=數(shù)據(jù)結(jié)構(gòu)+算法”的體現(xiàn)inta,b;scanf(“%d%d”,&a,&b);printf(“%d%d”,a,b);c=a;a=b;b=c;定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)核心之一設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)核心之二設(shè)計(jì)算法偽控制結(jié)構(gòu)基本操作算法要素算術(shù)運(yùn)算關(guān)系運(yùn)算邏輯運(yùn)算數(shù)據(jù)傳輸順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)有窮性確定性輸入輸出可行性算法的特性常量和變量變量是程序運(yùn)行過(guò)程中，取值可以改變的量。它與計(jì)算機(jī)的內(nèi)存單元相對(duì)應(yīng)。通常變量名中只能出現(xiàn)數(shù)字、字母或下劃線，而且變量名的首字符不能是數(shù)字。常量是指程序執(zhí)行過(guò)程中其值不發(fā)生改變的量。例如，數(shù)字、字符串、邏輯性常量True和False。算法描述自然語(yǔ)言描述流程圖描述偽代碼描述020103交換兩個(gè)數(shù)兩碗飯，如何交換？任務(wù)：交換兩個(gè)整數(shù)算法描述：

step1：讀入兩個(gè)非負(fù)整數(shù)a，b的值

step2：將a的值賦值給t

step3：將b的值賦值給a

step4：將t的值賦值給b

step5：輸出a，b的值abt優(yōu)點(diǎn)：簡(jiǎn)單容易缺點(diǎn)：容易產(chǎn)生二義性圖形符號(hào)名稱(chēng)含義起止框表示算法的開(kāi)始或結(jié)束處理框表示處理或運(yùn)算等功能輸入/輸出框表示進(jìn)行輸入/輸出操作判斷框根據(jù)給定的條件是否滿足決定執(zhí)行兩條路徑中的某一條路徑控制流表示算法執(zhí)行的路徑，箭頭代表方向任務(wù)：交換兩個(gè)整數(shù)算法：step1：讀入兩個(gè)非負(fù)整數(shù)a，b的值

step2：將a的值賦值給t

step3：將b的值賦值給a

step4：將t的值賦值給b

step5：輸出a，b的值a=1b=2t=aa=bb=toutputa,b順序結(jié)構(gòu)：傳統(tǒng)流程圖順序結(jié)構(gòu)：N-S流程圖選擇結(jié)構(gòu)：傳統(tǒng)流程圖選擇結(jié)構(gòu)：雙分支N-S流程圖循環(huán)結(jié)構(gòu)：傳統(tǒng)流程圖循環(huán)結(jié)構(gòu)：N-S流程圖運(yùn)算符號(hào)說(shuō)明符號(hào)表示示例賦值符號(hào)←或=a←5，b=5算術(shù)運(yùn)算符號(hào)+、-、*、/、mod（整數(shù)取余）、^（乘方）a+b，amod

b，a^b關(guān)系運(yùn)算符號(hào)>、>=、<、<=、=、<>（不等于）a>b、a<>b邏輯運(yùn)算符號(hào)and（與）、or（或）、not（非）not（a>=banda>0or

a>0）輸入和輸出input、output（或read、print）input

a，output

a選擇結(jié)構(gòu)如果P成立則A否則B：ifPthenAelseBif

A=B

then

AelseB循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)：whilePDoAFor型循環(huán)：fori=初值to

終值[stepn]DoAwhilei<=100dos=s+ii=i+1endwhilefori=1to100s=s+iendfor過(guò)程（函數(shù)）procedureName（）functionName（參數(shù)列表）……endprocedureendfunctionprocedurepi（）functionswap（a，b）arccos(-1)c=aendprocedurea=bb=cendfunction任務(wù)：交換兩個(gè)整數(shù)算法：

step1：讀入兩個(gè)非負(fù)整數(shù)a，b的值

step2：將a的值賦值給t

step3：將b的值賦值給a

step4：將t的值賦值給b

step5：輸出a，b的值//SwapAlgorithminputa,bt=aa=bb=toutputa,b數(shù)組數(shù)組就是一組有序數(shù)據(jù)的集合定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法按照順序排列的一列數(shù)一組有序數(shù)據(jù)的集合數(shù)列數(shù)組等差數(shù)列、擺動(dòng)數(shù)列、……一維數(shù)組、二維數(shù)組、……a1,a2,a3…,an一維數(shù)組：a[1],a[2],……,a[n]所有數(shù)據(jù)同一個(gè)數(shù)據(jù)類(lèi)型所有數(shù)據(jù)同一個(gè)數(shù)據(jù)類(lèi)型數(shù)據(jù)之間有（位置）順序數(shù)據(jù)之間有（位置）順序數(shù)據(jù)從1開(kāi)始計(jì)算下標(biāo)數(shù)據(jù)從0或1開(kāi)始計(jì)算下標(biāo)定義類(lèi)型特點(diǎn)格式找規(guī)律，寫(xiě)通項(xiàng)公式一次輸入，多次使用作用1、下面?zhèn)未a輸出的結(jié)果是：a[5]={1,2,3,4,5}outputa[1]outputa[2]outputa[3+1]outputa[5]12、下列偽代碼輸出的結(jié)果是：a[5]={1,2,3,4,5}s=0fori=1to5s=s+a[i]endforavg=s/5outputavg2453循環(huán)遍歷數(shù)組元素算法分析1）求5個(gè)數(shù)平均值，可以轉(zhuǎn)5圈進(jìn)行累加求和2）哪些數(shù)大于高于平均值呢？

需要再次使用這5個(gè)數(shù)，依次和平均值比較3）需用到數(shù)組，一次輸入，多次使用。任務(wù)：高于平均數(shù)個(gè)數(shù)問(wèn)題求：5個(gè)整數(shù)中大于平均數(shù)的個(gè)數(shù)，寫(xiě)出偽代碼和畫(huà)出流程圖。定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法a[5]=0,s=0,num=0fori=1to5//累加求和求均值inputa[i]s=s+a[i]endforavg=s/5fori=1to5//統(tǒng)計(jì)高于均值個(gè)數(shù)ifa[i]>avgthennum=num+1endifendforoutputnum算法分析1）循環(huán)10圈，求出總分、最高分、最低分。2）總分中減去最高分和最低分。3）求去掉最高分和最低分的平均分。任務(wù)：體育計(jì)分問(wèn)題

10個(gè)評(píng)委給運(yùn)動(dòng)員打分，去掉一個(gè)最高分，去掉一個(gè)最低分，求選手最終得分（去掉最高分最低分后的平均分）。定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法a[10]=0,s=0fori=1to10//輸入且累加求和inputa[i]s=s+a[i]endfors=s-max–min//計(jì)算且輸出均值avg=s/_____outputavgmax=_________//求最大最小值min=a[1]fori=2to10if________________thenmax=a[i]ifa[i]<minthenmin=a[i]endfora[i]>maxa[1]8數(shù)組&循環(huán)數(shù)組作用一次輸入，多次使用數(shù)組示例①統(tǒng)計(jì)高于平均值個(gè)數(shù)②體育計(jì)分問(wèn)題數(shù)組特點(diǎn)相同的數(shù)據(jù)類(lèi)型數(shù)據(jù)之間有順序下標(biāo)從0或1開(kāi)始數(shù)組的訪問(wèn)循環(huán)遍歷數(shù)組元素生活中的數(shù)組①組團(tuán)旅游②統(tǒng)計(jì)購(gòu)物小票③報(bào)菜名34562數(shù)組一組有序數(shù)據(jù)的集合1函數(shù)函數(shù)就是模塊化設(shè)計(jì)將不同功能的函數(shù)搭建在一起構(gòu)成系統(tǒng)定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法類(lèi)型系統(tǒng)預(yù)定義（三角函數(shù)，……）用戶自定義主調(diào)函數(shù)與被調(diào)函數(shù)：A，B兩個(gè)函數(shù)。A函數(shù)調(diào)用了B函數(shù)，A叫做主調(diào)函數(shù)，B叫做被調(diào)函數(shù)。注意事項(xiàng)：（1）函數(shù)名（2）函數(shù)參數(shù)（3）函數(shù)返回值過(guò)程/函數(shù)123456主調(diào)函數(shù)格式：變量=Name（實(shí)參表列）被調(diào)函數(shù)格式：functionName(形參表列)…endfunctionA函數(shù)：…調(diào)用B函數(shù)…B函數(shù)：………1、下面?zhèn)未a輸出的結(jié)果是：

主調(diào)函數(shù)：a=2b=cube(a)outputb

被調(diào)函數(shù)：functioncube(x)returnx^3endfunction2、下列偽代碼輸出的結(jié)果是：

主調(diào)函數(shù)：a=1，b=2c=max（a，b）outputc

被調(diào)函數(shù)：functionmax（x，y）ifx>ythenreturnxelsereturnyendifendfunction28過(guò)程/函數(shù)算法分析怎么用戶自定義函數(shù)呢？1）函數(shù)名oddeven2）函數(shù)參數(shù)：x3）函數(shù)返回值：0/1任務(wù)：奇偶問(wèn)題自定義一個(gè)函數(shù)，功能是判斷一個(gè)整數(shù)是奇數(shù)還是偶數(shù)，請(qǐng)寫(xiě)出流程圖和偽代碼。定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法被調(diào)函數(shù)框架：functionoddeven(x)……endfunction主調(diào)函數(shù)：flag=oddeven(m)主調(diào)函數(shù)：inputmflag=odd_even(m)ifflag=0thenoutput"even"elseoutput"odd"endif被調(diào)函數(shù)：functionodd_even(x)ifxmod2=0thenreturn0elsereturn1endfunction算法分析怎么定義自定義函數(shù)呢？1）函數(shù)名area2）函數(shù)參數(shù)：r3）函數(shù)返回值：s任務(wù)：圓面積問(wèn)題自定義一個(gè)函數(shù)，功能是給定一個(gè)圓的半徑r，求出圓的面積，請(qǐng)寫(xiě)出流程圖和偽代碼。定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法被調(diào)函數(shù)框架：functionarea(r)……endfunction主調(diào)函數(shù)：s=area(r)主調(diào)函數(shù)：inputrs=____________outputs被調(diào)函數(shù)：functionarea(r)returnendfunctionarea(r)3.14*r^2函數(shù)函數(shù)名函數(shù)參數(shù)函數(shù)返回值主調(diào)函數(shù)與被調(diào)函數(shù)主調(diào)函數(shù)：變量=函數(shù)（實(shí)參）被調(diào)函數(shù)：function函數(shù)名（形參）

…endfunction函數(shù)類(lèi)型系統(tǒng)預(yù)定義函數(shù)用戶自定義函數(shù)實(shí)參與形參主調(diào)函數(shù)：實(shí)參被調(diào)函數(shù)：形參生活中的函數(shù)①三角函數(shù)、指數(shù)對(duì)數(shù)函數(shù)②excel函數(shù)③底薪+提成的正比例函數(shù)34562函數(shù)就是模塊化設(shè)計(jì)1時(shí)間復(fù)雜度需要消耗的時(shí)間資源空間復(fù)雜度需要消耗的空間資源正確性：準(zhǔn)確無(wú)誤健壯性：容錯(cuò)力強(qiáng)可讀性：易理解算法的特征有窮性、確定性可行性、輸入和輸出算法描述自然語(yǔ)言、流程圖、偽代碼算法的要素基本操作控制結(jié)構(gòu)發(fā)現(xiàn)算法發(fā)現(xiàn)問(wèn)題、數(shù)學(xué)模型、數(shù)據(jù)結(jié)構(gòu)（數(shù)組等）、算法設(shè)計(jì)、編程實(shí)現(xiàn)（函數(shù)等）算法評(píng)價(jià)時(shí)間復(fù)雜度、空間復(fù)雜度正確性、健壯性、可讀性34562什么是算法？解決問(wèn)題的方法和步驟14.2經(jīng)典算法枚舉法010203040506070809010203040506070809枚舉法貪心算法動(dòng)態(tài)規(guī)劃分治法遞推法遞歸法迭代法查找排序算法策略10回溯法10細(xì)數(shù)一下你身邊的枚舉法找出100以內(nèi)的素?cái)?shù)忘記密碼？配菜方案（一葷一素一飲品）枚舉法：窮舉法、暴力法、蠻力法什么是枚舉法？根據(jù)問(wèn)題的部分條件確定答案的大致范圍，并在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到將全部情況驗(yàn)證完畢。枚舉法的思想枚舉法的設(shè)計(jì)1）找出枚舉范圍2）找出約束條件枚舉法的實(shí)現(xiàn)循環(huán)+條件判斷任務(wù)1：百錢(qián)買(mǎi)百雞雞翁一值錢(qián)五，雞母一值錢(qián)三，雞雛三值錢(qián)一。百錢(qián)買(mǎi)百雞，問(wèn)雞翁、雞母、雞雛各幾何？定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法雞雛三，值錢(qián)一雞翁一值錢(qián)五雞母一值錢(qián)三設(shè)要買(mǎi)x只公雞，y只母雞，z只小雞，列方程：枚舉法的設(shè)計(jì)1）找出枚舉范圍2）找出約束條件算法分析x+y+z=100①5x+3y+z/3=100②x∈[0,20]y∈[0,33]z∈[0,99]約束條件枚舉范圍x=01…20y=01…33z=03…99x∈[0,20]y∈[0,33]z∈[0,99]枚舉范圍指定取值范圍內(nèi)，窮盡所有可能后，選取可行方案的過(guò)程枚舉法的實(shí)現(xiàn)循環(huán)+條件判斷forx=0to20fory=0to33forz=0to99step3ifx+y+z=100and5x+3y+z/3=100thenoutputx,y,zendforendforendfor任務(wù)2：猜字問(wèn)題雨水淋濕了算術(shù)書(shū)的一道題，8個(gè)數(shù)字只能看清3個(gè)，第一個(gè)數(shù)字雖然看不清，但可看出不是1。求其余數(shù)字是什么？[□*(□3+□)]2=8□□9定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法任務(wù)2：猜字問(wèn)題雨水淋濕了算術(shù)書(shū)的一道題，8個(gè)數(shù)字只能看清3個(gè)，第一個(gè)數(shù)字雖然看不清，但可看出不是1。求其余數(shù)字是什么？[□*(□3+□)]2=8□□9定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法1）枚舉范圍：A：2～9B、C：1～9D、E：0～9算法分析2）約束條件：(A*(B*10+3+C))^2=8009+D*100+E*10forA=2to9forB=1to9forC=1to9forD=0to9forE=0to9if(A*(B*10+3+C))^2=8009+D*100+E*10thenoutputA,B,C,D,Eendforendforendforendforendfor枚舉結(jié)構(gòu)特點(diǎn)循環(huán)+選擇適用范圍可能解個(gè)數(shù)不多的情況算法設(shè)計(jì)步驟找出枚舉范圍找出約束條件枚舉優(yōu)缺點(diǎn)優(yōu)點(diǎn)：直觀形象缺點(diǎn)：效率低應(yīng)用舉例①找鑰匙②

驗(yàn)鈔機(jī)驗(yàn)鈔③

品酒員品酒34562枚舉的概念一一列舉，逐個(gè)檢驗(yàn)1遞推法如何求等差數(shù)列、等比數(shù)列的通項(xiàng)、以及數(shù)列和？1）1,3,5,7,9,11,…,？2)1,3,9,27,81,…,？（1）等差：通項(xiàng)：an=a1+（n-1）*d=2n-1求和：S=(a1+an)*n/2=n^2（2）等比：通項(xiàng)：an=a1*q^(n-1)=1*3^(n-1)=3^(n-1)求和：S=a1*(1-q^n)/(1-q)=1*(1-3^n)/(1-3)=-（1-3^n）/2方法：通項(xiàng)公式與求和公式切0刀——1塊切1刀——2塊切2刀——4塊切3刀——7塊切4刀——11塊?你還能找到通項(xiàng)嗎？切蛋糕（垂直切、且要求塊數(shù)最多）你還能找到通項(xiàng)嗎？解決方案：1）相鄰項(xiàng)之間的關(guān)系ai=ai-1+i（第i刀塊數(shù)=上一刀塊數(shù)+本次切的刀數(shù)）切蛋糕（要求塊數(shù)最多）切0刀——1塊切1刀——2塊切2刀——4塊切3刀——7塊切4刀——11塊?2）用迭加法求通項(xiàng)公式a0=1a1=a0+1……+)an=an-1+n-------------------an=1+（1+2+…+n）=1+n*(n+1)/2010203040506070809010203040506070809枚舉法貪心算法動(dòng)態(tài)規(guī)劃分治法遞推法遞歸法迭代法查找排序算法策略10回溯法10從問(wèn)題的規(guī)模（項(xiàng)數(shù)）出發(fā)，找到大規(guī)模問(wèn)題與小規(guī)模問(wèn)題之間的關(guān)系（或前后項(xiàng)之間的關(guān)聯(lián)），然后根據(jù)他們之間的聯(lián)系逐步求解。這種在規(guī)定的初始條件下，找出后項(xiàng)對(duì)前項(xiàng)的依賴(lài)關(guān)系的操作，稱(chēng)為遞推。什么是遞推？遞推公式表示某項(xiàng)和它前面若干項(xiàng)的關(guān)系式就叫遞推公式。邊界條件初始條件稱(chēng)為邊界條件。遞推法設(shè)計(jì)遞推法實(shí)現(xiàn)1）找出遞推規(guī)律，寫(xiě)出遞推公式2）根據(jù)初始條件，順推或逆推1）循環(huán)寫(xiě)入數(shù)組，非遞歸求解2）根據(jù)遞推公式，遞歸求解遞推法分類(lèi)順推和逆推兩種遞推法特點(diǎn)1）問(wèn)題可以劃分成多個(gè)狀態(tài)。2）除初始狀態(tài)外，其它各狀態(tài)都可用固定的遞推關(guān)系式來(lái)表示。任務(wù)：兔子繁殖問(wèn)題這是一個(gè)古典數(shù)學(xué)問(wèn)題：有一對(duì)兔子，從出生后第3個(gè)月起每個(gè)月都生一對(duì)兔子，小兔子長(zhǎng)到第3個(gè)月后每個(gè)月又生一對(duì)兔子。假設(shè)所有的兔子不死，問(wèn)第20月兔子總數(shù)為多少？定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法任務(wù)：兔子繁殖問(wèn)題算法分析月數(shù)小兔子對(duì)數(shù)中兔子對(duì)數(shù)老兔子對(duì)數(shù)兔子總數(shù)110012010131012411135212563238……………定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法任務(wù)：兔子繁殖問(wèn)題算法分析這就是著名的斐波那契數(shù)列。1,1,2,3,5,8,13,…遞推法設(shè)計(jì)1）找出遞推規(guī)律，寫(xiě)出遞推公式2）根據(jù)初始條件，順推或逆推遞推式：an=an-1+an-2初始條件：a1=1，a2=1a[20]=0,a[1]=1,a[2]=1inputnfori=3tona[i]=a[i-1]+a[i-2]endforoutputa[n]設(shè)f(n)函數(shù)求Fibonacci遞歸式：f(n)=f(n-1)+f(n-2)遞歸出口：n=2orn=1界函數(shù)：f(n-1),f(n-2)非遞歸實(shí)現(xiàn)遞歸實(shí)現(xiàn)被調(diào)函數(shù)functionf(n)ifn=2orn=1thenreturn1elsereturnf(n-1)+f(n-2)endifendfunction主調(diào)函數(shù)inputnf=f(n)outputf遞推式：an=an-1+an-2初始條件：a1=1，a2=1任務(wù)：猴子吃桃子猴子第一天摘下若干個(gè)桃子，當(dāng)即吃下了一半，還不過(guò)癮，有多吃了一個(gè)。第2天早上又將剩下的桃子吃掉了一半，又多吃了一個(gè)。以后每天早上都吃了前一天剩下的一半零一個(gè)。到第10天早上想再吃時(shí)，就只剩下一個(gè)桃子了。求第1天共摘了多少個(gè)桃子？定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法任務(wù)：猴子吃桃子算法分析天數(shù)桃子數(shù)量10194810722…1?遞推法設(shè)計(jì)1）找出遞推規(guī)律，寫(xiě)出遞推公式2）根據(jù)初始條件，順推或逆推遞推式：an-1=(an+1)*2初始條件：a10=1設(shè)monkey(n,f)函數(shù)求第n天吃桃數(shù)量f遞推式：monkey(n,f)=monkey(n-1,2*(f+1))遞歸出口：n>1界函數(shù)：monkey(n-1,2*(f+1))被調(diào)函數(shù)：functionmonkey(n,f)ifn>1thenf=2*(f+1)monkey(n-1,f)endifendfunctiona[10]=1i=10whilei>=2doa[i-1]=2*(a[i]+1)i=i-1endwhileoutputa[1]遞推式：an-1=(an+1)*2初始條件：a10=1主調(diào)函數(shù)：f=1monkey(10,f)outputf非遞歸實(shí)現(xiàn)遞歸實(shí)現(xiàn)算法設(shè)計(jì)步驟寫(xiě)遞推公式順推或逆推遞推優(yōu)缺點(diǎn)優(yōu)點(diǎn)：可避開(kāi)求通項(xiàng)公式的麻煩缺點(diǎn)：遞推公式固定遞推特點(diǎn)問(wèn)題可劃分為多個(gè)狀態(tài)，除初始狀態(tài)外，其他均可寫(xiě)遞推公式遞推實(shí)現(xiàn)①循環(huán)+數(shù)組②遞歸調(diào)用應(yīng)用舉例①猜年齡②

碟中諜、案中案、

環(huán)環(huán)相扣34562遞推的概念前項(xiàng)后項(xiàng)有特定關(guān)系1遞歸法細(xì)數(shù)一下你身邊的遞歸法文字遞歸分形圖形德羅斯特效應(yīng)010203040506070809010203040506070809枚舉法貪心算法動(dòng)態(tài)規(guī)劃分治法遞推法遞歸法迭代法查找排序算法策略10回溯法10什么是遞歸？遞推+回溯遞歸法的思想在調(diào)用一個(gè)函數(shù)的過(guò)程中又出現(xiàn)直接或間接地調(diào)用該函數(shù)本身，稱(chēng)為函數(shù)的遞歸調(diào)用。如：sin(sin(30*pi()/180))遞歸法的設(shè)計(jì)遞歸法的實(shí)現(xiàn)1）縮小規(guī)模：將原問(wèn)題轉(zhuǎn)換為性質(zhì)相似的獨(dú)立子問(wèn)題2）遞歸出口：有遞歸終止的條件遞歸法三要素條件判斷+函數(shù)調(diào)用1）遞歸式：遞歸公式，或遞歸函數(shù)2）遞歸出口：遞歸終止條件3）界函數(shù)：?jiǎn)栴}規(guī)模變化的函數(shù)，保證遞歸規(guī)模向出口靠攏，

類(lèi)似循環(huán)中的步長(zhǎng)。functiontell_story()

if(講話被打斷)then

故事結(jié)束;else

從前有座山;……;

tell_story();

endifendfunction遞歸出口遞歸式任務(wù)1：求自然數(shù)n的階乘一個(gè)正整數(shù)的階乘是所有小于及等于該數(shù)的正整數(shù)的積，并且0的階乘為1。定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法數(shù)學(xué)定義：n！=1*2*3*……(n-1)*nn！=n*(n-1)!遞歸法的設(shè)計(jì)1）縮小規(guī)模：獨(dú)立的相似子問(wèn)題2）遞歸出口：遞歸結(jié)束算法分析以n=4為例fact(4)=4*fact(3)fact(3)=3*fact(2)fact(2)=2*fact(1)fact(1)=1fact(1)=1fact(2)=2fact(3)=6fact(4)=24遞推回溯遞歸出口縮小規(guī)模主調(diào)函數(shù)：inputnoutputfact(n)被調(diào)函數(shù)：functionfact(n)ifn=1thenreturn1elsereurnn*fact(n-1)endifendfunction任務(wù)2：走樓梯問(wèn)題小明走路喜歡蹦蹦跳跳，他最喜歡在樓梯上跳來(lái)跳去。但年幼的他一次只能走上一階或者一下子蹦上兩階?，F(xiàn)在一共有N階臺(tái)階，請(qǐng)你計(jì)算一下小明從第0階到第N階共有幾種走法？定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法算法分析設(shè)f(n)為小明上樓梯的走法當(dāng)n=1時(shí)，1種走法當(dāng)n=2時(shí)，2種走法f(n)=f(n-1)+f(n-2)n級(jí)臺(tái)階的走法=先走一級(jí)后，n-1級(jí)臺(tái)階的走法+先走兩級(jí)后，n-2級(jí)臺(tái)階的走法遞推法（數(shù)組實(shí)現(xiàn)）：

a[10]={1,2}fori=3to10step1a[i]=a[i-1]+a[i-2]endfor主調(diào)函數(shù)：inputnoutputf(n)被調(diào)函數(shù)：

functionf(n)ifn=1thenreturn1elseifn=2thenreturn2elsereurnf(n)=f(n-1)+f(n-2)endifendfunction遞歸三要素遞歸式遞歸出口界函數(shù)遞歸優(yōu)缺點(diǎn)優(yōu)點(diǎn)：容易理解缺點(diǎn)：時(shí)空代價(jià)大算法設(shè)計(jì)步驟縮小規(guī)模找出遞歸出口遞歸實(shí)現(xiàn)遞歸調(diào)用+條件判斷應(yīng)用舉例①繁衍生息（分形）②

購(gòu)物返券③

冤冤相報(bào)何時(shí)了34562遞歸的概念和特點(diǎn)一一遞推，回溯1迭代法細(xì)數(shù)你身邊的迭代…版本升級(jí)長(zhǎng)江后浪推前浪，一代新人換舊人010203040506070809010203040506070809枚舉法貪心算法動(dòng)態(tài)規(guī)劃分治法遞推法遞歸法迭代法查找排序算法策略10回溯法10迭代法也稱(chēng)輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過(guò)程，跟迭代法相對(duì)應(yīng)的是直接法，即一次性解決問(wèn)題。什么是迭代法？迭代法設(shè)計(jì)迭代法實(shí)現(xiàn)1）循環(huán)結(jié)構(gòu)2）要有循環(huán)迭代終止條件1）循環(huán)+變量的值替換2）遞歸求解迭代法特點(diǎn)輾轉(zhuǎn)特性（即翻來(lái)覆去地用變量的舊值遞推出新的值，新值隨即變成舊值）任務(wù)：最大公約數(shù)問(wèn)題

請(qǐng)用輾轉(zhuǎn)相除法求兩自然數(shù)m，n的最大公約數(shù)是多少？定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法算法分析設(shè)m=14，n=6，最大公約數(shù)為2輾轉(zhuǎn)相除法mnr1462620146273算法描述非遞歸實(shí)現(xiàn)inputm,nifm<nthent=m,m=n,n=tendifr=mmodnwhiler<>0dom=nn=rr=mmodnendwhileoutputn遞歸實(shí)現(xiàn)設(shè)gcd(m,n)函數(shù)遞歸式：gcd(m,n)遞歸出口：r=0界函數(shù)：gcd(n,r)主調(diào)函數(shù)：inputm,nifm<nthent=m,m=n,n=tendifgcd(m,n)被調(diào)函數(shù)：functiongcd(m,n)r=mmodnifr=0thenoutputnelsegcd(n,r)endifendfunction非遞歸實(shí)現(xiàn)任務(wù)：兔子繁殖問(wèn)題

請(qǐng)用迭代法求解斐波那契數(shù)列的前20項(xiàng)定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法算法分析1,1,2,3,5,8,13,21,34,55,…設(shè)f1=1,f2=1f1=f1+f2=2f2=f1+f2=3…f1=1f2=1outputf1,f2i=1whilei<10dof1=f1+f2f2=f1+f2outputf1,f2i=i+1endwhile定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法迭代法設(shè)計(jì)迭代法實(shí)現(xiàn)1）循環(huán)迭代2）要有迭代終止條件1）循環(huán)2）遞歸求解迭代算法的設(shè)計(jì)循環(huán)結(jié)構(gòu)有迭代終止的條件迭代優(yōu)缺點(diǎn)優(yōu)點(diǎn)：解決收斂問(wèn)題的方法缺點(diǎn)：迭代次數(shù)可能過(guò)多，開(kāi)銷(xiāo)大迭代特點(diǎn)輾轉(zhuǎn)特性（翻來(lái)覆去舊值換新值）迭代的實(shí)現(xiàn)①循環(huán)（非遞歸）②遞歸應(yīng)用舉例①家電以舊換新②

長(zhǎng)江后浪推前浪34562迭代的概念舊值遞推新值1查找法細(xì)數(shù)一下你身邊的查找青玉案?元夕?辛棄疾李彥宏?百度總裁010203040506070809010203040506070809枚舉法貪心算法動(dòng)態(tài)規(guī)劃分治法遞推法遞歸法迭代法查找排序算法策略10回溯法10線性查找：枚舉法折半查找：分治法任務(wù)1：查找（線性查找）

現(xiàn)有6個(gè)數(shù)，要求用線性查找法，查找數(shù)字6，如果該數(shù)不在列表中，則輸出"無(wú)此數(shù)"。定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法264754遍歷=枚舉6算法分析：算法描述：定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法inputa[6]={2,6,4,7,5,4},i=1fori=1to6ifa[i]=6thenoutput“Findit,itisat"&i&"site.”exitendifendforifi>6thenoutput"NotFindit."查找技術(shù)任務(wù)2：查找（折半查找）

現(xiàn)有6個(gè)數(shù)，要求用線性查找法，查找數(shù)字6，如果該數(shù)不在列表中，則輸出"無(wú)此數(shù)"。定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法264754折半=分治算法分析：定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法1）對(duì)數(shù)據(jù)排序。264754244567244567topmidbottom62）設(shè)置bottom=1，top=6。3）設(shè)置mid=(1+6)/2=34）bottom=mid+1，top=6244567bottomtopmid算法描述：定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法inputa[6]={2,6,4,7,5,4}，bottom=1，top=6sortamid=(bottom+top)/2whilebottom<=topdoifa[mid]=a[des]thenoutputa[mid]elseifa[des]<a[mid]thentop=mid-1elsebottom=mid+1endifendwhile查找技術(shù)查找算法線性查找折半查找查找策略線性=枚舉折半=分治排序算法010203040506070809010203040506070809枚舉法貪心算法動(dòng)態(tài)規(guī)劃分治法遞推法遞歸法迭代法查找排序算法策略10回溯法10排序前排序后比較元素大小改變?cè)匚恢?2AdjustCompare排序技術(shù)快速排序法冒泡排序法選擇排序法比較排序法插入排序法歸并排序希爾排序……選擇法冒泡法插入法部分有序空位移動(dòng)插入被標(biāo)記的隊(duì)員歸并算法打撲克時(shí)，你用到哪些排序？任務(wù)：冒泡排序

現(xiàn)有6個(gè)數(shù)，要求用冒泡排序法進(jìn)行排序。排序過(guò)程定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法冒泡排序8>6j=1j+1869327大數(shù)沉底小數(shù)上浮i=1任務(wù)：冒泡排序

現(xiàn)有6個(gè)數(shù)，要求用冒泡排序法進(jìn)行排序。排序過(guò)程定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法冒泡排序8<9689327j=2j+1大數(shù)沉底小數(shù)上浮i=1任務(wù)：冒泡排序

現(xiàn)有6個(gè)數(shù)，要求用冒泡排序法進(jìn)行排序。排序過(guò)程定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法冒泡排序9>3689327j=3j+1大數(shù)沉底小數(shù)上浮i=1任務(wù)：冒泡排序

現(xiàn)有6個(gè)數(shù)，要求用冒泡排序法進(jìn)行排序。排序過(guò)程定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法冒泡排序9>2683927j=4j+1大數(shù)沉底小數(shù)上浮i=1任務(wù)：冒泡排序

現(xiàn)有6個(gè)數(shù)，要求用冒泡排序法進(jìn)行排序。排序過(guò)程定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法冒泡排序9>7683297j=5j+1大數(shù)沉底小數(shù)上浮i=1任務(wù)：冒泡排序定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法冒泡排序inputa[6]={8,6,9,3,2,7}fori=1to5forj=1to6-iifa[j]>a[j+1]thent=a[j]a[j]=a[j+1]a[j+1]=tendifendforendforoutputa[6]冒泡排序排序方法比較排序冒泡排序……排序策略大數(shù)沉底、小數(shù)上浮分治法010203040506070809010203040506070809枚舉法貪心算法動(dòng)態(tài)規(guī)劃分治法遞推法遞歸法迭代法查找排序算法策略10回溯法10一口吃不成胖子，但胖子卻是一口一口吃來(lái)的切西瓜凡治眾如治寡，分?jǐn)?shù)是也；斗眾如斗寡，形名是也。十則圍之，五則攻之，倍則分之，敵則能戰(zhàn)之，不若則能避之。孫子兵法“分而治之”就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。什么是分治法？分治分治，要先分，再治，最后合分：把問(wèn)題劃分為子問(wèn)題治：遞歸的求解子問(wèn)題合：把子問(wèn)題的解合并稱(chēng)問(wèn)題的解分治法的步驟functionDivide_Conquer（P）if（P的規(guī)模足夠?。﹖hen

直接求解else

將P分解為P1,P2,…,Pkendiffori=1tokDivide_Conquer（Pi）endforendfunction任務(wù)1：二分求冪計(jì)算機(jī)模擬手工計(jì)算2^159=?定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法手工計(jì)算2^159，怎么計(jì)算？自然是判斷指數(shù)，如果指數(shù)為奇數(shù)，則，2^奇數(shù)冪=2*2^奇數(shù)冪-1，如：2^159=2*2^158，否則，指數(shù)為偶數(shù)冪，2^偶數(shù)冪=4^偶數(shù)冪的一半。如：2^158=（2^2）^79=4^79算法分析求解過(guò)程2^159=？=2*2^158=2*4^79=2*4*4^78=2*(4*16^39)=……=2*(4*(16*256*(256^2)*(256^2^2^2)^2))functionf(x,n)//求x^nifn=1thenreturnxendififnmod2=1thenreturnx*f(x,n-1)elsereturnf(x^2,n/2)endifendfunction流程圖偽代碼任務(wù)2：有假幣16個(gè)硬幣中，混進(jìn)了1枚假幣。現(xiàn)在知道假幣的重量比真幣的質(zhì)量要輕。給你一個(gè)天平，請(qǐng)用最快的時(shí)間把那個(gè)可惡的假幣找出來(lái)。定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法算法分析方法1：枚舉任意取1枚硬幣，與其他硬幣進(jìn)行比較，若發(fā)現(xiàn)輕者，這那枚為偽幣。最多可能有15次比較。算法分析方法2：一次二分法

將硬幣分為8組，每組2個(gè)，每組比較一次，若發(fā)現(xiàn)輕的，則為偽幣。最多可能有8次比較。算法分析方法3：多次二分法①②③④算法分析方法4：三分13-23-12-12-2Inputn=16,t=0whilen>1dot=t+1n=(n+2)/3endwhileoutputt流程圖偽代碼公共子問(wèn)題分久必合最優(yōu)子結(jié)構(gòu)計(jì)算復(fù)雜性問(wèn)題可以分解成若干個(gè)規(guī)模較小的相同子問(wèn)題問(wèn)題的計(jì)算復(fù)雜性一般都是隨著問(wèn)題規(guī)模的增加而增加，問(wèn)題規(guī)?？s小到一定規(guī)模，就可輕易求解了子問(wèn)題的解可以合并為原問(wèn)題的解子問(wèn)題是相互獨(dú)立的，不包含公共子問(wèn)題算法設(shè)計(jì)步驟分解、求解、合成適用范圍最優(yōu)子結(jié)構(gòu)、計(jì)算復(fù)雜性、分久必合、公共子問(wèn)題分治結(jié)構(gòu)特點(diǎn)減治分治優(yōu)缺點(diǎn)優(yōu)點(diǎn)：降低復(fù)雜度缺點(diǎn)：遞歸效率低應(yīng)用舉例①二分查找②

切西瓜③

還半價(jià)34562分治的概念各個(gè)擊破、分而治之1動(dòng)態(tài)規(guī)劃010203040506070809010203040506070809枚舉法貪心算法動(dòng)態(tài)規(guī)劃分治法遞推法遞歸法迭代法查找排序算法策略10回溯法10今天你要是進(jìn)不了前一百，你就進(jìn)不了重點(diǎn)高中。你進(jìn)不了重點(diǎn)高中，就進(jìn)不了重點(diǎn)大學(xué)。進(jìn)不了重點(diǎn)大學(xué)，你等于是這輩子完了。決策決策決策小升初中考高考多階段決策問(wèn)題多階段決策過(guò)程，是指這樣一類(lèi)的決策問(wèn)題：由問(wèn)題的特性，可將過(guò)程按時(shí)間、空間等標(biāo)志分為若干個(gè)互相聯(lián)系又相互區(qū)別的階段，在它的每一個(gè)階段都需要做出決策，從而使整個(gè)過(guò)程達(dá)到最好的效果。20世紀(jì)50年代，美國(guó)數(shù)學(xué)家Bellman在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理。這種優(yōu)化理論，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，從而創(chuàng)立了解決這類(lèi)過(guò)程優(yōu)化問(wèn)題的新方法——?jiǎng)討B(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃dynamicprogramming多階段決策最短路徑問(wèn)題決策者需要作出時(shí)間上有先后之別的多次決策。前一次決策的選擇將直接影響到后一次決策，后一次決策的狀態(tài)取決于前一次決策的結(jié)果。決策者關(guān)心的是多次決策的最終結(jié)果，而不是各決策的即時(shí)結(jié)果。

階段———把一個(gè)復(fù)雜的決策問(wèn)題按時(shí)間或空間特征分解為若干個(gè)相互聯(lián)系的階段，以便順序求解。一般用k表示。

狀態(tài)———每個(gè)階段有若干個(gè)狀態(tài)，表示某一個(gè)階段決策面臨的條件或所處的位置。一般用s表示。

決策———就是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)觸發(fā)對(duì)下一階段狀態(tài)作出的選擇。一般用Xk=XK(SK)表示。表示k階段，狀態(tài)Sk時(shí)的決策。狀態(tài)轉(zhuǎn)移方程———————一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)移過(guò)程由狀態(tài)轉(zhuǎn)移過(guò)程描述。大多數(shù)情況下可以用數(shù)學(xué)公式表達(dá)。指標(biāo)函數(shù)—————分為：階段函數(shù)和過(guò)程函數(shù)（目標(biāo)函數(shù)）兩種。它是全過(guò)程或子過(guò)程或各階段上確定數(shù)量的函數(shù)。如費(fèi)用、成本、距離、利潤(rùn)、時(shí)間等。

最優(yōu)解————對(duì)指標(biāo)函數(shù)求解，稱(chēng)為最優(yōu)解。階段變量Step1Step2Step3Step4Step5Step6Step7按時(shí)間或空間劃分階段___________按時(shí)間或空間確定狀態(tài)___________狀態(tài)變量確定決策變量以及決策集合_____________決策變量寫(xiě)出狀態(tài)轉(zhuǎn)移方程__________確定決策變量取值范圍___________狀態(tài)方程取值范圍寫(xiě)出指標(biāo)函數(shù)遞推公式___________指標(biāo)函數(shù)由后向前逆序求解__________逆序求解任務(wù)：最短路徑下圖從A點(diǎn)到G點(diǎn)最短路徑是哪條？定義所需的變量輸入數(shù)據(jù)輸出數(shù)據(jù)處理數(shù)據(jù)關(guān)鍵之一設(shè)計(jì)數(shù)據(jù)描述關(guān)鍵之二設(shè)計(jì)算法

階段———按空間劃分階段。分為6個(gè)階段。K=1,…,6

狀態(tài)———狀態(tài)變量可用城市編號(hào)。S1={A}，S2={B1,B2}，S3={C1,C2,C3,C4}，S4={D1,D2,D3}，S5={E1,E2,E3}，S6={F1,F2}，S7={G}

決策———決策變量也可用城市編號(hào)。X1(S1)=A，X2(S2)=B1，X3(S3)=C2，X4(S4)=D1，X5(S5)=E2，X6(S6)=F2，X7(S7)=G

狀態(tài)轉(zhuǎn)移方程———————Sk+1=Xk

指標(biāo)函數(shù)—————階段函數(shù)：Vk=(Sk，XK)目標(biāo)函數(shù)：fk（Sk）=min{Vk+fk+1（Sk+1）}

逆序求解—————從k=6開(kāi)始計(jì)算。

逆序求解—————K=6f6(F1)=4，f6(F2)=3K=5f5(E1)=min{3+f6(F1)=7*，5+f6(F2)=8}=7f5(E2)=min{5+f6(F1)=9，2+f6(F2)=5*}=5f5(E3)=min{6+f6(F1)=10，6+f6(F2)=9*}=9K=4f4(D1)=min{2+f5(E1)=9，2+f5(E2)=7*}=7f4(D2)=min{1+f5(E2)=6*，2+f5(E3)=11}=6f4(D3)=min{3+f5(E2)=8*，3+f5(E3)=12}=8

逆序求解—————K=3f3(C1)=min{6+f4(D1)=13*，8+f4(D2)=14}=13f3(C2)=min{3+f4(D1)=10*，5+f4(D2)=11}=10f3(C3)=min{3+f4(D2)=9*，3+f4(D3)=11}=9f3(C4)=min{8+f4(D2)=14，4+f4(D3)=12*}=12K=2f2(B1)=min{1+f3(C1)=14，3+f3(C2)=13*，6+f3(C3)=15}=13f2(B2)=min{8+f3(C2)=18，7+f3(C3)=16*，6+f3(C4)=18}=16

逆序求解—————K=1f1(A)=min{5+f2(B1)=18*，3+f2(B2)=19}=18

最短路徑—————AB1C2D1E2F2Ginput階段變量，狀態(tài)變量，決策變量，狀態(tài)數(shù)組fori=階段最大值downto1step-1//倒推每一個(gè)階段forj=狀態(tài)最小值to狀態(tài)最大值//枚舉階段i的每一個(gè)狀態(tài)fork=決策最小值to決策最大值//枚舉i階段j狀態(tài)下的每一種決策

目標(biāo)函數(shù)output最優(yōu)方案最優(yōu)子結(jié)構(gòu)問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。最優(yōu)子結(jié)構(gòu)無(wú)后效性某階段狀態(tài)一旦確定，該狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。無(wú)后效性重疊子問(wèn)題重疊子問(wèn)題子問(wèn)題之間是不獨(dú)立的，一個(gè)子問(wèn)題在下一階段的決策中可能被多次使用。1）解決復(fù)雜問(wèn)題2）找到全局最優(yōu)解3）可以得到一組解1）依賴(lài)于經(jīng)驗(yàn)和技巧2）無(wú)后效性局限大3）維數(shù)災(zāi)難動(dòng)態(tài)規(guī)劃算法步驟階段、狀態(tài)決策、狀態(tài)轉(zhuǎn)移指標(biāo)函數(shù)、最優(yōu)解動(dòng)態(tài)規(guī)劃適用條件最優(yōu)子結(jié)構(gòu)無(wú)后效性重疊子問(wèn)題動(dòng)態(tài)規(guī)劃算法特點(diǎn)多次決策前一次決策影響后一次決策關(guān)心的是總結(jié)果，而非即時(shí)結(jié)果算法實(shí)現(xiàn)框架多重循環(huán)目標(biāo)函數(shù)逆序求解動(dòng)態(tài)規(guī)劃優(yōu)缺點(diǎn)優(yōu)點(diǎn)：全局最優(yōu)解缺點(diǎn)：無(wú)標(biāo)準(zhǔn)模型

維數(shù)災(zāi)難34562動(dòng)態(tài)規(guī)劃的思想多階段決策1貪心算法010203040506070809010203040506070809枚舉法貪心算法動(dòng)態(tài)規(guī)劃分治法遞推法遞歸法迭代法查找排序算法策略10回溯法10合法搶劫田忌賽馬找零錢(qián)貪心算法也稱(chēng)貪婪法。顧名思義，是指在求解最優(yōu)化問(wèn)題時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解，或者是整體最優(yōu)解的近似解?，F(xiàn)在只有面值分別為1、5和11元的硬幣，希望找回總額為15元的硬幣，要求硬幣數(shù)量最少的發(fā)放方法11+1+1+1+1=15（五枚）5+5

+5=15（三枚）貪心選擇問(wèn)題最優(yōu)解可通過(guò)一系列貪心策略的選擇得到一個(gè)問(wèn)題的最優(yōu)解包含了它的子問(wèn)題的最優(yōu)解最優(yōu)子結(jié)構(gòu)Step1根據(jù)題意選取一種度量標(biāo)準(zhǔn)Step2按照這種度量標(biāo)準(zhǔn)對(duì)數(shù)據(jù)進(jìn)行排序Step3循環(huán)+判斷保留可行解舍去無(wú)效解貪心策略排序排序排序排序貪心策略價(jià)值度量標(biāo)準(zhǔn)容量度量標(biāo)準(zhǔn)單位價(jià)值標(biāo)準(zhǔn)……任務(wù)：發(fā)工資問(wèn)題財(cái)務(wù)處發(fā)工資，如果每個(gè)老師的工資額都知道，最少需要準(zhǔn)備多少?gòu)埲嗣駧?，才能在給每位老師發(fā)工資的時(shí)候都