信息學(xué)奧賽-算法教程-pascal

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

2、是否想到，是否有過關(guān)注，引發(fā)學(xué)生對系統(tǒng)方法和思想的思考，重視建立編程思想，強化編程習(xí)慣的培養(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算法設(shè)計的要求通常設(shè)計一個“好”的算法，應(yīng)考慮達到以下目標(biāo)。1正確性正確性：算法應(yīng)當(dāng)滿足具體問題的需求。2可讀性可讀性：算法主要是為了人的閱讀與交流，其次才是機器執(zhí)行?？勺x性好有助于人對算法的理解。3健壯性健壯性：當(dāng)輸入數(shù)據(jù)非法時，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進行處理，而不會產(chǎn)生莫明其妙的輸出結(jié)果。4效率與低存儲量需求。效率與低存儲量需求。效率指的是算法執(zhí)行時間。對于同一個問題

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

5、能正確地實現(xiàn)預(yù)定功能的特性稱為算法的（）。A正確性B易讀性C健壯性D高效率【解析】針對實際問題設(shè)計的算法，人們總是希望能夠得到滿意的結(jié)果。但一個算法又總是在某個特定的計算工具上執(zhí)行的，因此算法在執(zhí)行過程中往往要受到計算工具的限制，使執(zhí)行結(jié)果產(chǎn)生偏差。算法與計算公式是有差別的，在設(shè)計一個算法時，必須要考慮它的可行性，否則將得不到滿意的結(jié)果?！敬鸢浮緼（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ù)的組合。例如，當(dāng)n=5，r=3時，所有組合為：553542541532531521432431421321total=10組合的總數(shù)［程序］programzuhe11constn=