信息學奧賽——算法入門教程

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

2、....................................................................................2信息學奧賽中的根本算法(枚舉法) ...........................................................................................4接受枚舉算法解題的根本思路： ...........

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

4、 ...........................................................................................7回溯根本思想 .......................................................................................................................7

5、信息學奧賽中的根本算法(遞歸算法) .....................................................................................10遞歸算法的定義： ..........................................................................................................

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

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

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

9、...........................................20貪心法應用 .........................................................................................................................21算法在信息學奧賽中的應用〔搜尋法一〕 ...........................

10、..................................................24搜尋算法應用 .....................................................................................................................24算法在信息學奧賽中的應用〔搜尋法二〕 .......................

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

12、.................................................32動態(tài)規(guī)劃算法應用 .............................................................................................................33細心整理開展很快，程序所能支配的自由空間一般比擬充分，所以空間困難度就不如時間 困難度那么重要了，

13、有許多問題人們主要是探究其算法的時間困難度，而很少探 討它的空間消耗。時間困難性和空間困難性在必需條件下是可以相互轉化的。在中學生信息學 奧賽中，對程序的運行時間作出了嚴格的限制，假如運行時間超出了限定就會判錯，因此在設計算法時首先要考慮的是時間因素，必要時可以以犧牲空間來換取 時間，動態(tài)規(guī)劃法就是一種以犧牲空間換取時間的有效算法。對于空間因素，視題目的要求而定，一般可以不作太多的考慮。我們通過一個簡潔的數(shù)值計算問題，來比擬兩個不同算法

14、的效率〔在這里只比擬時間困難度〕 。例：求 N！所產生的數(shù)后面有多少個 0〔中間的 0 不計〕 。算法一：從 1 乘到 n，每乘一個數(shù)判定一次，假設后面有 0 那么去掉后面的 0， 并登記 0 的個數(shù)。為了不超出數(shù)的表示范圍，去掉與生成 0 無關的數(shù)，只保存有 效位數(shù)，當乘完 n 次后就得到 0 的個數(shù)?！瞤ascal 程序如下〕 var i,t,n,sum:longint; begint:=0; sum:=1;readln(n);fo

15、r i:=1 to n dobeginsum:=sum*i;while sum mod 10=0 dobeginsum:=sum div 10;inc(t);{計數(shù)器增加 1}end;sum:=sum mod 1000;{舍去與生成 0 無關的數(shù)}end;writeln(t:6); end.算法二：此題中生成 O 的個數(shù)只與含 5 的個數(shù)有關，n！的分解數(shù)中含 5 的個數(shù)就等于末尾 O 的個數(shù)，因此問題轉化為干脆求 n！的分解數(shù)中含 5