信息學奧賽-算法教程-pascal

1、信息學奧賽輔導教程信息學奧賽輔導教程第3章算法與程序設計模塊3.1算法算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。常用的算法：列舉了窮舉搜索、遞歸、回溯、遞推、模擬、分治、貪心、深度優(yōu)先搜索、廣度優(yōu)先搜索等幾種較為常用的算法，沒有做過多的描述，一旦給出具體描述，容易使內(nèi)容加深，產(chǎn)生嚴重學科取向的引導，符合教育部普通高中課程方案的特點，對于這些必需的方法和思想，關鍵不在于學生能不能，而在于教師

2、是否想到，是否有過關注，引發(fā)學生對系統(tǒng)方法和思想的思考，重視建立編程思想，強化編程習慣的培養(yǎng)。3.1.1算法的5個重要特性1有窮性有窮性：一個算法必須總是（對任何合法的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成。2確定性確定性：算法中每一條指令必須有確切的含義，不會產(chǎn)生二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑。3可行性可行性：一個算法是能行的。即算法中描述的操作是執(zhí)行有限次運算來實現(xiàn)的。4輸入輸入：一個算法有

3、零個或多個輸入。5輸出輸出：一個算法有一個或多個輸出。3.1.2算法設計的要求通常設計一個“好”的算法，應考慮達到以下目標。1正確性正確性：算法應當滿足具體問題的需求。2可讀性可讀性：算法主要是為了人的閱讀與交流，其次才是機器執(zhí)行?？勺x性好有助于人對算法的理解。3健壯性健壯性：當輸入數(shù)據(jù)非法時，算法也能適當?shù)刈龀龇磻蜻M行處理，而不會產(chǎn)生莫明其妙的輸出結(jié)果。4效率與低存儲量需求。效率與低存儲量需求。效率指的是算法執(zhí)行時間。對于同一個問題

4、如果有多個算法可以解決，執(zhí)行時間短的算法效率高。低存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。信息技術與信息學競賽2【答案】D（3）算法指的是（）。A計算機程序B解決問題的計算方法C排序算法D解決問題的有限運算序列【解析】所謂算法是指解題方案的準確而完整的描述。對于一個問題，如果可以通過一個計算機程序在有限的存儲空間內(nèi)運行有限長的時間而得到正確的結(jié)果，則稱這個問題是算法可解的。但算法不等于程序，也不等于計算方法?！敬鸢浮緿（4）算法

5、能正確地實現(xiàn)預定功能的特性稱為算法的（）。A正確性B易讀性C健壯性D高效率【解析】針對實際問題設計的算法，人們總是希望能夠得到滿意的結(jié)果。但一個算法又總是在某個特定的計算工具上執(zhí)行的，因此算法在執(zhí)行過程中往往要受到計算工具的限制，使執(zhí)行結(jié)果產(chǎn)生偏差。算法與計算公式是有差別的，在設計一個算法時，必須要考慮它的可行性，否則將得不到滿意的結(jié)果。【答案】A（5）遞歸算法一般需要利用（）來實現(xiàn)。A棧B隊列C循環(huán)鏈表D雙向鏈表【答案】A3.2窮舉搜

6、索法有一些問題一時難以找到規(guī)律或者公式，或者根本沒有規(guī)律、公式。這時可以利用計算機高速運算的特點，使用窮舉來解決。窮舉搜索法是窮舉所有可能情形，并從中找出符合要求的解決。窮舉搜索法所有可能情形，最直觀的是聯(lián)系循環(huán)的算法。例1找出n個自然數(shù)（123…n）中r個數(shù)的組合。例如，當n=5，r=3時，所有組合為：553542541532531521432431421321total=10組合的總數(shù)［程序］programzuhe11constn=