信息學(xué)奧賽——算法入門教程

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

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

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

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

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

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

7、.............13遞推法應(yīng)用 .........................................................................................................................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細(xì)心整理開展很快，程序所能支配的自由空間一般比擬充分，所以空間困難度就不如時(shí)間 困難度那么重要了，

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

14、的效率〔在這里只比擬時(shí)間困難度〕 。例：求 N！所產(chǎn)生的數(shù)后面有多少個(gè) 0〔中間的 0 不計(jì)〕 。算法一：從 1 乘到 n，每乘一個(gè)數(shù)判定一次，假設(shè)后面有 0 那么去掉后面的 0， 并登記 0 的個(gè)數(shù)。為了不超出數(shù)的表示范圍，去掉與生成 0 無關(guān)的數(shù)，只保存有 效位數(shù)，當(dāng)乘完 n 次后就得到 0 的個(gè)數(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);{計(jì)數(shù)器增加 1}end;sum:=sum mod 1000;{舍去與生成 0 無關(guān)的數(shù)}end;writeln(t:6); end.算法二：此題中生成 O 的個(gè)數(shù)只與含 5 的個(gè)數(shù)有關(guān)，n！的分解數(shù)中含 5 的個(gè)數(shù)就等于末尾 O 的個(gè)數(shù)，因此問題轉(zhuǎn)化為干脆求 n！的分解數(shù)中含 5