2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 算法基礎(chǔ)

2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 算法基礎(chǔ) 學(xué)習(xí)過(guò)程序設(shè)計(jì)的人對(duì)算法這個(gè)詞并不陌生，從廣義上講，算法是指為解決一個(gè)問(wèn)題而采用的方法和步驟；從程序計(jì)設(shè)的角度上講，算法是指利用程序設(shè)計(jì)語(yǔ)言的各種語(yǔ)句，為解決特定的問(wèn)題而構(gòu)成的各種邏輯組合。我們?cè)诰帉?xiě)程序的過(guò)程就是在實(shí)施某種算法，因此程序設(shè)計(jì)的實(shí)質(zhì)就是用計(jì)算機(jī)語(yǔ)言構(gòu)造解決問(wèn)題的算法。算法是程序設(shè)計(jì)的靈魂，一個(gè)好的程序必須有一個(gè)好的算法，一個(gè)沒(méi)有有效算法的程序就像一個(gè)沒(méi)有靈魂的軀體。 算法具有五個(gè)特征： 1、有窮性： 一個(gè)算法應(yīng)包括有限的運(yùn)算步驟，執(zhí)行了有窮的操作后將終止運(yùn)算，不能是個(gè)死循環(huán)； 2、確切性： 算法的每一步驟必須有確切的定義，讀者理解時(shí)不會(huì)產(chǎn)生二義性。并且，在任何條件下，算法只有唯一的一條執(zhí)行路徑，對(duì)于相同的輸入只能得出相同的輸出。如在算法中不允許有“計(jì)算8/0”或“將7或8與x相加”之類的運(yùn)算，因?yàn)榍罢叩挠?jì)算結(jié)果是什么不清楚，而后者對(duì)于兩種可能的運(yùn)算應(yīng)做哪一種也不知道。 3、輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以描述運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定義了初始條件。如在5個(gè)數(shù)中找出最小的數(shù)，則有5個(gè)輸入。 4、輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果，這是算法設(shè)計(jì)的目的。它們是同輸入有著某種特定關(guān)系的量。如上述在5個(gè)數(shù)中找出最小的數(shù)，它的出輸出為最小的數(shù)。如果一個(gè)程序沒(méi)有輸出，這個(gè)程序就毫無(wú)意義了； 5、可行性： 算法中每一步運(yùn)算應(yīng)該是可行的。算法原則上能夠精確地運(yùn)行，而且人能用筆和紙做有限次運(yùn)算后即可完成。 如何來(lái)評(píng)價(jià)一個(gè)算法的好壞呢？主要是從兩個(gè)方面： 一是看算法運(yùn)行所占用的時(shí)間；我們用時(shí)間復(fù)雜度來(lái)衡量，例如：在以下3個(gè)程序中， （1）x:=x+1 （2）for i:=1 to n do x:=x+1 （3）for i:=1 to n do for j:=1 to n do x:=x+1 含基本操作“x增1”的語(yǔ)句x:=x+1的出現(xiàn)的次數(shù)分別為1，n和n2則這三個(gè)程序段的時(shí)間復(fù)雜度分別為O（1），O（n），O（n2），分別稱為常量階、線性階和平方階。在算法時(shí)間復(fù)雜度的表示中，還有可能出現(xiàn)的有：對(duì)數(shù)階O(log n)，指數(shù)階O(2n)等。在n很大時(shí)，不同數(shù)量級(jí)的時(shí)間復(fù)雜度有：O(1)< O(log n)<O(n)< O(nlog n)<O(n2) <O(n3) <O(2n)，很顯然，指數(shù)階的算法不是一個(gè)好的算法。 二是看算法運(yùn)行時(shí)所占用的空間，既空間復(fù)雜度。由于當(dāng)今計(jì)算機(jī)硬件技術(shù)發(fā)展很快，程序所能支配的自由空間一般比較充分，所以空間復(fù)雜度就不如時(shí)間復(fù)雜度那么重要了，有許多問(wèn)題人們主要是研究其算法的時(shí)間復(fù)雜度，而很少討論它的空間耗費(fèi)。 時(shí)間復(fù)雜性和空間復(fù)雜性在一定條件下是可以相互轉(zhuǎn)化的。在中學(xué)生信息學(xué)奧賽中，對(duì)程序的運(yùn)行時(shí)間作出了嚴(yán)格的限制，如果運(yùn)行時(shí)間超出了限定就會(huì)判錯(cuò)，因此在設(shè)計(jì)算法時(shí)首先要考慮的是時(shí)間因素，必要時(shí)可以以犧牲空間來(lái)?yè)Q取時(shí)間，動(dòng)態(tài)規(guī)劃法就是一種以犧牲空間換取時(shí)間的有效算法。對(duì)于空間因素，視題目的要求而定，一般可以不作太多的考慮。 我們通過(guò)一個(gè)簡(jiǎn)單的數(shù)值計(jì)算問(wèn)題，來(lái)比較兩個(gè)不同算法的效率（在這里只比較時(shí)間復(fù)雜度）。 例：求N！所產(chǎn)生的數(shù)后面有多少個(gè)0（中間的0不計(jì)）。 算法一：從1乘到n，每乘一個(gè)數(shù)判斷一次，若后面有0則去掉后面的0，并記下0的個(gè)數(shù)。為了不超出數(shù)的表示范圍，去掉與生成0無(wú)關(guān)的數(shù)，只保留有效位數(shù)，當(dāng)乘完n次后就得到0的個(gè)數(shù)。（pascal程序如下） var　i,t,n,sum:longint; begin 　t:=0; sum:=1; readln(n); 　for i:=1 to n do 　begin 　 sum:=sum*i; 　 while sum mod 10=0 do 　 begin 　 sum:=sum div 10; 　 inc(t);{計(jì)數(shù)器增加1} 　 end; 　 sum:=sum mod 1000;{舍去與生成0無(wú)關(guān)的數(shù)} 　end; 　writeln(t:6); end. 算法二：此題中生成O的個(gè)數(shù)只與含5的個(gè)數(shù)有關(guān)，n！的分解數(shù)中含5的個(gè)數(shù)就等于末尾O的個(gè)數(shù)，因此問(wèn)題轉(zhuǎn)化為直接求n！的分解數(shù)中含5的個(gè)數(shù)。 var t,n:integer; begin 　readln(n); 　t:=0; 　repeat 　 n:=n div 5 ; 　 inc(t,n); {計(jì)數(shù)器增加n} 　until n<5; 　writeln(t:6); end. 分析對(duì)比兩種算法就不難看出，它們的時(shí)間復(fù)雜度分別為O（N）、O（logN）,算法二的執(zhí)行時(shí)間遠(yuǎn)遠(yuǎn)小于算法一的執(zhí)行時(shí)間。 在信息學(xué)奧賽中，其主要任務(wù)就是設(shè)計(jì)一個(gè)有效的算法，去求解所給出的問(wèn)題。如果僅僅學(xué)會(huì)一種程序設(shè)計(jì)語(yǔ)言，而沒(méi)學(xué)過(guò)算法的選手在比賽中是不會(huì)取得好的成績(jī)的，選手水平的高低在于能否設(shè)計(jì)出好的算法。