第一篇:總結(jié)數(shù)位DP算法
數(shù)位dp是一種計(jì)數(shù)用的dp,一般就是要統(tǒng)計(jì)一個(gè)區(qū)間[le,ri]內(nèi)滿足一些條件數(shù)的個(gè)數(shù)。比如,[1,10000] 中統(tǒng)計(jì)不含有4的數(shù)。
所謂數(shù)位dp,字面意思就是在數(shù)位上進(jìn)行dp咯。就是對(duì)數(shù)字每一位每一位遞推
此類(lèi)題目最基本的暴力方法:
1.for(int i=le;i<=ri;i++)
2.if(Check(i))ans++;
而數(shù)位DP就是從最低(高)位起,一位一位的放數(shù)字,然后記憶化一下,累加一下
有兩種方法,一是遞推,二是記憶化搜索
一,記憶化搜索:
思路來(lái)自: 數(shù)位dp總結(jié)之從入門(mén)到模板 假設(shè)題目要求是不含有62的數(shù)
狀態(tài)定義:d[pos][pre] 表示當(dāng)前枚舉到pos位置,且pos+1位的數(shù)字是pre,此時(shí)滿足題意的數(shù)字的個(gè)數(shù)(也即是pre==6時(shí),pos該位置不能放2)還要個(gè)數(shù)組a[i]保存第i位的數(shù)字,如213,a[0]=3,注意是從右往左數(shù)
有個(gè)問(wèn)題是枚舉第pos位數(shù)時(shí),此位置放數(shù)字的范圍要判斷一下,比如題目給出在[1,894] 枚舉的時(shí)候要判斷是否在894以內(nèi)
比如,213,第一位放了2,那么第二位就只能放0~1,所以模板中用了個(gè)limit判斷pos前的幾位數(shù)字是否與n一樣,true的話只能枚舉0~a[pos],false就是0~9,不然比題目要求的213大了
還有個(gè)問(wèn)題是前導(dǎo)0的問(wèn)題,假如枚舉5位數(shù),你放的時(shí)候前2位都是00,那數(shù)字不變成3位了嘛,所以需要個(gè)lead保存前幾位是否都是0,當(dāng)然這是看題意的,有時(shí)候題目不要求,可以直接省去
好了,看模板:
1.typedef long long ll;2.int a[20];
3.ll dp[20][state];//不同題目狀態(tài)不同
4.ll dfs(int pos,/*state變量*/,bool lead/*前導(dǎo)零*/,bool limit/*數(shù)位上界變量*/)//不是每個(gè)題都要判斷前導(dǎo)零
5.{
6.//遞歸邊界,既然是按位枚舉,最低位是0,那么pos==-1說(shuō)明這個(gè)數(shù)我枚舉完了
7.if(pos==-1)return 1;/*這里一般返回1,表示你枚舉的這個(gè)數(shù)是合法的,那么這里就需要你在枚舉時(shí)必須每一位都要滿足題目條件,也就是說(shuō)當(dāng)前枚舉到pos位,一定要保證前面已經(jīng)枚舉的數(shù)位是合法的。不過(guò)具體題目不同或者寫(xiě)法不同的話不一定要返回1 */ 8.//第二個(gè)就是記憶化(在此前可能不同題目還能有一些剪枝)
9.if(!limit &&!lead && dp[pos][state]!=-1)return dp[pos][state];10./*常規(guī)寫(xiě)法都是在沒(méi)有限制的條件記憶化,這里與下面記錄狀態(tài)是對(duì)應(yīng),具體為什么是有條件的記憶化后面會(huì)講*/
11.int up=limit?a[pos]:9;//根據(jù)limit判斷枚舉的上界up;這個(gè)的例子前面用213講過(guò)了
12.ll ans=0;13.//開(kāi)始計(jì)數(shù)
14.for(int i=0;i<=up;i++)//枚舉,然后把不同情況的個(gè)數(shù)加到ans就可以了
15.{
16.if()...17.else if()...18.ans+=dfs(pos-1,/*狀態(tài)轉(zhuǎn)移*/,lead && i==0,limit && i==a[pos])//最后兩個(gè)變量傳參都是這樣寫(xiě)的
19./*這里還算比較靈活,不過(guò)做幾個(gè)題就覺(jué)得這里也是套路了
20.大概就是說(shuō),我當(dāng)前數(shù)位枚舉的數(shù)是i,然后根據(jù)題目的約束條件分類(lèi)討論
21.去計(jì)算不同情況下的個(gè)數(shù),還有要根據(jù)state變量來(lái)保證i的合法性,比如題目
22.要求數(shù)位上不能有62連續(xù)出現(xiàn),那么就是state就是要保存前一位pre,然后分類(lèi),23.前一位如果是6那么這意味就不能是2,這里一定要保存枚舉的這個(gè)數(shù)是合法*/
24.}
25.//計(jì)算完,記錄狀態(tài)
26.if(!limit &&!lead)dp[pos][state]=ans;
27./*這里對(duì)應(yīng)上面的記憶化,在一定條件下時(shí)記錄,保證一致性,當(dāng)然如果約束條件不需要考慮lead,這里就是lead就完全不用考慮了*/
28.return ans;29.}
30.ll solve(ll x)31.{
32.int pos=0;
33.while(x)//把數(shù)位都分解出來(lái)
34.{
35.a[pos++]=x%10;//個(gè)人老是喜歡編號(hào)為[0,pos),看不慣的就按自己習(xí)慣來(lái),反正注意數(shù)位邊界就行
36.x/=10;37.}
38.return dfs(pos-1/*從最高位開(kāi)始枚舉*/,/*一系列狀態(tài) */,true,true);//剛開(kāi)始最高位都是有限制并且有前導(dǎo)零的,顯然比最高位還要高的一位視為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.}
注意:
那個(gè)if(!limit &&!lead &&dp[pos][state]!=-1)return dp[pos][state];limit 的數(shù)字必須要枚舉,不能直接返回,每次都要算
雖然這會(huì)導(dǎo)致重復(fù),但這可以解決狀態(tài)沖突,而且重復(fù)計(jì)算的數(shù)字也很少 舉例如下:
題目:不能出現(xiàn)連續(xù)的11(11、112、211都是不合法的)那么我們開(kāi)始枚舉:
要枚舉3位數(shù),已經(jīng)枚舉了兩位01_,要枚舉最后一位,此時(shí)狀態(tài)為d[0][1] 即:在枚舉個(gè)位,且前一位為1,那么顯然得出d[0][1]=9 開(kāi)始新的一輪枚舉,枚舉到11_,此時(shí)狀態(tài)也是d[0][1] 因?yàn)橐呀?jīng)有9這個(gè)值了,所以返回了,但很明顯答案是0,是錯(cuò)的 當(dāng)然可以多開(kāi)一維防止?fàn)顟B(tài)沖突
可以看看數(shù)位DP模板題: HDU 2089 不要62 數(shù)位DP.二,遞推方法
思路來(lái)自:初探數(shù)位dp
狀態(tài)定義:d[i][j] 有i位數(shù)字,且第一位為j,在 0~j-1 + 000....999的符合題意的個(gè)數(shù),如 d[4][3] 就是在 3000~3999 的符合題意的個(gè)數(shù)
還要個(gè)數(shù)組a[i]保存第i位的數(shù)字,如213,a[1]=3,注意是從右往左數(shù)(下面是從1開(kāi)始數(shù)起了)
這樣狀態(tài)定義的能更加方便,可以預(yù)處理,因?yàn)楫?dāng)一個(gè)數(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
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è)一個(gè)數(shù)3229 得出 0000~0999 的個(gè)數(shù) 1000~1999 的個(gè)數(shù) 2000~2999 的個(gè)數(shù) 000~099 的個(gè)數(shù) 100~199 的個(gè)數(shù) 00~99 的個(gè)數(shù) 10~19 的個(gè)數(shù) 0~8 的個(gè)數(shù) 累加就是答案了 所以該區(qū)間是[0,n)是取不到的n的,注意計(jì)算的時(shí)候要加一個(gè)1 下面是一些題目: HDU 2089 不要62和4 HDU 3555 含49的數(shù) HDU 3652 含13且可以被13整除 codeforces 55d A 一個(gè)數(shù)字可以被它所有非零數(shù)整除的個(gè)數(shù) POJ 3252 Round Numbers HDU 4734 F(x)HDU 3709 Balanced Number HYSBZ 1799 self 同類(lèi)分布 URAL 1057 Amount of Degrees * HDU 4507 吉哥系列故事——恨7不成妻 * 總結(jié): 可能要用到的數(shù)位DP的題目類(lèi)型: 1~10^18,求某區(qū)間(很大),有特定要求的數(shù)字的個(gè)數(shù) 如求mod,求和,可以整除各位數(shù),不出現(xiàn)某些數(shù)...框架: int DFS(intpos,......)//DFS一位一位放數(shù)字,求出答案,函數(shù)的參數(shù)保存題目要求的狀態(tài) int solve(int n)//把n一位一位拆分,求出[1,n] 的符合要求的值 難點(diǎn):定義好狀態(tài)! 1.dp狀態(tài)要找好,不要出現(xiàn)狀態(tài)重疊現(xiàn)象,注意前導(dǎo)0有沒(méi)有影響 2.題目有求和sum,可能會(huì)很大,但可以轉(zhuǎn)化為保存sum對(duì)一個(gè)數(shù)求mod的值 3.有時(shí)候dp狀態(tài)定義不好可能要求每次DFS都要memset一下,換換思路想想通用的狀態(tài)定義,如sum從加法改為減法 算法分塊總結(jié) 為備戰(zhàn)2005年11月4日成都一戰(zhàn),特將已經(jīng)做過(guò)的題目按算法分塊做一個(gè)全面詳細(xì)的總結(jié),主要突出算法思路,盡量選取有代表性的題目,盡量做到算法的全面性,不漏任何ACM可能涉及的算法思路。算法設(shè)計(jì)中,時(shí)刻都要牢記要減少冗余,要以簡(jiǎn)潔高效為追求目標(biāo)。另外當(dāng)遇到陌生的問(wèn)題時(shí),要想方設(shè)法進(jìn)行模型簡(jiǎn)化,轉(zhuǎn)化,轉(zhuǎn)化成我們熟悉的東西。 圖論模型的應(yīng)用 分層圖思想的應(yīng)用: 用此思想可以建立起更簡(jiǎn)潔、嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型,進(jìn)而很容易得到有效算法。重要的是,新建立的圖有一些很好的性質(zhì): 由于層是由復(fù)制得到的,所以所有層都非常相似,以至于我們只要在邏輯上分出層的概念即可,根本不用在程序中進(jìn)行新層的存儲(chǔ),甚至幾乎不需要花時(shí)間去處理。由于層之間的相似性,很多計(jì)算結(jié)果都是相同的。所以我們只需對(duì)這些計(jì)算進(jìn)行一次,把結(jié)果存起來(lái),而不需要反復(fù)計(jì)算。如此看來(lái),雖然看起來(lái)圖變大了,但實(shí)際上問(wèn)題的規(guī)模并沒(méi)有變大。層之間是拓?fù)溆行虻?。這也就意味著在層之間可以很容易實(shí)現(xiàn)遞推等處理,為發(fā)現(xiàn)有效算法打下了良好的基礎(chǔ)。 這些特點(diǎn)說(shuō)明這個(gè)分層圖思想還是很有潛力的,尤其是各層有很多公共計(jì)算結(jié)果這一點(diǎn),有可能大大消除冗余計(jì)算,進(jìn)而降低算法時(shí)間復(fù)雜度。二分圖最大及完備匹配的應(yīng)用: ZOJ place the robots: 二分圖最優(yōu)匹配的應(yīng)用: 最大網(wǎng)絡(luò)流算法的應(yīng)用:典型應(yīng)用就求圖的最小割。最小費(fèi)用最大流的應(yīng)用: 容量有上下界的最大流的應(yīng)用: 歐拉路以及歐拉回路的應(yīng)用:主要利用求歐拉路的套圈算法。最小生成樹(shù): 求最小生成樹(shù),比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復(fù)雜度降為O(Vlog2V+E),后者一般應(yīng)用于稀疏圖,其時(shí)間復(fù)雜度為O(Elog2V)。最小K度限制生成樹(shù): 抽象成數(shù)學(xué)模型就是: 設(shè)G=(V,E,ω)是連通的無(wú)向圖,v0 ∈V是特別指定的一個(gè)頂點(diǎn),k為給定的一個(gè)正整數(shù)。首先考慮邊界情況。先求出問(wèn)題有解時(shí)k 的最小值:把v0點(diǎn)從圖中刪去后,圖中可能會(huì)出 現(xiàn)m 個(gè)連通分量,而這m 個(gè)連通分量必須通過(guò)v0來(lái)連接,所以,在圖G 的所有生成樹(shù)中 dT(v0)≥m。也就是說(shuō),當(dāng)k 首先,將 v0和與之關(guān)聯(lián)的邊分別從圖中刪去,此時(shí)的圖可能不再連通,對(duì)各個(gè)連通分量,分別求最小生成樹(shù)。接著,對(duì)于每個(gè)連通分量V’,求一點(diǎn)v1,v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’},則該連通分量通過(guò)邊(v1,v0)與v0相連。于是,我們就得到了一個(gè)m度限制生成樹(shù),不難證明,這就是最小m度限制生成樹(shù)。這一步的時(shí)間復(fù)雜度為O(Vlog2V+E)我們所求的樹(shù)是無(wú)根樹(shù),為了解題的簡(jiǎn)便,把該樹(shù)轉(zhuǎn)化成以v0為根的有根樹(shù)。 假設(shè)已經(jīng)得到了最小p度限制生成樹(shù),如何求最小p+1 度限制生成樹(shù)呢?在原先的樹(shù)中加入一條與v0相關(guān)聯(lián)的邊后,必定形成一個(gè)環(huán)。若想得到一棵p+1 度限制生成樹(shù),需刪去一條在環(huán)上的且與v0無(wú)關(guān)聯(lián)的邊。刪去的邊的權(quán)值越大,則所得到的生成樹(shù)的權(quán)值和就越小。動(dòng)態(tài)規(guī)劃就有了用武之地。設(shè)Best(v)為路徑v0—v上與v0無(wú)關(guān)聯(lián)且權(quán)值最大的邊。定義father(v)為v的父結(jié)點(diǎn),動(dòng)態(tài)轉(zhuǎn)移方程:Best(v)=max(Best(father(v)),(father(v),v)),邊界條件為Best[v0]=-∞,Best[v’]=-∞|(v0,v’)∈E(T)。 狀態(tài)共|V|個(gè),狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度O(1),所以總的時(shí)間復(fù)雜度為O(V)。故由最小p度限制生成樹(shù)得到最小p+1度限制生成樹(shù)的時(shí)間復(fù)雜度為O(V)。1 先求出最小m度限制生成樹(shù); 2由最小m度限制生成樹(shù)得到最小m+1度限制生成樹(shù);3 當(dāng)dT(v0)=k時(shí)停止。 加邊和去邊過(guò)程,利用動(dòng)態(tài)規(guī)劃優(yōu)化特別值得注意。 次小生成樹(shù): 加邊和去邊很值得注意。 每加入一條不在樹(shù)上的邊,總能形成一個(gè)環(huán),只有刪去環(huán)上的一條邊,才能保證交換后仍然是生成樹(shù),而刪去邊的權(quán)值越大,新得到的生成樹(shù)的權(quán)值和越小。具體做法: 首先做一步預(yù)處理,求出樹(shù)上每?jī)蓚€(gè)結(jié)點(diǎn)之間的路徑上的權(quán)值最大的邊,然后,枚舉圖中不在樹(shù)上的邊,有了剛才的預(yù)處理,我們就可以用O(1)的時(shí)間得到形成的環(huán)上的權(quán)值最大的邊。如何預(yù)處理呢?因?yàn)檫@是一棵樹(shù),所以并不需要什么高深的算法,只要簡(jiǎn)單的BFS 即可。 最短路徑的應(yīng)用: Dijkstra 算法應(yīng)用: Folyed 算法應(yīng)用: Bellman-Ford 算法的應(yīng)用: 差分約束系統(tǒng)的應(yīng)用: 搜索算法 搜索對(duì)象和搜索順序的選取最為重要。一些麻煩題,要注意利用數(shù)據(jù)有序化,要找一個(gè)較優(yōu)的搜索出發(fā)點(diǎn),凡是能用高效算法的地方盡量爭(zhēng)取用高效算法。基本的遞歸回溯深搜,記憶化搜索,注意剪枝: 廣搜(BFS)的應(yīng)用: 枚舉思想的應(yīng)用: ZOJ 1252 island of logic A*算法的應(yīng)用: IDA*算法的應(yīng)用,以及跳躍式搜索探索: 限深搜索,限次: 迭代加深搜索: 部分搜索+高效算法(比如二分匹配,動(dòng)態(tài)規(guī)劃): ZOJ milk bottle data: 剪枝優(yōu)化探索: 可行性剪枝,最優(yōu)性剪枝,調(diào)整搜索順序是常用的優(yōu)化手段。 動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃最重要的就是狀態(tài)的選取,以及狀態(tài)轉(zhuǎn)移方程,另外還要考慮高效的預(yù)處理(以便更好更快的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移)。最常用的思想就是用枚舉最后一次操作。 狀態(tài)壓縮DP,又叫帶集合的動(dòng)態(tài)規(guī)劃:題目特點(diǎn)是有一維的維數(shù)特別小。類(lèi)似TSP問(wèn)題的DP: 狀態(tài)劃分比較困難的題目: 樹(shù)形DP: 四邊形不等式的應(yīng)用探索:四邊形不等式通常應(yīng)用是把O(n^3)復(fù)雜度O(n^2) 高檔數(shù)據(jù)結(jié)構(gòu)的應(yīng)用 并查集的應(yīng)用: 巧用并查集中的路徑壓縮思想: 堆的利用: 線段樹(shù)的應(yīng)用: 總結(jié)用線段樹(shù)解題的方法 根據(jù)題目要求將一個(gè)區(qū)間建成線段樹(shù),一般的題目都需要對(duì)坐標(biāo)離散。建樹(shù)時(shí),不要拘泥于線段樹(shù)這個(gè)名字而只將線段建樹(shù),只要是表示區(qū)間,而且區(qū)間是由單位元素(可以是一個(gè)點(diǎn)、線段、或數(shù)組中一個(gè)值)組成的,都可以建線段樹(shù);不要拘泥于一維,根據(jù)題目要求可以建立面積樹(shù)、體積樹(shù)等等 樹(shù)的每個(gè)節(jié)點(diǎn)根據(jù)題目所需,設(shè)置變量記錄要求的值 用樹(shù)形結(jié)構(gòu)來(lái)維護(hù)這些變量:如果是求總數(shù),則是左右兒子總數(shù)之和加上本節(jié)點(diǎn)的總數(shù),如果要求最值,則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時(shí),都只對(duì)O(logL)個(gè)節(jié)點(diǎn)修改這個(gè)特點(diǎn),在O(logL)的時(shí)間內(nèi)維護(hù)修改后相關(guān)節(jié)點(diǎn)的變量。 在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中,要靈活的運(yùn)用子樹(shù)的收縮與葉子節(jié)點(diǎn)的釋放,避免重復(fù)操作。 Trie的應(yīng)用:; Trie圖的應(yīng)用探索: 后綴數(shù)組的應(yīng)用研究: 在字符串處理當(dāng)中,后綴樹(shù)和后綴數(shù)組都是非常有力的工具,其中后綴樹(shù)了解得比較多,關(guān)于后綴數(shù)組則很少見(jiàn)于國(guó)內(nèi)的資料。其實(shí)后綴數(shù)組是后綴樹(shù)的一個(gè)非常精巧的替代品,它比后綴樹(shù)容易編程實(shí)現(xiàn),能夠?qū)崿F(xiàn)后綴樹(shù)的很多功能而時(shí)間復(fù)雜度也不太遜色,并且,它比后綴樹(shù)所占用的空間小很多。 樹(shù)狀數(shù)組的應(yīng)用探索:; 計(jì)算幾何 掌握基本算法的實(shí)現(xiàn)。凸包的應(yīng)用:; 半平面交算法的應(yīng)用:; 幾何+模擬類(lèi)題目:幾何設(shè)計(jì)好算法,模擬控制好精度。掃描法:; 轉(zhuǎn)化法:ZOJ 1606 將求所圍的格子數(shù),巧妙的轉(zhuǎn)化為求多邊形的面積。離散法思想的應(yīng)用:; 經(jīng)典算法:找平面上的最近點(diǎn)對(duì)。 貪心 矩形切割 二分思想應(yīng)用 活用經(jīng)典算法 利用歸并排序算法思想求數(shù)列的逆序?qū)?shù): 利用快速排序算法思想,查詢N個(gè)數(shù)中的第K小數(shù): 博弈問(wèn)題 博弈類(lèi)題目通常用三類(lèi)解法:第一類(lèi)推結(jié)論; 第二類(lèi)遞推,找N位置,P位置; 第三類(lèi)SG函數(shù)的應(yīng)用。第四類(lèi)極大極小法,甚至配合上αβ剪枝。最難掌握的就是第四類(lèi)極大極小法。 第一類(lèi):推結(jié)論。典型題目: 第二類(lèi):遞推。典型題目: 比如有向無(wú)環(huán)圖類(lèi)型的博弈。在一個(gè)有向圖中,我們把選手I有必勝策略的初始位置稱(chēng)為N位置(Next player winning),其余的位置被稱(chēng)為P位置(Previous player winning)。很顯然,P位置和N位置應(yīng)該具有如下性質(zhì): 1. 所有的結(jié)束位置都是P位置。 2. 對(duì)于每一個(gè)N位置,至少存在一種移動(dòng)可以將棋子移動(dòng)到一個(gè)P位置。3. 對(duì)于每一個(gè)P位置,它的每一種移動(dòng)都會(huì)將棋子移到一個(gè)N位置。 這樣,獲勝的策略就是每次都把棋子移動(dòng)到一個(gè)P位置,因?yàn)樵谝粋€(gè)P位置,你的對(duì)手只能將棋子移動(dòng)到一個(gè)N位置,然后你總有一種方法再把棋子移動(dòng)到一個(gè)P位置。一直這樣移動(dòng),最后你一定會(huì)將棋子移動(dòng)到一個(gè)結(jié)束位置(結(jié)束位置是P位置),這時(shí)你的對(duì)手將無(wú)法在移動(dòng)棋子,你便贏得了勝利。 與此同時(shí),得到了這些性質(zhì),我們便很容易通過(guò)倒退的方法求出哪些位置是P位置,哪些位置是N位置,具體的算法為: 1. 將所有的結(jié)束位置標(biāo)為P位置。 2. 將所有能一步到達(dá)P位置的點(diǎn)標(biāo)為N位置。 3. 找出所有只能到達(dá)N位置的點(diǎn),將它們標(biāo)為P位置。 4. 如果在第三步中沒(méi)有找到新的被標(biāo)為P位置的點(diǎn),則算法結(jié)束,否則轉(zhuǎn)到步驟2。這樣我們便確定了所有位置,對(duì)于題目給出的任一初始位置,我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類(lèi):SG函數(shù)的應(yīng)用。 關(guān)于SG函數(shù)的基本知識(shí):對(duì)于一個(gè)有向圖(X, F)來(lái)說(shuō),SG函數(shù)g是一個(gè)在X上的函數(shù),并且它返回一個(gè)非負(fù)整數(shù)值,具體定義為 g(x)?min{n?0,n?g(y)對(duì)于所有y?F(x)} 1. 對(duì)于所有的結(jié)束位置x,g(x)= 0。 2. 對(duì)于每一個(gè)g(x)≠ 0的位置x,在它可以一步到達(dá)的位置中至少存在一個(gè)位置y使得g(y)= 0。 3.對(duì)于每一個(gè)g(x)= 0的位置x,所有可以由它一步到達(dá)的位置y都有g(shù)(y)≠ 0。 定理 如果g(xi)是第i個(gè)有向圖的SG函數(shù)值,i = 1,…,n,那么在由這n個(gè)有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四類(lèi):極大極小法。 典型題目:ZOJ 1155:Triangle War ZOJ 1993:A Number Game 矩陣妙用 矩陣最基本的妙用就是利用快速乘法O(logn)來(lái)求解遞推關(guān)系(最基本的就是求Fibonacci數(shù)列的某項(xiàng))和各種圖形變換,以及利用高斯消元法變成階梯矩陣。典型題目: 數(shù)學(xué)模型舉例 向量思想的應(yīng)用: UVA 10089:注意降維和向量的規(guī)范化 ; 利用復(fù)數(shù)思想進(jìn)行向量旋轉(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的元素個(gè)數(shù)不會(huì)超過(guò)100,因此可以考慮用一個(gè)數(shù)代替一個(gè)集合,首先把所有的運(yùn)算結(jié)果都用預(yù)處理算出來(lái),到計(jì)算的時(shí)候只要用O(1)的復(fù)雜度就可以完成一次運(yùn)算。 組合數(shù)學(xué) Polya定理則是解決同構(gòu)染色計(jì)數(shù)問(wèn)題的有力工具。 補(bǔ)集轉(zhuǎn)化思想 ZOJ 單色三角形: 字符串相關(guān) 擴(kuò)展的KMP算法應(yīng)用:;最長(zhǎng)回文串; 最長(zhǎng)公共子串; 最長(zhǎng)公共前綴; 填充問(wèn)題 高精度運(yùn)算 三維空間問(wèn)題專(zhuān)題 無(wú)論什么問(wèn)題,一旦擴(kuò)展到三難空間,就變得很有難度了。三維空間的問(wèn)題,很考代碼實(shí)現(xiàn)能力。 其它問(wèn)題的心得 解決一些判斷同構(gòu)問(wèn)題的方法:同構(gòu)的關(guān)鍵在于一一對(duì)應(yīng),而如果枚舉一一對(duì)應(yīng)的關(guān)系,時(shí)間復(fù)雜度相當(dāng)?shù)母撸米钚”硎?,就能把一個(gè)事物的本質(zhì)表示出來(lái)。求最小表示時(shí),我們一定要仔細(xì)分析,將一切能區(qū)分兩個(gè)元素的條件都在最小表示中體現(xiàn),而且又不能主觀的加上其他條件。得到最小表示后,我們往往還要尋求適當(dāng)?shù)摹⒏咝У钠ヅ渌惴ǎɡ鏚MP字符匹配之類(lèi)的),來(lái)比較最小表示是否相同,這里常常要將我們熟悉的高效算法進(jìn)行推廣 算法分析與設(shè)計(jì)總結(jié)報(bào)告 71110415 錢(qián)玉明 在計(jì)算機(jī)軟件專(zhuān)業(yè)中,算法分析與設(shè)計(jì)是一門(mén)非常重要的課程,很多人為它如癡如醉。很多問(wèn)題的解決,程序的編寫(xiě)都要依賴它,在軟件還是面向過(guò)程的階段,就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個(gè)公式。算法的學(xué)習(xí)對(duì)于培養(yǎng)一個(gè)人的邏輯思維能力是有極大幫助的,它可以培養(yǎng)我們養(yǎng)成思考分析問(wèn)題,解決問(wèn)題的能力。作為IT行業(yè)學(xué)生,學(xué)習(xí)算法無(wú)疑會(huì)增強(qiáng)自己的競(jìng)爭(zhēng)力,修煉自己的“內(nèi)功”。 下面我將談?wù)勎覍?duì)這門(mén)課程的心得與體會(huì)。 一、數(shù)學(xué)是算法的基礎(chǔ) 經(jīng)過(guò)這門(mén)課的學(xué)習(xí),我深刻的領(lǐng)悟到數(shù)學(xué)是一切算法分析與設(shè)計(jì)的基礎(chǔ)。這門(mén)課的很多時(shí)間多花在了數(shù)學(xué)公式定理的引入和證明上。雖然很枯燥,但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來(lái)的,尤其是算法性能的分析更是與數(shù)學(xué)息息相關(guān)。其中有幾個(gè)定理令我印象深刻。 ①主定理 本門(mén)課中它主要應(yīng)用在分治法性能分析上。例如:T(n)=a*T(n/b)+f(n),它可以看作一個(gè)大問(wèn)題分解為a個(gè)子問(wèn)題,其中子問(wèn)題的規(guī)模為b。而f(n)可看作這些子問(wèn)題的組合時(shí)的消耗。這些可以利用主定理的相關(guān)結(jié)論進(jìn)行分析處理。當(dāng)f(n)量級(jí)高于nlogba時(shí),我們可以設(shè)法降低子問(wèn)題組合時(shí)的消耗來(lái)提高性能。反之我們可以降低nlogba的消耗,即可以擴(kuò)大問(wèn)題的規(guī)?;蛘邷p小子問(wèn)題的個(gè)數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進(jìn)行有效的改進(jìn)。 ②隨機(jī)算法中的許多定理的運(yùn)用 在這門(mén)課中,我學(xué)到了以前從未遇見(jiàn)過(guò)的隨機(jī)算法,它給予我很大的啟示。隨機(jī)算法不隨機(jī),它可通過(guò)多次的嘗試來(lái)降低它的錯(cuò)誤率以至于可以忽略不計(jì)。這些都不是空穴來(lái)風(fēng),它是建立在嚴(yán)格的定理的證明上。如素?cái)?shù)判定定理是個(gè)很明顯的例子。它運(yùn)用了包括費(fèi)馬小定理在內(nèi)的各種定理。將這些定理進(jìn)行有效的組合利用,才得出行之有效的素?cái)?shù)判定的定理。尤其是對(duì)尋找證據(jù)數(shù)算法的改進(jìn)的依據(jù),也是建立在3個(gè)定理上。還有檢查字符串是否匹配也是運(yùn)用了許多定理:指紋的運(yùn)用,理論出錯(cuò)率的計(jì)算,算法性能的評(píng)價(jià)也都是建立在數(shù)學(xué)定理的運(yùn)用上。 這些算法都給予了我很大啟發(fā),要想學(xué)好算法,學(xué)好數(shù)學(xué)是必不可少的。沒(méi)有深厚的數(shù)學(xué)功力作為地基,即使再漂亮的算法框架,代碼實(shí)現(xiàn)也只能是根底淺的墻上蘆葦。 二、算法的核心是思想 我們學(xué)習(xí)這門(mén)課不是僅僅掌握那幾個(gè)經(jīng)典算法例子,更重要的是為了學(xué)習(xí)蘊(yùn)含在其中的思想方法。為什么呢?舉個(gè)例子。有同學(xué)曾問(wèn)我這樣一個(gè)問(wèn)題:1000只瓶子裝滿水,但有一瓶有毒,且毒發(fā)期為1個(gè)星期?,F(xiàn)在用10只老鼠在一個(gè)星期內(nèi)判斷那只瓶子有毒,每只老鼠可以喝多個(gè)瓶子的水,每個(gè)瓶子可以只喝一點(diǎn)。問(wèn)如何解決?其實(shí)一開(kāi)始我也一頭霧水,但是他提醒我跟計(jì)算機(jī)領(lǐng)域相關(guān),我就立馬有了思路,運(yùn)用二進(jìn)制。因?yàn)橛?jì)算機(jī)的最基本思想就是二進(jìn)制。所以說(shuō),我們不僅要學(xué)習(xí)算法,更得學(xué)習(xí)思想方法。 ①算法最基本的設(shè)計(jì)方法包括分治法,動(dòng)態(tài)規(guī)劃法,貪心法,周游法,回溯法,分支定界法。我們可利用分治法做快速排序,降低找n個(gè)元素中最大元和最小元的量級(jí),降低n位二進(jìn)制x和y相乘的量級(jí),做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問(wèn)題分解為規(guī)模較小的獨(dú)立的子問(wèn)題,關(guān)鍵是子問(wèn)題要與原問(wèn)題同類(lèi),可以采取平衡法來(lái)提高性能。 動(dòng)態(tài)規(guī)劃法是把大問(wèn)題分解為子問(wèn)題,但是子問(wèn)題是重復(fù)的,后面的問(wèn)題可以利用前面解決過(guò)的問(wèn)題的結(jié)果。如構(gòu)造最優(yōu)二叉查找樹(shù),解決矩陣連乘時(shí)最小計(jì)算次數(shù)問(wèn)題,尋找最長(zhǎng)公共子序列等等。 貪心法就是局部最優(yōu)法,先使局部最優(yōu),再依次構(gòu)造出更大的局部直至整體。如Kruscal最小生成樹(shù)算法,求哈夫曼編碼問(wèn)題。 周游法就是簡(jiǎn)單理解就是采取一定的策略遍歷圖中所有的點(diǎn),典型的應(yīng)用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。 回溯法就是就是在滿足一定的條件后就往前走,當(dāng)走到某步時(shí),發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應(yīng)用就是8皇后問(wèn)題,平面點(diǎn)集的凸包問(wèn)題和0-1背包問(wèn)題。 分支定界法:它是解決整數(shù)規(guī)劃問(wèn)題一種最常用的方法。典型應(yīng)用就是解決整數(shù)規(guī)劃問(wèn)題。 ②評(píng)價(jià)算法性能的方法如平攤分析中的聚集法,會(huì)計(jì)法和勢(shì)能法。聚集法就是把指令分為幾類(lèi),計(jì)算每一類(lèi)的消耗,再全部疊加起來(lái)。會(huì)計(jì)法就是計(jì)算某個(gè)指令時(shí)提前將另一個(gè)指令的消耗也算進(jìn)去,以后計(jì)算另一個(gè)指令時(shí)就不必再算了。勢(shì)能法計(jì)算每一步的勢(shì)的變化以及執(zhí)行這步指令的消耗,再將每一步消耗全部累計(jì)。 這幾種方法都是平攤分析法,平攤分析的實(shí)質(zhì)就是總體考慮指令的消耗時(shí)間,盡管某些指令的消耗時(shí)間很大也可以忽略不計(jì)。上述三種方法難易程度差不多,每種方法都有屬于它的難點(diǎn)。如聚集法中如何將指令有效分類(lèi),會(huì)計(jì)法中用什么指令提前計(jì)算什么指令的消耗,勢(shì)能法中如何選取勢(shì)能。因此掌握這些方法原理還不夠,還要學(xué)會(huì)去應(yīng)用,在具體的問(wèn)題中去判斷分析。 三、算法與應(yīng)用緊密相關(guān) 我認(rèn)為學(xué)習(xí)算法不能局限于書(shū)本上的理論運(yùn)算,局限于如何提高性能以降低復(fù)雜度,我們要將它與實(shí)際生活聯(lián)系起來(lái)。其實(shí)算法問(wèn)題的產(chǎn)生就來(lái)自于生活,設(shè)計(jì)出高效的算法就是為了更好的應(yīng)用。如尋找最長(zhǎng)公共子序列算法可以應(yīng)用在生物信息學(xué)中通過(guò)檢測(cè)相似DNA片段的相似成分來(lái)檢測(cè)生物特性的相似性,也可以用來(lái)判斷兩個(gè)字符串的相近性,這可應(yīng)用在數(shù)據(jù)挖掘中??焖俑盗⑷~變換(FFT)可應(yīng)用在計(jì)算多項(xiàng)式相乘上來(lái)降低復(fù)雜度,脫線min算法就是利用了Union-Find這種結(jié)構(gòu)。還有圖中相關(guān)算法,它對(duì)于解決網(wǎng)絡(luò)流量分配問(wèn)題起了很大的幫助,等等。 這些應(yīng)用給了我很大的啟發(fā):因?yàn)閱渭冎v一個(gè)Union-Find算法,即使了解了它的實(shí)現(xiàn)原理,遇到具體的實(shí)際問(wèn)題也不知去如何應(yīng)用。這就要求我們要將自己學(xué)到的算法要和實(shí)際問(wèn)題結(jié)合起來(lái),不能停留在思想方法階段,要學(xué)以致用,做到具體問(wèn)題具體分析。 四、對(duì)計(jì)算模型和NP問(wèn)題的理解 由于對(duì)這部分內(nèi)容不是很理解,所以就粗淺的談一下我的看法。 首先談到計(jì)算模型,就不得不提到圖靈計(jì)算,他將基本的計(jì)算抽象化,造出一個(gè)圖靈機(jī),得出了計(jì)算的本質(zhì)。并提出圖靈機(jī)可以計(jì)算的問(wèn)題都是可以計(jì)算的,否則就是不可計(jì)算的。由此引申出一個(gè)著名論題:任何合理的計(jì)算模型都是相互等價(jià)的。它說(shuō)明了可計(jì)算性本身不依賴于任何具體的模型而客觀存在。 NP問(wèn)題比較復(fù)雜,我認(rèn)為它是制約算法發(fā)展的瓶頸,但這也是算法分析的魅力所在。NP問(wèn)題一般可分為3類(lèi),NP-C問(wèn)題,NP-hard問(wèn)題以及頑型問(wèn)題。NP-C它有個(gè)特殊的性質(zhì),如果存在一個(gè)NP-C問(wèn)題找到一個(gè)多項(xiàng)式時(shí)間的解法,則所有的NP-C問(wèn)題都能找到多項(xiàng)式時(shí)間解法。如哈密頓回路問(wèn)題。NP-hard主要是解決最優(yōu)化問(wèn)題。它不一定是NP問(wèn)題。這些問(wèn)題在規(guī)模較小時(shí)可以找出精確解,但是規(guī)模大時(shí),就因時(shí)間太復(fù)雜而找不到最優(yōu)解。此時(shí)一般會(huì)采用近似算法的解法。頑型問(wèn)題就是已經(jīng)證明不可能有多項(xiàng)式時(shí)間的算法,如漢諾塔問(wèn)題。 最后談?wù)剬?duì)這門(mén)課程的建議 ①對(duì)于這門(mén)算法課,我認(rèn)為應(yīng)該加強(qiáng)對(duì)算法思想方法的學(xué)習(xí)。所以我建議老師可不可以先拋出問(wèn)題而不給出答案,講完一章,再發(fā)課件。讓我們先思考一會(huì)兒,或者給出個(gè)獎(jiǎng)勵(lì)機(jī)制,誰(shuí)能解決這個(gè)問(wèn)題,平時(shí)成績(jī)加分。這在一定程度上會(huì)將強(qiáng)我們思考分析問(wèn)題的能力。因?yàn)槲腋杏X(jué)到,一個(gè)問(wèn)題出來(lái),未經(jīng)過(guò)思考就已經(jīng)知曉它的答案,就沒(méi)什么意思,得不到提高,而且也不能加深對(duì)問(wèn)題的思考和理解。下次遇到類(lèi)似的問(wèn)題也就沒(méi)有什么印象。而且上課讓我們思考,點(diǎn)名回答問(wèn)題可以一定程度上有效的防止不認(rèn)真聽(tīng)課的現(xiàn)象。 ②作業(yè)安排的不是很恰當(dāng)。本門(mén)課主要安排了三次作業(yè),個(gè)人感覺(jué)只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實(shí)現(xiàn)一下偽代碼,沒(méi)有太多的技術(shù)含量。而且對(duì)于培養(yǎng)我們的解決問(wèn)題的能力也沒(méi)有太多的幫助,因?yàn)檫@間接成為了程序設(shè)計(jì)題,不是算法設(shè)計(jì)題。 ③本門(mén)課的時(shí)間安排的不太恰當(dāng),因?yàn)楸緦W(xué)期的課程太多,壓力太大。沒(méi)有太多的時(shí)間去學(xué)習(xí)這門(mén)課程。因?yàn)槲蚁嘈糯蠹叶紝?duì)它感興趣,比較重視,想花功夫,但苦于沒(méi)時(shí)間。所以可不可以將課程提前一個(gè)學(xué)期,那時(shí)候離散數(shù)學(xué)也已經(jīng)學(xué)過(guò),且課程的壓力也不是很大。錯(cuò)開(kāi)時(shí)間的話,我覺(jué)得應(yīng)該能夠更好提高大家算法分析設(shè)計(jì)的能力。 認(rèn)識(shí)數(shù)位 教學(xué)目標(biāo): 知識(shí)與技能:。通過(guò)計(jì)數(shù)器使學(xué)生認(rèn)識(shí)個(gè)位,十位、百位,了解個(gè)位、十位上數(shù)表示含義,會(huì)正確讀、寫(xiě)100以內(nèi)的數(shù)。 過(guò)程與方法:。通過(guò)動(dòng)手操作、觀察,直觀體驗(yàn)數(shù)的意義,數(shù)的讀、寫(xiě)法的過(guò)程方法。 情感態(tài)度、價(jià)值觀:在學(xué)習(xí)中建立數(shù)感,能積極參與學(xué)習(xí),形成獨(dú)立思考和合作學(xué)習(xí)的習(xí)慣。 學(xué)習(xí)方式:動(dòng)手操作,自主合作交流探究。 教學(xué)準(zhǔn)備:每人一個(gè)計(jì)數(shù)器,(學(xué)具)幻燈片(分片)數(shù)位、數(shù)字卡片。 教學(xué)過(guò)程: 環(huán)節(jié) 學(xué)生活動(dòng) 教師活動(dòng) 設(shè)計(jì)意圖 創(chuàng)設(shè)情境 生答 出示計(jì)數(shù)器 同學(xué)們你們認(rèn)識(shí)這是什么學(xué)具嗎? (生如果不認(rèn)識(shí),師直接點(diǎn)出,這是計(jì)數(shù)器,是用來(lái)學(xué)習(xí)數(shù)用的)。 激發(fā)學(xué)生強(qiáng)烈的學(xué)習(xí)欲望。 探 究 與 體 驗(yàn) 自由讀,在計(jì)數(shù)器上標(biāo)出個(gè)、十、百位。 從右邊數(shù)第一位是個(gè)位,第二位是十位,第三位是百位。 指生讀,齊讀。 學(xué)生動(dòng)手撥 讀作二十四,寫(xiě)作24。 因?yàn)槭粨艿氖?,個(gè)位撥的是4,所以就是24。 24中的2表示2個(gè)十,4表示4個(gè)一。 自己在計(jì)數(shù)器上撥數(shù) 讀一讀、說(shuō)一說(shuō)、寫(xiě)一寫(xiě)。 匯報(bào): 讀作四十二,寫(xiě)做42。因?yàn)?在十位上表示4個(gè)十,2在個(gè)位上表示2個(gè)一。所以寫(xiě)做42。 學(xué)生動(dòng)手撥數(shù)、讀數(shù) 說(shuō)意義,“十位上的5表示5個(gè)十,個(gè)位上的5表示5個(gè)一”。 學(xué)生看圖,照樣子撥珠,同桌交流,匯報(bào):計(jì)數(shù)器的十位上的數(shù)是6,表示6個(gè)十,個(gè)位上沒(méi)有珠,表示一個(gè)也沒(méi)有用零表示。這個(gè)計(jì)數(shù)器上的珠子表示60。 1、認(rèn)識(shí)計(jì)數(shù)器上的數(shù)位。 幻燈片出示。 同學(xué)們,從右邊數(shù)第一位、第二位、第三位各是什么位?(若學(xué)生回答不出來(lái),教師講解)。從右邊數(shù)第一位是個(gè)位,第二位是十位,第三位是百位。 2、撥數(shù),寫(xiě)數(shù)、讀數(shù)。 (1)教師說(shuō)數(shù)學(xué)生撥。 在計(jì)數(shù)器的十位上撥2,個(gè)位上撥4。這個(gè)數(shù)讀作多少?該怎樣寫(xiě)出來(lái)?你們?cè)囍鴵芤粨堋⒄f(shuō)一說(shuō)。你是怎么知道的? (2)寫(xiě)法及數(shù)表示的意義: 十位上是2,就在十位上寫(xiě)2,表示2個(gè)十。個(gè)位上是4,就在個(gè)位上寫(xiě)4,表示4個(gè)一。讀作二十四。板書(shū)24。 同桌同學(xué)互相說(shuō)一說(shuō)24中2和4各表示什么? 1、練習(xí)撥一撥、讀一讀。 教師說(shuō)數(shù),在十位上撥4 在個(gè)位上撥2,讀讀、寫(xiě)寫(xiě)、說(shuō)說(shuō)你是怎么知道的? 讓學(xué)生在計(jì)數(shù)器上撥出55。 (讓學(xué)生說(shuō)說(shuō)這兩個(gè)5的意義有什么不同) 4、出示圖片(試一試) 照樣子撥珠再寫(xiě)數(shù),并讀出來(lái) 重點(diǎn)引導(dǎo):第2個(gè)計(jì)數(shù)器,個(gè)位上沒(méi)珠,怎么辦?寫(xiě)幾表示 引導(dǎo)學(xué)生歸納寫(xiě)數(shù)的方法。 計(jì)數(shù)器的十位上是幾就在十位上寫(xiě)幾,計(jì)數(shù)器的個(gè)位上是幾就在個(gè)位上寫(xiě)幾。通過(guò)自己利用計(jì)數(shù)器撥數(shù)、讀數(shù)、寫(xiě)數(shù)等多種形式調(diào)動(dòng)學(xué)生的多種感官參與學(xué)習(xí)活動(dòng),使學(xué)生對(duì)數(shù)的寫(xiě)法、讀法以及數(shù)位有了進(jìn)一步的體驗(yàn)和感悟,對(duì)數(shù)的意義也有了初步的了解。 在學(xué)生操作的同時(shí),注重讓學(xué)生用語(yǔ)言表達(dá)數(shù)的意義,這樣學(xué)生對(duì)數(shù)的讀法、寫(xiě)法、數(shù)位理解的就更加深刻了。 鞏 固 與 應(yīng) 用 1、題:獨(dú)立完成 集體訂正。 2、題同桌互讀 指生讀 3、題在計(jì)數(shù)器上撥一撥,然后寫(xiě)出來(lái)。 4、題:同桌交流,填空。完成練習(xí)1、2、3、4題數(shù)字游戲。 4題:指導(dǎo)第1圖 1個(gè)〇是十,4個(gè)〇是多少? 1個(gè)△是一5個(gè)△是多少? 4個(gè)十5個(gè)一合起來(lái)是多少? 數(shù)字游戲:分組進(jìn)行:一人說(shuō)數(shù)一人在數(shù)位表上撥。多種形式的練習(xí),鞏固加深理解了所學(xué)知識(shí),同時(shí)也激發(fā)了學(xué)生學(xué)習(xí)數(shù)學(xué)的熱情。 1.去掉超鏈接的下畫(huà)線: 在 我們可以通過(guò)使用DataTime這個(gè)類(lèi)來(lái)獲取當(dāng)前的時(shí)間。通過(guò)調(diào)用類(lèi)中的各種方法我們可以獲取不同的時(shí)間:如:日期(2008-09-04)、時(shí)間(12:12:12)、日期+時(shí)間(2008-09-04 12:11:10)等。 //獲取日期+時(shí)間 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 //獲取時(shí)間 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(); 獲取小時(shí) // 20 DateTime.Now.Minute.ToString(); 獲取分鐘 // 31 DateTime.Now.Second.ToString(); 獲取秒數(shù) // 45 //n為一個(gè)數(shù),可以數(shù)整數(shù),也可以事小數(shù) dt.AddYears(n).ToString(); //時(shí)間加n年 dt.AddDays(n).ToString(); //加n天 dt.AddHours(n).ToString(); //加n小時(shí) dt.AddMonths(n).ToString(); //加n個(gè)月 dt.AddSeconds(n).ToString(); //加n秒 dt.AddMinutes(n).ToString(); //加n分 SQL語(yǔ)句使用時(shí)間和日期的函數(shù) getdate():獲取系統(tǒng)當(dāng)前時(shí)間 dateadd(datepart,number,date):計(jì)算在一個(gè)時(shí)間的基礎(chǔ)上增加一個(gè)時(shí)間后的新時(shí)間值,比如:dateadd(yy,30,getdate())datediff(datepart,startdate,enddate):計(jì)算兩個(gè)時(shí)間的差值,比如:datediff(yy,getdate(),'2008-08-08')dataname(datepart,date):獲取時(shí)間不同部分的值,返回值為字符串 datepart(datepart,date):和datename相似,只是返回值為整型 day(date):獲取指定時(shí)間的天數(shù) month(date):獲取指定時(shí)間的月份 year(date):獲取指定時(shí)間的年份 select year(getdate()):當(dāng)前年份第二篇:算法總結(jié)
第三篇:算法總結(jié)
第四篇:認(rèn)識(shí)數(shù)位
第五篇:web 算法總結(jié)