編程內(nèi)功修煉-算法siki微信公眾號：sikieduSIKI學(xué)院-加入U(xiǎn)nity-A計(jì)劃會有一個從零到深入的學(xué)習(xí)路線提供（視頻課程）Unity課程免費(fèi)，后續(xù)更新的所有Unity課程免費(fèi)遇到問題在課程討論區(qū)提問，老師解答如何加入？上SIKI學(xué)院-Unity-A計(jì)劃本課程也是C#編程第五季建議先把C#前四季課程看完可以從公眾號sikiedu獲取前四季的下載地址公眾號內(nèi)回復(fù)102獲取全四季下載地址前置內(nèi)容主要講解以下算法：分治法堆排序二叉樹動態(tài)規(guī)劃貪心算法圖編程內(nèi)功講什么？算法解決了哪些問題？互聯(lián)網(wǎng)信息的訪問檢測，海量數(shù)據(jù)的管理在一個交通圖中，尋找最近的路人類基因工程，dna有10萬個基因，處理這些基因序列需要復(fù)雜的算法支持上面的算法是我們沒有接觸到，或者是封裝到底層的東西，那么作為程序員，在日常編碼過程中會在什么地方使用算法呢？在你利用代碼去編寫程序，去解決問題的時(shí)候，其實(shí)這些編碼過程都可以總結(jié)成一個算法，只是有些算法看起來比較普遍比較一般，偶爾我們也會涉及一些復(fù)雜的算法比如一些AI.大多數(shù)我們都會利用已有的思路（算法）去開發(fā)游戲！注意地方：編程內(nèi)功主要講解的是算法，并不會講解Unity的使用算法的作用學(xué)習(xí)算法就像是去理解編程可以讓我們平時(shí)的編碼過程變得更加通暢并且會提高我們解決程序問題的能力所以稱之為內(nèi)功修煉學(xué)習(xí)算法的作用分治策略是：對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法。可使用分治法求解的一些經(jīng)典問題（1）二分搜索（2）大整數(shù)乘法（3）Strassen矩陣乘法（4）棋盤覆蓋（5）合并排序（6）快速排序（7）線性時(shí)間選擇（8）最接近點(diǎn)對問題（9）循環(huán)賽日程表（10）漢諾塔分治算法股票問題1，暴力求解2，分治法分治算法-最大子數(shù)組問題天數(shù)012345678910111213141516價(jià)格100113110851051028663811019410610179949097變化13-3-2520-3-16-231820-712-5-2215-47什么是樹？1，空樹2，只有一個根節(jié)點(diǎn)的樹3，什么是子樹？什么是父子結(jié)點(diǎn)？什么是根節(jié)點(diǎn)？什么是度？（擁有子樹的個數(shù)稱為結(jié)點(diǎn)的度）結(jié)點(diǎn)關(guān)系：孩子，兄弟樹（數(shù)據(jù)結(jié)構(gòu)的一種）什么是樹的層次？最大層是樹的深度什么是有序樹和無序樹？樹1，樹只有一個根節(jié)點(diǎn)2，子樹之間是不相交的3，一個結(jié)點(diǎn)不能有兩個父結(jié)點(diǎn)樹的錯誤案例存儲結(jié)構(gòu)一般是順序存儲和鏈?zhǔn)酱鎯Α涞年P(guān)系復(fù)雜使用鏈?zhǔn)酱鎯?，雙親表示法2，孩子表示法3，孩子兄弟表示法樹的存儲結(jié)構(gòu)什么是二叉樹？1，空二叉樹2，只有根結(jié)點(diǎn)3，大于一個結(jié)點(diǎn)什么是左右子樹？二叉樹1，斜樹左斜樹

右斜樹2，滿二叉樹3，完全二叉樹特殊二叉樹非完全二叉樹1，在二叉樹的第i層上最多有2i-1個結(jié)點(diǎn)（i>=1）2，深度為k的二叉樹至多有2k-1個結(jié)點(diǎn) 20+21+22+23+24+25+26+27+.....+2k-1+-1 =1+20+21+22+23+24+25+26+27+.....+2k-1-1 =21+21+22+23+24+25+26+27+.....+2k-1-1 =22+22+23+24+25+26+27+.....+2k-1-1 =23+23+24+25+26+27+.....+2k-1-1 =2k-1+2k-1-1 =2k-13,對于一個完全二叉樹，假設(shè)它有n個結(jié)點(diǎn)，對結(jié)點(diǎn)進(jìn)行從1開始編號，對任一結(jié)點(diǎn)i滿足下面 a，它的雙親是結(jié)點(diǎn)i/2(除了i=1的情況) b，左孩子是2i右孩子是2i+1 c，如果2i>n說明無左孩子2i+1>n說明無右孩子二叉樹性質(zhì)一般的樹來說是一對多的關(guān)系，使用順序結(jié)構(gòu)存儲起來比較困難，但是二叉樹是一種特殊的樹，每個結(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)，并且子節(jié)點(diǎn)有左右之分，并且兄弟，父親，孩子可以很方便的通過編號得到，所以我們使用順序存儲結(jié)構(gòu)使用二叉樹的存儲。二叉樹存儲結(jié)構(gòu)二叉樹存儲-1二叉樹存儲-2二叉樹存儲-3順序存儲一般只用于完全二叉樹二叉樹-二叉鏈表存儲二叉樹每個結(jié)點(diǎn)最多有兩個孩子，所以為它設(shè)計(jì)一個數(shù)據(jù)域和兩個指針域，我們稱這樣的鏈表為二叉鏈表。二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問二叉樹中的所有結(jié)點(diǎn)，使得每個結(jié)點(diǎn)被訪問一次且僅被訪問一次。1，前序遍歷先輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，再依次遍歷輸出左結(jié)點(diǎn)和右結(jié)點(diǎn) A(B)(C)B(D)C(E)FDGHEIABDGHCEI二叉樹的遍歷2，中序遍歷

先遍歷輸出左結(jié)點(diǎn)，再輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，再遍歷輸出右結(jié)點(diǎn)

GＤHBAEICF二叉樹的遍歷3，后序遍歷先遍歷輸出左結(jié)點(diǎn)，再遍歷輸出右結(jié)點(diǎn)，最后輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)GHDBIEFCA二叉樹的遍歷4，層序遍歷從樹的第一層開始，從上到下逐層遍歷，在同一層中，從左到右對結(jié)點(diǎn)逐個訪問輸出二叉樹的遍歷二叉排序樹，又稱為二叉查找樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹。

若它的左子樹不為空，則左子樹上所有的結(jié)點(diǎn)的值均小于根結(jié)構(gòu)的值；

若它的右子樹不為空，則右字?jǐn)?shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

它的左右子樹也分別為二叉排序樹。1，排序方便2，方便查找3，方便插入和刪除二叉排序樹二叉排序樹二叉排序樹刪除操作二叉排序樹刪除1，葉子結(jié)點(diǎn)2，僅有左子樹或者右子數(shù)的結(jié)點(diǎn)3，左右子樹都有二叉排序樹刪除操作因?yàn)槎媾判驑涞拇鎯Γ陨碇档拇笮∮嘘P(guān)系，并不是想之前學(xué)習(xí)的完全二叉樹使用順序結(jié)構(gòu)可以存儲的所以我們使用鏈?zhǔn)浇Y(jié)構(gòu)存儲二叉排序樹。二叉排序樹的存儲一個是樹類的定義BSTree一個是結(jié)點(diǎn)類的定義BSNode二叉排序樹的代碼實(shí)現(xiàn)堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值，稱為大頂堆；或者每個結(jié)點(diǎn)的值都小于等于其左右孩子結(jié)點(diǎn)的值，稱為小頂堆!堆堆排序算法就是利用堆（小頂堆或者大頂堆）進(jìn)行排序的方法。

將待排序的序列構(gòu)造成一個大頂堆，此時(shí)整個序列的最大值就是根節(jié)點(diǎn)。將它移走（跟堆的最后一個元素交換，此時(shí)末尾元素就是最大值），然后將剩余的n-1個序列重新構(gòu)造成一個堆，這樣就會得到n個元素中的次小值。如此反復(fù)執(zhí)行，便能得到一個有序序列了。堆排序堆排序堆排序什么是動態(tài)規(guī)劃，我們要如何描述它?動態(tài)規(guī)劃算法通?；谝粋€遞推公式及一個或多個初始狀態(tài)。當(dāng)前子問題的解將由上一次子問題的解推出。動態(tài)規(guī)劃和分治法相似，都是通過組合子問題的解來求解原問題。分治法將問題劃分成互不相交的子問題，遞歸求解子問題，再將他們的解組合起來，求出原問題的解。與之相反，動態(tài)規(guī)劃應(yīng)用于子問題重疊的情況，即不同的子問題具有公共的子子問題。在這種情況下，分治算法會做出許多不必要的工作，它會反復(fù)的求解那些公共子問題。而動態(tài)規(guī)劃算法對每個子子問題只求解一次，將結(jié)果保存到表格中，從而無需每次求解一個子子問題都要重新計(jì)算。動態(tài)規(guī)劃（DynamicProgramming）假定我們知道sering公司出售一段長度為I英寸的鋼條的價(jià)格為pi(i=1,2,3….)鋼條長度為整英寸如圖給出價(jià)格表的描述（任意長度的鋼條價(jià)格都有）先給我們一段長度為n的鋼條，問怎么切割，獲得的收益最大rn?考慮n=4的時(shí)候假如一個最優(yōu)解把n段七個成了k段（1<=k<=n）,那么最優(yōu)切割方案：

最大收益：

第一種求最優(yōu)解方案：對于rn(n>=1)，最優(yōu)切割收益：

將切割方案分成下面幾種1，不切割收益為pn2，將它切割成兩半，切割成兩半的情況有，對每種情況求最優(yōu)解 (1,n-1)(2,n-2)(3,n-3)(4,n-4).....(n-1,1)

對這兩半分別求最優(yōu)解,最優(yōu)解的和就是當(dāng)前情況的最優(yōu)解第二種求最優(yōu)解方案：我們從鋼條的左邊切下長度為i的一段，只對右邊剩下長度為n-i的一段繼續(xù)進(jìn)行切割，對左邊的不再切割。這樣，不做任何切割的方案就是：當(dāng)?shù)谝欢伍L度為n的時(shí)候，收益為pn，剩余長度為0，對應(yīng)的收益為0。如果第一段長度為i，收益為pi：代碼實(shí)現(xiàn)-自頂向下遞歸實(shí)現(xiàn)分析效率，關(guān)于上述方法的運(yùn)行性能時(shí)間問題。動態(tài)規(guī)劃的方法進(jìn)行求解上面的方法之所以效率很低，是因?yàn)樗磸?fù)求解相同的子問題。因此，動態(tài)規(guī)劃算法安排求解的順序，對每個子問題只求解一次，并將結(jié)果保存下來。如果隨后再次需要此子問題的解，只需查找保存的結(jié)果，不必重新計(jì)算。因此動態(tài)規(guī)劃的方法是付出額外的內(nèi)存空間來節(jié)省計(jì)算時(shí)間。動態(tài)規(guī)劃有兩種等價(jià)的實(shí)現(xiàn)方法（我們使用上面的鋼條切割問題為例，實(shí)現(xiàn)這兩種方法）第一種方法是帶備忘的自頂向下法

此方法依然是按照自然的遞歸形式編寫過程，但過程中會保存每個子問題的解（通常保存在一個數(shù)組中）。當(dāng)需要計(jì)算一個子問題的解時(shí)，過程首先檢查是否已經(jīng)保存過此解。如果是，則直接返回保存的值，從而節(jié)省了計(jì)算時(shí)間；如果沒有保存過此解，按照正常方式計(jì)算這個子問題。我們稱這個遞歸過程是帶備忘的。第二種方法是自底向上法

首先恰當(dāng)?shù)亩x子問題的規(guī)模，使得任何問題的求解都只依賴于更小的子問題的解。因而我們將子問題按照規(guī)模排序，按從小到大的順序求解。當(dāng)求解某個問題的時(shí)候，它所依賴的更小的子問題都已經(jīng)求解完畢，結(jié)果已經(jīng)保存。動態(tài)規(guī)劃-鋼條切割問題長度i12345678910價(jià)格p[i]1589101717202430問題描述：

假設(shè)現(xiàn)有容量mkg的背包，另外有i個物品，重量分別為w[1]w[2]...w[i]（kg）,價(jià)值分別為p[1]p[2]...p[i]（元）,將哪些物品放入背包可以使得背包的總價(jià)值最大？最大價(jià)值是多少？（示例一：m=10i=3重量和價(jià)值分別為3kg-4元4kg-5元5kg-6元

）1，窮舉法（把所有情況列出來，比較得到總價(jià)值最大的情況）

如果容量增大，物品增多，這個方法的運(yùn)行時(shí)間將成指數(shù)增長2，動態(tài)規(guī)劃算法

我們要求得i個物體放入容量為m(kg)的背包的最大價(jià)值（記為c[i，m]）。在選擇物品的時(shí)候，對于每種物品i只有兩種選擇，即裝入背包或不裝入背包。某種物品不能裝入多次（可以認(rèn)為每種物品只有一個），因此該問題被稱為0-1背包問題

對于c[i，m]有下面幾種情況： a、c[i,0]=c[0,m]=0 b、c[i,m]=c[i-1,m]w[i]>m（最后一個物品的重量大于容量，直接舍棄不用） w[i]<=m的時(shí)候有兩種情況，一種是放入i，一種是不放入i

不放入ic[i,m]=c[i-1,m]

放入ic[i,m]=c[i-1,m-w[i]]+p[i] c[i,m]=max(不放入i，放入i)動態(tài)規(guī)劃-01背包問題對于許多最優(yōu)化問題，使用動態(tài)規(guī)劃算法來求最優(yōu)解有些殺雞用牛刀了，可以使用更加簡單、更加高效的算法。貪心算法就是這樣的算法，它在每一步做出當(dāng)時(shí)看起來最佳的選擇。也就是說它總是做出局部最優(yōu)的選擇，從而得到全局最優(yōu)解。對于某些問題并不保證得到最0優(yōu)解，但對很多問題確實(shí)可以求得最優(yōu)解。貪心算法有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時(shí)刻只能由一個活動使用。每個活動ai都有一個開始時(shí)間si和結(jié)束時(shí)間fi。一旦被選擇后，活動ai就占據(jù)半開時(shí)間區(qū)間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行（最大兼容活動子集）。例如下圖所示的活動集合S，其中各項(xiàng)活動按照結(jié)束時(shí)間單調(diào)遞增排序。{a3,a9,a11}是一個兼容的活動子集，但它不是最大子集，因?yàn)樽蛹瘂a1,a4,a8,a11}更大，實(shí)際上它是我們這個問題的最大兼容子集，但它不是唯一的一個{a2，a4，a9，a11}1，動態(tài)規(guī)劃算法解決思路

我們使用Sij代表在活動ai結(jié)束之后，且在aj開始之前的那些活動的集合，我們使用c[i,j]代表Sij的最大兼容活動子集的大小，對于上述問題就是求c[