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

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