“遞歸算法”的教學設計

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

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

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

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

5、法).....................................................................................10遞歸算法的定義：.............................................................................................................10遞歸算法應用......

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

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

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

9、..................20貪心法應用.........................................................................................................................21算法在信息學奧賽中的應用（搜索法一）......................................................

10、.......................24搜索算法應用.....................................................................................................................24算法在信息學奧賽中的應用（搜索法二）....................................................

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

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

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

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