第一篇：總結(jié)數(shù)位DP算法

數(shù)位dp是一種計數(shù)用的dp，一般就是要統(tǒng)計一個區(qū)間[le,ri]內(nèi)滿足一些條件數(shù)的個數(shù)。比如，[1,10000] 中統(tǒng)計不含有4的數(shù)。

所謂數(shù)位dp，字面意思就是在數(shù)位上進行dp咯。就是對數(shù)字每一位每一位遞推

此類題目最基本的暴力方法：

1.for(int i=le;i<=ri;i++)

2.if(Check(i))ans++;

而數(shù)位DP就是從最低(高)位起，一位一位的放數(shù)字，然后記憶化一下，累加一下

有兩種方法，一是遞推，二是記憶化搜索

一，記憶化搜索：

思路來自： 數(shù)位dp總結(jié)之從入門到模板 假設(shè)題目要求是不含有62的數(shù)

狀態(tài)定義：d[pos][pre] 表示當前枚舉到pos位置，且pos+1位的數(shù)字是pre，此時滿足題意的數(shù)字的個數(shù)(也即是pre==6時，pos該位置不能放2)還要個數(shù)組a[i]保存第i位的數(shù)字，如213，a[0]=3，注意是從右往左數(shù)

有個問題是枚舉第pos位數(shù)時，此位置放數(shù)字的范圍要判斷一下，比如題目給出在[1,894] 枚舉的時候要判斷是否在894以內(nèi)

比如，213，第一位放了2，那么第二位就只能放0~1，所以模板中用了個limit判斷pos前的幾位數(shù)字是否與n一樣，true的話只能枚舉0~a[pos]，false就是0~9，不然比題目要求的213大了

還有個問題是前導0的問題，假如枚舉5位數(shù)，你放的時候前2位都是00，那數(shù)字不變成3位了嘛，所以需要個lead保存前幾位是否都是0，當然這是看題意的，有時候題目不要求，可以直接省去

好了，看模板：

1.typedef long long ll;2.int a[20];

3.ll dp[20][state];//不同題目狀態(tài)不同

4.ll dfs(int pos,/*state變量*/,bool lead/*前導零*/,bool limit/*數(shù)位上界變量*/)//不是每個題都要判斷前導零

5.{

6.//遞歸邊界，既然是按位枚舉，最低位是0，那么pos==-1說明這個數(shù)我枚舉完了

7.if(pos==-1)return 1;/*這里一般返回1，表示你枚舉的這個數(shù)是合法的，那么這里就需要你在枚舉時必須每一位都要滿足題目條件，也就是說當前枚舉到pos位，一定要保證前面已經(jīng)枚舉的數(shù)位是合法的。不過具體題目不同或者寫法不同的話不一定要返回1 */ 8.//第二個就是記憶化(在此前可能不同題目還能有一些剪枝)

9.if(!limit &&!lead && dp[pos][state]!=-1)return dp[pos][state];10./*常規(guī)寫法都是在沒有限制的條件記憶化，這里與下面記錄狀態(tài)是對應，具體為什么是有條件的記憶化后面會講*/

11.int up=limit?a[pos]:9;//根據(jù)limit判斷枚舉的上界up;這個的例子前面用213講過了

12.ll ans=0;13.//開始計數(shù)

14.for(int i=0;i<=up;i++)//枚舉，然后把不同情況的個數(shù)加到ans就可以了

15.{

16.if()...17.else if()...18.ans+=dfs(pos-1,/*狀態(tài)轉(zhuǎn)移*/,lead && i==0,limit && i==a[pos])//最后兩個變量傳參都是這樣寫的

19./*這里還算比較靈活，不過做幾個題就覺得這里也是套路了

20.大概就是說，我當前數(shù)位枚舉的數(shù)是i，然后根據(jù)題目的約束條件分類討論

21.去計算不同情況下的個數(shù)，還有要根據(jù)state變量來保證i的合法性，比如題目

22.要求數(shù)位上不能有62連續(xù)出現(xiàn),那么就是state就是要保存前一位pre,然后分類，23.前一位如果是6那么這意味就不能是2，這里一定要保存枚舉的這個數(shù)是合法*/

24.}

25.//計算完，記錄狀態(tài)

26.if(!limit &&!lead)dp[pos][state]=ans;

27./*這里對應上面的記憶化，在一定條件下時記錄，保證一致性，當然如果約束條件不需要考慮lead，這里就是lead就完全不用考慮了*/

28.return ans;29.}

30.ll solve(ll x)31.{

32.int pos=0;

33.while(x)//把數(shù)位都分解出來

34.{

35.a[pos++]=x%10;//個人老是喜歡編號為[0,pos),看不慣的就按自己習慣來，反正注意數(shù)位邊界就行

36.x/=10;37.}

38.return dfs(pos-1/*從最高位開始枚舉*/,/*一系列狀態(tài) */,true,true);//剛開始最高位都是有限制并且有前導零的，顯然比最高位還要高的一位視為0嘛

39.}

40.int main()41.{

42.ll le,ri;

43.while(~scanf(“%lld%lld”,&le,&ri))44.{

45.//初始化dp數(shù)組為-1,這里還有更加優(yōu)美的優(yōu)化,后面講 46.printf(“%lldn”,solve(ri)-solve(le-1));47.} 48.}

注意：

那個if(!limit &&!lead &&dp[pos][state]!=-1)return dp[pos][state];limit 的數(shù)字必須要枚舉，不能直接返回，每次都要算

雖然這會導致重復，但這可以解決狀態(tài)沖突，而且重復計算的數(shù)字也很少 舉例如下：

題目：不能出現(xiàn)連續(xù)的11(11、112、211都是不合法的)那么我們開始枚舉：

要枚舉3位數(shù)，已經(jīng)枚舉了兩位01_，要枚舉最后一位，此時狀態(tài)為d[0][1] 即：在枚舉個位，且前一位為1，那么顯然得出d[0][1]=9 開始新的一輪枚舉，枚舉到11_，此時狀態(tài)也是d[0][1] 因為已經(jīng)有9這個值了，所以返回了，但很明顯答案是0，是錯的 當然可以多開一維防止狀態(tài)沖突

可以看看數(shù)位DP模板題： HDU 2089 不要62 數(shù)位DP.二，遞推方法

思路來自：初探數(shù)位dp

狀態(tài)定義：d[i][j] 有i位數(shù)字，且第一位為j，在 0~j-1 + 000....999的符合題意的個數(shù)，如 d[4][3] 就是在 3000~3999 的符合題意的個數(shù)

還要個數(shù)組a[i]保存第i位的數(shù)字，如213，a[1]=3，注意是從右往左數(shù)（下面是從1開始數(shù)起了）

這樣狀態(tài)定義的能更加方便，可以預處理，因為當一個數(shù)字的第一位比題目要求的第一位小后，后面的幾位能000..~999..如4269，如果第一位枚舉 3 _ _ _，那么后三位可以任取

模板如下：

1.for(int i=1;i<=7;i++)//枚舉位數(shù)

2.{

3.for(int j=0;j<10;j++)//枚舉第i位可能出現(xiàn)的數(shù)

4.{

5.for(int k=0;k<10;k++)//枚舉第i-1位可能出現(xiàn)的數(shù)

6.{

7.if(j!=4&&!(j==6&&k==2))//符合題意的條件

8.dp[i][j] += dp[i-1][k];9.} 10.} 11.}

以HDU 2089，解釋怎么算出答案（不含4，62的數(shù)字）

1.#include

2.#include 3.#include

4.#include

5.using namespace std;6.int d[10][10],digit[10];

7.//d[i][j] 表示有i位數(shù)字，且第一位是j的數(shù)字的 滿足題意的數(shù)量

8.void init()9.{

10.d[0][0]=1;

11.for(int i=1;i<=7;i++)12.for(int j=0;j<=9;j++)13.for(int k=0;k<=9;k++)14.if(j!=4&&!(j==6&&k==2))15.d[i][j]+=d[i-1][k];16.}

17.int solve(int x)// [0,x)

18.{

19.int len=0;20.while(x){

21.digit[++len]=x%10;22.x/=10;23.}

24.digit[len+1]=0;25.int ans=0;

26.for(int i=len;i>=1;i--){

27.for(int j=0;j

28.if(j!=4&&!(j==2&&digit[i+1]==6))29.ans+=d[i][j];30.31.if(digit[i]==4||(digit[i+1]==6&&digit[i]==2))32.break;33.}

34.return ans;35.}

36.int main(int argc, char const *argv[])37.{

38.int n,m;39.init();

40.while(cin>>n>>m,n+m)41.cout<

42.return 0;43.}

假設(shè)一個數(shù)3229 得出

0000~0999 的個數(shù) 1000~1999 的個數(shù) 2000~2999 的個數(shù) 000~099 的個數(shù) 100~199 的個數(shù) 00~99 的個數(shù) 10~19 的個數(shù) 0~8 的個數(shù) 累加就是答案了

所以該區(qū)間是[0,n)是取不到的n的，注意計算的時候要加一個1

下面是一些題目：

HDU 2089 不要62和4 HDU 3555 含49的數(shù)

HDU 3652 含13且可以被13整除

codeforces 55d A 一個數(shù)字可以被它所有非零數(shù)整除的個數(shù) POJ 3252 Round Numbers HDU 4734 F(x)HDU 3709 Balanced Number HYSBZ 1799 self 同類分布

URAL 1057 Amount of Degrees * HDU 4507 吉哥系列故事——恨7不成妻 *

總結(jié)：

可能要用到的數(shù)位DP的題目類型：

1~10^18，求某區(qū)間（很大），有特定要求的數(shù)字的個數(shù) 如求mod，求和，可以整除各位數(shù)，不出現(xiàn)某些數(shù)...框架：

int DFS(intpos,......)//DFS一位一位放數(shù)字，求出答案，函數(shù)的參數(shù)保存題目要求的狀態(tài)

int solve(int n)//把n一位一位拆分，求出[1,n] 的符合要求的值

難點：定義好狀態(tài)！

1.dp狀態(tài)要找好，不要出現(xiàn)狀態(tài)重疊現(xiàn)象，注意前導0有沒有影響

2.題目有求和sum，可能會很大，但可以轉(zhuǎn)化為保存sum對一個數(shù)求mod的值 3.有時候dp狀態(tài)定義不好可能要求每次DFS都要memset一下，換換思路想想通用的狀態(tài)定義，如sum從加法改為減法

第二篇：算法總結(jié)

算法分塊總結(jié)

為備戰(zhàn)2005年11月4日成都一戰(zhàn)，特將已經(jīng)做過的題目按算法分塊做一個全面詳細的總結(jié)，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設(shè)計中，時刻都要牢記要減少冗余，要以簡潔高效為追求目標。另外當遇到陌生的問題時，要想方設(shè)法進行模型簡化，轉(zhuǎn)化，轉(zhuǎn)化成我們熟悉的東西。

圖論模型的應用

分層圖思想的應用：

用此思想可以建立起更簡潔、嚴謹?shù)臄?shù)學模型，進而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質(zhì)： 由于層是由復制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進行新層的存儲，甚至幾乎不需要花時間去處理。由于層之間的相似性，很多計算結(jié)果都是相同的。所以我們只需對這些計算進行一次，把結(jié)果存起來，而不需要反復計算。如此看來，雖然看起來圖變大了，但實際上問題的規(guī)模并沒有變大。層之間是拓撲有序的。這也就意味著在層之間可以很容易實現(xiàn)遞推等處理，為發(fā)現(xiàn)有效算法打下了良好的基礎(chǔ)。

這些特點說明這個分層圖思想還是很有潛力的，尤其是各層有很多公共計算結(jié)果這一點，有可能大大消除冗余計算，進而降低算法時間復雜度。二分圖最大及完備匹配的應用： ZOJ place the robots: 二分圖最優(yōu)匹配的應用：

最大網(wǎng)絡(luò)流算法的應用：典型應用就求圖的最小割。最小費用最大流的應用：

容量有上下界的最大流的應用：

歐拉路以及歐拉回路的應用：主要利用求歐拉路的套圈算法。最小生成樹：

求最小生成樹，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復雜度降為O(Vlog2V+E)，后者一般應用于稀疏圖，其時間復雜度為O(Elog2V)。最小K度限制生成樹：

抽象成數(shù)學模型就是：

設(shè)G=(V,E,ω)是連通的無向圖，v0 ∈V是特別指定的一個頂點,k為給定的一個正整數(shù)。首先考慮邊界情況。先求出問題有解時k 的最小值：把v0點從圖中刪去后，圖中可能會出 現(xiàn)m 個連通分量，而這m 個連通分量必須通過v0來連接，所以，在圖G 的所有生成樹中 dT(v0)≥m。也就是說，當k

首先，將 v0和與之關(guān)聯(lián)的邊分別從圖中刪去，此時的圖可能不再連通，對各個連通分量，分別求最小生成樹。接著，對于每個連通分量V’，求一點v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過邊(v1,v0)與v0相連。于是，我們就得到了一個m度限制生成樹，不難證明，這就是最小m度限制生成樹。這一步的時間復雜度為O(Vlog2V+E)我們所求的樹是無根樹，為了解題的簡便，把該樹轉(zhuǎn)化成以v0為根的有根樹。

假設(shè)已經(jīng)得到了最小p度限制生成樹，如何求最小p+1 度限制生成樹呢？在原先的樹中加入一條與v0相關(guān)聯(lián)的邊后，必定形成一個環(huán)。若想得到一棵p+1 度限制生成樹，需刪去一條在環(huán)上的且與v0無關(guān)聯(lián)的邊。刪去的邊的權(quán)值越大，則所得到的生成樹的權(quán)值和就越小。動態(tài)規(guī)劃就有了用武之地。設(shè)Best(v)為路徑v0—v上與v0無關(guān)聯(lián)且權(quán)值最大的邊。定義father(v)為v的父結(jié)點，動態(tài)轉(zhuǎn)移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

狀態(tài)共|V|個，狀態(tài)轉(zhuǎn)移的時間復雜度O(1)，所以總的時間復雜度為O(V)。故由最小p度限制生成樹得到最小p+1度限制生成樹的時間復雜度為O(V)。1 先求出最小m度限制生成樹；

2由最小m度限制生成樹得到最小m+1度限制生成樹;3 當dT(v0)=k時停止。

加邊和去邊過程，利用動態(tài)規(guī)劃優(yōu)化特別值得注意。

次小生成樹：

加邊和去邊很值得注意。

每加入一條不在樹上的邊，總能形成一個環(huán)，只有刪去環(huán)上的一條邊，才能保證交換后仍然是生成樹，而刪去邊的權(quán)值越大，新得到的生成樹的權(quán)值和越小。具體做法：

首先做一步預處理，求出樹上每兩個結(jié)點之間的路徑上的權(quán)值最大的邊，然后，枚舉圖中不在樹上的邊，有了剛才的預處理，我們就可以用O(1)的時間得到形成的環(huán)上的權(quán)值最大的邊。如何預處理呢？因為這是一棵樹，所以并不需要什么高深的算法，只要簡單的BFS 即可。

最短路徑的應用：

Dijkstra 算法應用： Folyed 算法應用：

Bellman-Ford 算法的應用：

差分約束系統(tǒng)的應用：

搜索算法

搜索對象和搜索順序的選取最為重要。一些麻煩題，要注意利用數(shù)據(jù)有序化，要找一個較優(yōu)的搜索出發(fā)點，凡是能用高效算法的地方盡量爭取用高效算法?；镜倪f歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應用： 枚舉思想的應用： ZOJ 1252 island of logic A*算法的應用：

IDA*算法的應用，以及跳躍式搜索探索： 限深搜索，限次： 迭代加深搜索：

部分搜索+高效算法（比如二分匹配，動態(tài)規(guī)劃）： ZOJ milk bottle data: 剪枝優(yōu)化探索：

可行性剪枝，最優(yōu)性剪枝，調(diào)整搜索順序是常用的優(yōu)化手段。

動態(tài)規(guī)劃

動態(tài)規(guī)劃最重要的就是狀態(tài)的選取，以及狀態(tài)轉(zhuǎn)移方程，另外還要考慮高效的預處理（以便更好更快的實現(xiàn)狀態(tài)轉(zhuǎn)移）。最常用的思想就是用枚舉最后一次操作。

狀態(tài)壓縮DP，又叫帶集合的動態(tài)規(guī)劃：題目特點是有一維的維數(shù)特別小。類似TSP問題的DP：

狀態(tài)劃分比較困難的題目： 樹形DP：

四邊形不等式的應用探索：四邊形不等式通常應用是把O(n^3)復雜度O(n^2)

高檔數(shù)據(jù)結(jié)構(gòu)的應用

并查集的應用：

巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹的應用：

總結(jié)用線段樹解題的方法

根據(jù)題目要求將一個區(qū)間建成線段樹，一般的題目都需要對坐標離散。建樹時，不要拘泥于線段樹這個名字而只將線段建樹，只要是表示區(qū)間，而且區(qū)間是由單位元素(可以是一個點、線段、或數(shù)組中一個值)組成的，都可以建線段樹；不要拘泥于一維，根據(jù)題目要求可以建立面積樹、體積樹等等

樹的每個節(jié)點根據(jù)題目所需，設(shè)置變量記錄要求的值

用樹形結(jié)構(gòu)來維護這些變量：如果是求總數(shù)，則是左右兒子總數(shù)之和加上本節(jié)點的總數(shù)，如果要求最值，則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時，都只對O(logL)個節(jié)點修改這個特點，在O(logL)的時間內(nèi)維護修改后相關(guān)節(jié)點的變量。

在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中，要靈活的運用子樹的收縮與葉子節(jié)點的釋放，避免重復操作。

Trie的應用：；

Trie圖的應用探索： 后綴數(shù)組的應用研究：

在字符串處理當中，后綴樹和后綴數(shù)組都是非常有力的工具，其中后綴樹了解得比較多，關(guān)于后綴數(shù)組則很少見于國內(nèi)的資料。其實后綴數(shù)組是后綴樹的一個非常精巧的替代品，它比后綴樹容易編程實現(xiàn)，能夠?qū)崿F(xiàn)后綴樹的很多功能而時間復雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。

樹狀數(shù)組的應用探索：；

計算幾何

掌握基本算法的實現(xiàn)。凸包的應用：；

半平面交算法的應用：；

幾何+模擬類題目：幾何設(shè)計好算法，模擬控制好精度。掃描法：；

轉(zhuǎn)化法：ZOJ 1606 將求所圍的格子數(shù)，巧妙的轉(zhuǎn)化為求多邊形的面積。離散法思想的應用：；

經(jīng)典算法：找平面上的最近點對。

貪心

矩形切割

二分思想應用

活用經(jīng)典算法

利用歸并排序算法思想求數(shù)列的逆序?qū)?shù)：

利用快速排序算法思想，查詢N個數(shù)中的第K小數(shù)：

博弈問題

博弈類題目通常用三類解法：第一類推結(jié)論； 第二類遞推，找N位置，P位置； 第三類SG函數(shù)的應用。第四類極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類極大極小法。

第一類：推結(jié)論。典型題目： 第二類：遞推。典型題目：

比如有向無環(huán)圖類型的博弈。在一個有向圖中，我們把選手I有必勝策略的初始位置稱為N位置(Next player winning)，其余的位置被稱為P位置(Previous player winning)。很顯然，P位置和N位置應該具有如下性質(zhì)：

1． 所有的結(jié)束位置都是P位置。

2． 對于每一個N位置，至少存在一種移動可以將棋子移動到一個P位置。3． 對于每一個P位置，它的每一種移動都會將棋子移到一個N位置。

這樣，獲勝的策略就是每次都把棋子移動到一個P位置，因為在一個P位置，你的對手只能將棋子移動到一個N位置，然后你總有一種方法再把棋子移動到一個P位置。一直這樣移動，最后你一定會將棋子移動到一個結(jié)束位置（結(jié)束位置是P位置），這時你的對手將無法在移動棋子，你便贏得了勝利。

與此同時，得到了這些性質(zhì)，我們便很容易通過倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為：

1． 將所有的結(jié)束位置標為P位置。

2． 將所有能一步到達P位置的點標為N位置。

3． 找出所有只能到達N位置的點，將它們標為P位置。

4． 如果在第三步中沒有找到新的被標為P位置的點，則算法結(jié)束，否則轉(zhuǎn)到步驟2。這樣我們便確定了所有位置，對于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類：SG函數(shù)的應用。

關(guān)于SG函數(shù)的基本知識：對于一個有向圖(X, F)來說，SG函數(shù)g是一個在X上的函數(shù)，并且它返回一個非負整數(shù)值，具體定義為

g(x)?min{n?0,n?g(y)對于所有y?F(x)}

1． 對于所有的結(jié)束位置x，g(x)= 0。

2． 對于每一個g(x)≠ 0的位置x，在它可以一步到達的位置中至少存在一個位置y使得g(y)= 0。

3．對于每一個g(x)＝ 0的位置x，所有可以由它一步到達的位置y都有g(shù)(y)≠ 0。

定理 如果g(xi)是第i個有向圖的SG函數(shù)值，i = 1,…,n，那么在由這n個有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

第四類：極大極小法。

典型題目：ZOJ 1155：Triangle War

ZOJ 1993：A Number Game

矩陣妙用

矩陣最基本的妙用就是利用快速乘法O（logn）來求解遞推關(guān)系（最基本的就是求Fibonacci數(shù)列的某項）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目：

數(shù)學模型舉例

向量思想的應用：

UVA 10089：注意降維和向量的規(guī)范化 ；

利用復數(shù)思想進行向量旋轉(zhuǎn)。

UVA 10253：

遞推

數(shù)代集合

數(shù)代集合的思想：

ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題：Intuitionistic Logic 用枚舉+數(shù)代集合思想優(yōu)化，注意到題中有一句話：“You may assume that the number H = |H| of elements of H?doesn't exceed 100”，這句話告訴我們H的元素個數(shù)不會超過100，因此可以考慮用一個數(shù)代替一個集合，首先把所有的運算結(jié)果都用預處理算出來，到計算的時候只要用O(1)的復雜度就可以完成一次運算。

組合數(shù)學

Polya定理則是解決同構(gòu)染色計數(shù)問題的有力工具。

補集轉(zhuǎn)化思想

ZOJ 單色三角形：

字符串相關(guān)

擴展的KMP算法應用：；最長回文串； 最長公共子串； 最長公共前綴；

填充問題

高精度運算

三維空間問題專題

無論什么問題，一旦擴展到三難空間，就變得很有難度了。三維空間的問題，很考代碼實現(xiàn)能力。

其它問題的心得

解決一些判斷同構(gòu)問題的方法：同構(gòu)的關(guān)鍵在于一一對應，而如果枚舉一一對應的關(guān)系，時間復雜度相當?shù)母?，利用最小表示，就能把一個事物的本質(zhì)表示出來。求最小表示時，我們一定要仔細分析，將一切能區(qū)分兩個元素的條件都在最小表示中體現(xiàn)，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當?shù)?、高效的匹配算法（例如KMP字符匹配之類的），來比較最小表示是否相同，這里常常要將我們熟悉的高效算法進行推廣

第三篇：算法總結(jié)

算法分析與設(shè)計總結(jié)報告

71110415 錢玉明

在計算機軟件專業(yè)中，算法分析與設(shè)計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個公式。算法的學習對于培養(yǎng)一個人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為IT行業(yè)學生，學習算法無疑會增強自己的競爭力，修煉自己的“內(nèi)功”。

下面我將談談我對這門課程的心得與體會。

一、數(shù)學是算法的基礎(chǔ)

經(jīng)過這門課的學習，我深刻的領(lǐng)悟到數(shù)學是一切算法分析與設(shè)計的基礎(chǔ)。這門課的很多時間多花在了數(shù)學公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學息息相關(guān)。其中有幾個定理令我印象深刻。

①主定理

本門課中它主要應用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個大問題分解為a個子問題，其中子問題的規(guī)模為b。而f(n)可看作這些子問題的組合時的消耗。這些可以利用主定理的相關(guān)結(jié)論進行分析處理。當f(n)量級高于nlogba時，我們可以設(shè)法降低子問題組合時的消耗來提高性能。反之我們可以降低nlogba的消耗，即可以擴大問題的規(guī)?；蛘邷p小子問題的個數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進行有效的改進。

②隨機算法中的許多定理的運用

在這門課中，我學到了以前從未遇見過的隨機算法，它給予我很大的啟示。隨機算法不隨機，它可通過多次的嘗試來降低它的錯誤率以至于可以忽略不計。這些都不是空穴來風，它是建立在嚴格的定理的證明上。如素數(shù)判定定理是個很明顯的例子。它運用了包括費馬小定理在內(nèi)的各種定理。將這些定理進行有效的組合利用，才得出行之有效的素數(shù)判定的定理。尤其是對尋找證據(jù)數(shù)算法的改進的依據(jù)，也是建立在3個定理上。還有檢查字符串是否匹配也是運用了許多定理：指紋的運用，理論出錯率的計算，算法性能的評價也都是建立在數(shù)學定理的運用上。

這些算法都給予了我很大啟發(fā)，要想學好算法，學好數(shù)學是必不可少的。沒有深厚的數(shù)學功力作為地基，即使再漂亮的算法框架，代碼實現(xiàn)也只能是根底淺的墻上蘆葦。

二、算法的核心是思想

我們學習這門課不是僅僅掌握那幾個經(jīng)典算法例子，更重要的是為了學習蘊含在其中的思想方法。為什么呢？舉個例子。有同學曾問我這樣一個問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個星期。現(xiàn)在用10只老鼠在一個星期內(nèi)判斷那只瓶子有毒，每只老鼠可以喝多個瓶子的水，每個瓶子可以只喝一點。問如何解決？其實一開始我也一頭霧水，但是他提醒我跟計算機領(lǐng)域相關(guān)，我就立馬有了思路，運用二進制。因為計算機的最基本思想就是二進制。所以說，我們不僅要學習算法，更得學習思想方法。

①算法最基本的設(shè)計方法包括分治法，動態(tài)規(guī)劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個元素中最大元和最小元的量級，降低n位二進制x和y相乘的量級，做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問題分解為規(guī)模較小的獨立的子問題，關(guān)鍵是子問題要與原問題同類，可以采取平衡法來提高性能。

動態(tài)規(guī)劃法是把大問題分解為子問題，但是子問題是重復的，后面的問題可以利用前面解決過的問題的結(jié)果。如構(gòu)造最優(yōu)二叉查找樹，解決矩陣連乘時最小計算次數(shù)問題，尋找最長公共子序列等等。

貪心法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構(gòu)造出更大的局部直至整體。如Kruscal最小生成樹算法，求哈夫曼編碼問題。

周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點，典型的應用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。

回溯法就是就是在滿足一定的條件后就往前走，當走到某步時，發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應用就是8皇后問題，平面點集的凸包問題和0-1背包問題。

分支定界法：它是解決整數(shù)規(guī)劃問題一種最常用的方法。典型應用就是解決整數(shù)規(guī)劃問題。

②評價算法性能的方法如平攤分析中的聚集法，會計法和勢能法。聚集法就是把指令分為幾類，計算每一類的消耗，再全部疊加起來。會計法就是計算某個指令時提前將另一個指令的消耗也算進去，以后計算另一個指令時就不必再算了。勢能法計算每一步的勢的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計。

這幾種方法都是平攤分析法，平攤分析的實質(zhì)就是總體考慮指令的消耗時間，盡管某些指令的消耗時間很大也可以忽略不計。上述三種方法難易程度差不多，每種方法都有屬于它的難點。如聚集法中如何將指令有效分類，會計法中用什么指令提前計算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學會去應用，在具體的問題中去判斷分析。

三、算法與應用緊密相關(guān)

我認為學習算法不能局限于書本上的理論運算，局限于如何提高性能以降低復雜度，我們要將它與實際生活聯(lián)系起來。其實算法問題的產(chǎn)生就來自于生活，設(shè)計出高效的算法就是為了更好的應用。如尋找最長公共子序列算法可以應用在生物信息學中通過檢測相似DNA片段的相似成分來檢測生物特性的相似性，也可以用來判斷兩個字符串的相近性，這可應用在數(shù)據(jù)挖掘中。快速傅立葉變換（FFT）可應用在計算多項式相乘上來降低復雜度，脫線min算法就是利用了Union-Find這種結(jié)構(gòu)。還有圖中相關(guān)算法，它對于解決網(wǎng)絡(luò)流量分配問題起了很大的幫助，等等。

這些應用給了我很大的啟發(fā)：因為單純講一個Union-Find算法，即使了解了它的實現(xiàn)原理，遇到具體的實際問題也不知去如何應用。這就要求我們要將自己學到的算法要和實際問題結(jié)合起來，不能停留在思想方法階段，要學以致用，做到具體問題具體分析。

四、對計算模型和NP問題的理解

由于對這部分內(nèi)容不是很理解，所以就粗淺的談一下我的看法。

首先談到計算模型，就不得不提到圖靈計算，他將基本的計算抽象化，造出一個圖靈機，得出了計算的本質(zhì)。并提出圖靈機可以計算的問題都是可以計算的，否則就是不可計算的。由此引申出一個著名論題：任何合理的計算模型都是相互等價的。它說明了可計算性本身不依賴于任何具體的模型而客觀存在。

NP問題比較復雜，我認為它是制約算法發(fā)展的瓶頸，但這也是算法分析的魅力所在。NP問題一般可分為3類，NP-C問題，NP-hard問題以及頑型問題。NP-C它有個特殊的性質(zhì)，如果存在一個NP-C問題找到一個多項式時間的解法，則所有的NP-C問題都能找到多項式時間解法。如哈密頓回路問題。NP-hard主要是解決最優(yōu)化問題。它不一定是NP問題。這些問題在規(guī)模較小時可以找出精確解，但是規(guī)模大時，就因時間太復雜而找不到最優(yōu)解。此時一般會采用近似算法的解法。頑型問題就是已經(jīng)證明不可能有多項式時間的算法，如漢諾塔問題。

最后談談對這門課程的建議

①對于這門算法課，我認為應該加強對算法思想方法的學習。所以我建議老師可不可以先拋出問題而不給出答案，講完一章，再發(fā)課件。讓我們先思考一會兒，或者給出個獎勵機制，誰能解決這個問題，平時成績加分。這在一定程度上會將強我們思考分析問題的能力。因為我感覺到，一個問題出來，未經(jīng)過思考就已經(jīng)知曉它的答案，就沒什么意思，得不到提高，而且也不能加深對問題的思考和理解。下次遇到類似的問題也就沒有什么印象。而且上課讓我們思考，點名回答問題可以一定程度上有效的防止不認真聽課的現(xiàn)象。

②作業(yè)安排的不是很恰當。本門課主要安排了三次作業(yè)，個人感覺只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實現(xiàn)一下偽代碼，沒有太多的技術(shù)含量。而且對于培養(yǎng)我們的解決問題的能力也沒有太多的幫助，因為這間接成為了程序設(shè)計題，不是算法設(shè)計題。

③本門課的時間安排的不太恰當，因為本學期的課程太多，壓力太大。沒有太多的時間去學習這門課程。因為我相信大家都對它感興趣，比較重視，想花功夫，但苦于沒時間。所以可不可以將課程提前一個學期，那時候離散數(shù)學也已經(jīng)學過，且課程的壓力也不是很大。錯開時間的話，我覺得應該能夠更好提高大家算法分析設(shè)計的能力。

第四篇：認識數(shù)位

認識數(shù)位

教學目標：

知識與技能：。通過計數(shù)器使學生認識個位，十位、百位，了解個位、十位上數(shù)表示含義，會正確讀、寫100以內(nèi)的數(shù)。

過程與方法：。通過動手操作、觀察，直觀體驗數(shù)的意義，數(shù)的讀、寫法的過程方法。

情感態(tài)度、價值觀：在學習中建立數(shù)感，能積極參與學習，形成獨立思考和合作學習的習慣。

學習方式：動手操作，自主合作交流探究。

教學準備：每人一個計數(shù)器，（學具）幻燈片（分片）數(shù)位、數(shù)字卡片。

教學過程：

環(huán)節(jié) 學生活動 教師活動 設(shè)計意圖

創(chuàng)設(shè)情境 生答 出示計數(shù)器

同學們你們認識這是什么學具嗎？

（生如果不認識，師直接點出，這是計數(shù)器，是用來學習數(shù)用的）。

激發(fā)學生強烈的學習欲望。

探

究

與

體

驗 自由讀，在計數(shù)器上標出個、十、百位。

從右邊數(shù)第一位是個位，第二位是十位，第三位是百位。

指生讀，齊讀。

學生動手撥

讀作二十四，寫作24。

因為十位撥的是2，個位撥的是4，所以就是24。

24中的2表示2個十，4表示4個一。

自己在計數(shù)器上撥數(shù)

讀一讀、說一說、寫一寫。

匯報：

讀作四十二，寫做42。因為4在十位上表示4個十，2在個位上表示2個一。所以寫做42。

學生動手撥數(shù)、讀數(shù)

說意義，“十位上的5表示5個十，個位上的5表示5個一”。

學生看圖，照樣子撥珠，同桌交流，匯報：計數(shù)器的十位上的數(shù)是6，表示6個十，個位上沒有珠，表示一個也沒有用零表示。這個計數(shù)器上的珠子表示60。

1、認識計數(shù)器上的數(shù)位。

幻燈片出示。

同學們，從右邊數(shù)第一位、第二位、第三位各是什么位？（若學生回答不出來，教師講解）。從右邊數(shù)第一位是個位，第二位是十位，第三位是百位。

2、撥數(shù)，寫數(shù)、讀數(shù)。

（1）教師說數(shù)學生撥。

在計數(shù)器的十位上撥2，個位上撥4。這個數(shù)讀作多少？該怎樣寫出來？你們試著撥一撥、說一說。你是怎么知道的？

（2）寫法及數(shù)表示的意義：

十位上是2，就在十位上寫2，表示2個十。個位上是4，就在個位上寫4，表示4個一。讀作二十四。板書24。

同桌同學互相說一說24中2和4各表示什么？

1、練習撥一撥、讀一讀。

教師說數(shù)，在十位上撥4

在個位上撥2，讀讀、寫寫、說說你是怎么知道的？

讓學生在計數(shù)器上撥出55。

（讓學生說說這兩個5的意義有什么不同）

4、出示圖片（試一試）

照樣子撥珠再寫數(shù)，并讀出來

重點引導：第2個計數(shù)器，個位上沒珠，怎么辦？寫幾表示

引導學生歸納寫數(shù)的方法。

計數(shù)器的十位上是幾就在十位上寫幾，計數(shù)器的個位上是幾就在個位上寫幾。通過自己利用計數(shù)器撥數(shù)、讀數(shù)、寫數(shù)等多種形式調(diào)動學生的多種感官參與學習活動，使學生對數(shù)的寫法、讀法以及數(shù)位有了進一步的體驗和感悟，對數(shù)的意義也有了初步的了解。

在學生操作的同時，注重讓學生用語言表達數(shù)的意義，這樣學生對數(shù)的讀法、寫法、數(shù)位理解的就更加深刻了。

鞏

固

與

應

用

1、題：獨立完成 集體訂正。

2、題同桌互讀

指生讀

3、題在計數(shù)器上撥一撥，然后寫出來。

4、題：同桌交流，填空。完成練習1、2、3、4題數(shù)字游戲。

4題：指導第1圖

1個〇是十，4個〇是多少？

1個△是一5個△是多少？

4個十5個一合起來是多少？

數(shù)字游戲：分組進行：一人說數(shù)一人在數(shù)位表上撥。多種形式的練習，鞏固加深理解了所學知識，同時也激發(fā)了學生學習數(shù)學的熱情。

第五篇：web 算法總結(jié)

1.去掉超鏈接的下畫線： 在 //添加這句就行。 2.格式為：你需要添加下畫線的文字 3.獲取時間

我們可以通過使用DataTime這個類來獲取當前的時間。通過調(diào)用類中的各種方法我們可以獲取不同的時間：如：日期（2008-09-04）、時間（12：12：12）、日期+時間（2008-09-04 12：11：10）等。

//獲取日期+時間

DateTime.Now.ToString();

// 2008-9-4 20:02:10 DateTime.Now.ToLocalTime().ToString();

// 2008-9-4 20:12:12 //獲取日期

DateTime.Now.ToLongDateString().ToString();

// 2008年9月4日 DateTime.Now.ToShortDateString().ToString();

// 2008-9-4 DateTime.Now.ToString(“yyyy-MM-dd”);

// 2008-09-04 DateTime.Now.Date.ToString();

// 2008-9-4 0:00:00 //獲取時間 DateTime.Now.ToLongTimeString().ToString();

// 20:16:16 DateTime.Now.ToShortTimeString().ToString();

// 20:16 DateTime.Now.ToString(“hh:mm:ss”);

// 08:05:57 DateTime.Now.TimeOfDay.ToString();

// 20:33:50.7187500 //其他

DateTime.ToFileTime().ToString();

// ***000 DateTime.Now.ToFileTimeUtc().ToString();

// ***750 DateTime.Now.ToOADate().ToString();

// 39695.8461709606 DateTime.Now.ToUniversalTime().ToString();

// 2008-9-4 12:19:14 DateTime.Now.Year.ToString();

獲取年份

// 2008 DateTime.Now.Month.ToString();

獲取月份

// 9 DateTime.Now.DayOfWeek.ToString();獲取星期

// Thursday DateTime.Now.DayOfYear.ToString();獲取第幾天

// 248 DateTime.Now.Hour.ToString();

獲取小時

// 20 DateTime.Now.Minute.ToString();

獲取分鐘

// 31 DateTime.Now.Second.ToString();

獲取秒數(shù)

// 45 //n為一個數(shù),可以數(shù)整數(shù),也可以事小數(shù) dt.AddYears(n).ToString();

//時間加n年 dt.AddDays(n).ToString();

//加n天 dt.AddHours(n).ToString();

//加n小時 dt.AddMonths(n).ToString();

//加n個月 dt.AddSeconds(n).ToString();

//加n秒 dt.AddMinutes(n).ToString();

//加n分 SQL語句使用時間和日期的函數(shù)

getdate():獲取系統(tǒng)當前時間

dateadd(datepart,number,date):計算在一個時間的基礎(chǔ)上增加一個時間后的新時間值,比如：dateadd(yy,30,getdate())datediff(datepart,startdate,enddate):計算兩個時間的差值,比如：datediff(yy,getdate(),'2008-08-08')dataname(datepart,date):獲取時間不同部分的值，返回值為字符串 datepart(datepart,date):和datename相似，只是返回值為整型 day(date):獲取指定時間的天數(shù) month(date):獲取指定時間的月份 year(date):獲取指定時間的年份 select year(getdate())：當前年份