版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、細(xì)心整理全國青少年信息學(xué)奧林匹克聯(lián)賽 全國青少年信息學(xué)奧林匹克聯(lián)賽算法講義 算法講義算法 算法根底篇 根底篇 ...................................................................................................................................1算法具有五個特征: .......................
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)用〔動態(tài)規(guī)劃法〕 ........................
12、.................................................32動態(tài)規(guī)劃算法應(yīng)用 .............................................................................................................33細(xì)心整理開展很快,程序所能支配的自由空間一般比擬充分,所以空間困難度就不如時間 困難度那么重要了,
13、有許多問題人們主要是探究其算法的時間困難度,而很少探 討它的空間消耗。時間困難性和空間困難性在必需條件下是可以相互轉(zhuǎn)化的。在中學(xué)生信息學(xué) 奧賽中,對程序的運(yùn)行時間作出了嚴(yán)格的限制,假如運(yùn)行時間超出了限定就會判錯,因此在設(shè)計算法時首先要考慮的是時間因素,必要時可以以犧牲空間來換取 時間,動態(tài)規(guī)劃法就是一種以犧牲空間換取時間的有效算法。對于空間因素,視題目的要求而定,一般可以不作太多的考慮。我們通過一個簡潔的數(shù)值計算問題,來比擬兩個不同算法
14、的效率〔在這里只比擬時間困難度〕 。例:求 N!所產(chǎn)生的數(shù)后面有多少個 0〔中間的 0 不計〕 。算法一:從 1 乘到 n,每乘一個數(shù)判定一次,假設(shè)后面有 0 那么去掉后面的 0, 并登記 0 的個數(shù)。為了不超出數(shù)的表示范圍,去掉與生成 0 無關(guān)的數(shù),只保存有 效位數(shù),當(dāng)乘完 n 次后就得到 0 的個數(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);{計數(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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 信息學(xué)奧賽——算法入門教程
- 信息學(xué)奧賽-算法教程-pascal
- 小學(xué)信息學(xué)奧賽教程
- 信息學(xué)奧賽教程c++版
- 信息學(xué)奧賽第一講-pascal入門
- 信息學(xué)奧賽培訓(xùn)教程c++版
- 信息學(xué)奧賽培訓(xùn)教程c++版
- 全國信息學(xué)奧賽noi培訓(xùn)教程(最新整理)
- 信息學(xué)奧賽noip初賽復(fù)習(xí)
- 信息學(xué)奧賽培訓(xùn)學(xué)習(xí)感受
- 信息學(xué)奧賽問題求解帶答案
- 信息學(xué)奧賽基礎(chǔ)知識習(xí)題
- bootstrap入門教程
- matlab入門教程
- amfphp入門教程
- labview入門教程
- 口琴入門教程
- ae入門教程
- caxa入門教程
- 攝影入門教程
評論
0/150
提交評論