“遞歸算法”的教學(xué)設(shè)計(jì)

1、全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽算法講義算法講義算法算法基礎(chǔ)篇基礎(chǔ)篇...................................................................................................................................1算法具有五個(gè)特征：.................................

2、..........................................................................2信息學(xué)奧賽中的基本算法(枚舉法)...........................................................................................4采用枚舉算法解題的基本思路：.......................

3、................................................................4枚舉算法應(yīng)用.......................................................................................................................4信息學(xué)奧賽中的基本算法(回溯法).............

4、..............................................................................7回溯基本思想.......................................................................................................................7信息學(xué)奧賽中的基本算法(遞歸算

5、法).....................................................................................10遞歸算法的定義：.............................................................................................................10遞歸算法應(yīng)用......

6、...............................................................................................................10算法在信息學(xué)奧賽中的應(yīng)用(遞推法)...................................................................................13遞推法應(yīng)用

7、.........................................................................................................................14算法在信息學(xué)奧賽中的應(yīng)用(分治法)................................................................................

8、...17分治法應(yīng)用.........................................................................................................................18信息學(xué)奧賽中的基本算法(貪心法).......................................................................

9、..................20貪心法應(yīng)用.........................................................................................................................21算法在信息學(xué)奧賽中的應(yīng)用（搜索法一）......................................................

10、.......................24搜索算法應(yīng)用.....................................................................................................................24算法在信息學(xué)奧賽中的應(yīng)用（搜索法二）....................................................

11、.........................28廣度優(yōu)先算法應(yīng)用.............................................................................................................29算法在信息學(xué)奧賽中的應(yīng)用（動(dòng)態(tài)規(guī)劃法）.......................................................

12、..................32動(dòng)態(tài)規(guī)劃算法應(yīng)用.............................................................................................................33發(fā)展很快，程序所能支配的自由空間一般比較充分，所以空間復(fù)雜度就不如時(shí)間復(fù)雜度那么重要了，有許多問題人們主要是研究其算法的時(shí)間復(fù)雜度，而很少討論它的空間耗費(fèi)。時(shí)間復(fù)

13、雜性和空間復(fù)雜性在一定條件下是可以相互轉(zhuǎn)化的。在中學(xué)生信息學(xué)奧賽中，對(duì)程序的運(yùn)行時(shí)間作出了嚴(yán)格的限制，如果運(yùn)行時(shí)間超出了限定就會(huì)判錯(cuò)，因此在設(shè)計(jì)算法時(shí)首先要考慮的是時(shí)間因素，必要時(shí)可以以犧牲空間來換取時(shí)間，動(dòng)態(tài)規(guī)劃法就是一種以犧牲空間換取時(shí)間的有效算法。對(duì)于空間因素，視題目的要求而定，一般可以不作太多的考慮。我們通過一個(gè)簡(jiǎn)單的數(shù)值計(jì)算問題，來比較兩個(gè)不同算法的效率（在這里只比較時(shí)間復(fù)雜度）。例：求N！所產(chǎn)生的數(shù)后面有多少個(gè)0（中間的0不

14、計(jì)）。算法一：從1乘到n，每乘一個(gè)數(shù)判斷一次，若后面有0則去掉后面的0，并記下0的個(gè)數(shù)。為了不超出數(shù)的表示范圍，去掉與生成0無關(guān)的數(shù)，只保留有效位數(shù)，當(dāng)乘完n次后就得到0的個(gè)數(shù)。（pal程序如下）varitnsum:longintbegint:=0sum:=1readln(n)fi:=1tondobeginsum:=sumiwhilesummod10=0dobeginsum:=sumdiv10inc(t)計(jì)數(shù)器增加1endsum:=su