noip復(fù)習(xí)(提高組c++版)_第1頁
noip復(fù)習(xí)(提高組c++版)_第2頁
noip復(fù)習(xí)(提高組c++版)_第3頁
noip復(fù)習(xí)(提高組c++版)_第4頁
noip復(fù)習(xí)(提高組c++版)_第5頁
已閱讀5頁,還剩216頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、 前 言 主 編葫蘆島市一高中 李思洋完成日期2012年8月27日NOIP復(fù)習(xí)資料(C+版)前 言有一天,我整理了NOIP的筆記,并收集了一些經(jīng)典算法。不過我感覺到筆記比較凌亂,并且有很多需要修改和補(bǔ)充的內(nèi)容,于是我又搜集一些資料,包括一些經(jīng)典習(xí)題,在幾個(gè)月的時(shí)間內(nèi)編寫出了NOIP復(fù)習(xí)資料。由于急于在假期之前打印出來并分發(fā)給同校同學(xué)(我們學(xué)校既沒有競(jìng)賽班,又沒有懂競(jìng)賽的老師。我們大家都是自學(xué)黨),NOIP復(fù)習(xí)資料有很多的錯(cuò)誤,還有一些想收錄而未收錄的內(nèi)容。在“減負(fù)”的背景下,暑期放了四十多天的假。于是我又有機(jī)會(huì)認(rèn)真地修訂NOIP復(fù)習(xí)資料。我編寫資料的目的有兩個(gè):總結(jié)我學(xué)過(包括沒學(xué)會(huì))的算法、

2、數(shù)據(jù)結(jié)構(gòu)等知識(shí);與同學(xué)共享NOIP知識(shí),同時(shí)使我和大家的RP+。大家要清醒地認(rèn)識(shí)到,NOIP復(fù)習(xí)資料頁數(shù)多,是因?yàn)槌绦虼a占了很大篇幅。這里的內(nèi)容只是信息學(xué)的皮毛。對(duì)于我們來說,未來學(xué)習(xí)的路還很漫長(zhǎng)?;炯僭O(shè)作為自學(xué)黨,大家應(yīng)該具有以下知識(shí)和能力: 能夠熟練地運(yùn)用C+語言編寫程序(或熟練地把C+語言“翻譯”成Pascal語言); 能夠閱讀代碼,理解代碼含義,并嘗試運(yùn)用; 對(duì)各種算法和數(shù)據(jù)結(jié)構(gòu)有一定了解,熟悉相關(guān)的概念; 學(xué)習(xí)了高中數(shù)學(xué)的算法、數(shù)列、計(jì)數(shù)原理,對(duì)初等數(shù)論有一些了解; 有較強(qiáng)的自學(xué)能力。代碼約定N、M、MAX、INF是事先定義好的常數(shù)(不會(huì)在代碼中再次定義,除非代碼是完整的程序)。

3、N、M、MAX針對(duì)數(shù)據(jù)規(guī)模而言,比實(shí)際最大數(shù)據(jù)規(guī)模大;INF針對(duì)取值而言,是一個(gè)非常大,但又與int的最大值有一定差距的數(shù),如100000000。對(duì)于不同程序,數(shù)組下標(biāo)的下限也是不同的,有的程序是0,有的程序是1。閱讀程序時(shí)要注意。閱讀順序和方法沒聽說過NOIP,或?qū)OIP不甚了解的同學(xué),應(yīng)該先閱讀附錄E,以加強(qiáng)對(duì)競(jìng)賽的了解。如果不能順利通過初賽,你就應(yīng)該先補(bǔ)習(xí)初賽知識(shí)。這本NOIP復(fù)習(xí)資料總結(jié)的是復(fù)賽知識(shí)。如果沒有學(xué)過C+語言,應(yīng)該先選擇一本C+語言教材。一般情況下,看到“面向?qū)ο缶幊獭币徽碌那耙豁摼妥銐蛄耍∟OIP不用“面向?qū)ο缶幊獭保挥脭[弄窗口對(duì)話框)。附錄G介紹了一些書籍和網(wǎng)站。

4、你應(yīng)該選擇一本書,認(rèn)真地學(xué)習(xí)。再選擇一個(gè)網(wǎng)站,作為練習(xí)的題庫。第一單元對(duì)競(jìng)賽中常用的操作和簡(jiǎn)單的算法分析進(jìn)行了總結(jié),算作對(duì)C+語言的鞏固。同時(shí),閱讀這一單元之后,你應(yīng)該選擇一個(gè)合適的C+代碼編輯器。第二到第六單元介紹了競(jìng)賽常用的算法。閱讀每一章時(shí),應(yīng)該先閱讀“小結(jié)”名曰“小結(jié)”,實(shí)際上是“導(dǎo)讀”。這五個(gè)單元除了經(jīng)典習(xí)題,還有某些思想和算法的具體實(shí)現(xiàn)方法。這些信息可能在明處,也可能在暗處,閱讀時(shí)要注意挖掘和體會(huì)。如果有時(shí)間,應(yīng)該在不看解析和代碼的前提下獨(dú)立完成這些題。第七單元是第六單元的一個(gè)部分,由于它的內(nèi)容來自背包九講,所以單獨(dú)放在一個(gè)單元。從第八單元開始,到第十三單元,基本上就沒有習(xí)題了。換

5、句話說,該“背課文”了。第八單元介紹了常用的排序算法。你可以有選擇地學(xué)習(xí),但一定要掌握“STL算法”和“快速排序”。第九單元介紹了基本數(shù)據(jù)結(jié)構(gòu),你一定要掌握第九單元前五小節(jié)的內(nèi)容(本單元也有應(yīng)該優(yōu)先閱讀的“小結(jié)”)。有余力的話,第六小節(jié)的并查集也應(yīng)該掌握。第十單元介紹了與查找、檢索有關(guān)的數(shù)據(jù)結(jié)構(gòu)和算法。你也可以有選擇地學(xué)習(xí)。第十一單元與數(shù)學(xué)有關(guān)。數(shù)學(xué)對(duì)于信息學(xué)來說具有舉足輕重的地位。標(biāo)有“!”的應(yīng)該背下來,至于其他內(nèi)容,如果出題,你應(yīng)該能把它解決。第十二單元仍與數(shù)學(xué)有關(guān)。第十三單元是圖論。學(xué)習(xí)時(shí)要先閱讀“小結(jié)”,把概念弄清楚。之后要掌握?qǐng)D的實(shí)現(xiàn)方法。接下來要掌握一些經(jīng)典圖論算法:Kruskal

6、算法、Dijkstra算法、SPFA、Floyd算法、拓?fù)渑判?。附錄F總結(jié)了2004年以來NOIP考察的知識(shí)點(diǎn),可以作為選擇性學(xué)習(xí)的參考。在學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)的同時(shí),應(yīng)該閱讀和學(xué)習(xí)附錄A。如果你還有余力,你應(yīng)該學(xué)習(xí)第十四單元。第十四單元的內(nèi)容不是必須要掌握的,但是一旦學(xué)會(huì),可以發(fā)揮C+語言的優(yōu)勢(shì),降低編程復(fù)雜度。臨近競(jìng)賽時(shí),應(yīng)該閱讀附錄B和附錄C,以增加經(jīng)驗(yàn),減少失誤。面臨的問題1. 這是復(fù)賽復(fù)習(xí)資料需要有人能用心總結(jié)、整理初賽的知識(shí),就像這份資料一樣。2. 潛在的問題還是相當(dāng)多的,只是時(shí)間不夠長(zhǎng),問題尚未暴露。3. 部分代碼缺少解說,或解說混亂。4. 個(gè)人語文水平較差,資料也是如此。5. 沒

7、有對(duì)應(yīng)的Pascal語言版本。如果有人能為P黨寫一個(gè)Pascal版的STL,他的RP一定會(huì)爆增!6. 希望有人能用整理資料,并以自由文檔形式發(fā)布。最后,歡迎大家以交流、分享和提高為目的修改、復(fù)制、分發(fā)本資料,同時(shí)歡迎大家將資料翻譯成Pascal語言版供更多OIer閱讀!謝謝大家的支持!葫蘆島市一高中 李思洋2012年8月27日 1 目 錄 目 錄標(biāo)題上的符號(hào):1. !:表示讀者應(yīng)該熟練掌握這些內(nèi)容,并且在競(jìng)賽時(shí)能很快地寫出來。換句話說就是應(yīng)該背下來。2. *:表示內(nèi)容在NOIP中很少涉及,或者不完全適合NOIP的難度。3. #:表示代碼存在未更正的錯(cuò)誤,或算法本身存在缺陷。I 前 言1目 錄I

8、第一單元C+語言基礎(chǔ)11.1程序結(jié)構(gòu)11.2數(shù)據(jù)類型41.3運(yùn)算符61.4函數(shù)81.5輸入和輸出!91.6其他常用操作!101.7字符串操作!131.8文件操作!131.9簡(jiǎn)單的算法分析和優(yōu)化141.10代碼編輯器16第二單元基礎(chǔ)算法172.1經(jīng)典枚舉問題172.2火柴棒等式182.3梵塔問題192.4斐波那契數(shù)列192.5常見的遞推關(guān)系!202.6選擇客棧222.72k進(jìn)制數(shù)232.8Healthy Holsteins242.9小結(jié)25第三單元搜索273.1N皇后問題273.2走迷宮293.38數(shù)碼問題313.4埃及分?jǐn)?shù)343.5Mayan游戲363.6預(yù)處理和優(yōu)化403.7代碼模板413.

9、8搜索題的一些調(diào)試技巧433.9小結(jié)44第四單元貪心算法464.1裝載問題464.2區(qū)間問題464.3刪數(shù)問題474.4工序問題474.5種樹問題474.6馬的哈密爾頓鏈474.7三值的排序494.8田忌賽馬504.9小結(jié)50第五單元分治算法515.1一元三次方程求解515.2快速冪515.3排序515.4最長(zhǎng)非降子序列535.5循環(huán)賽日程表問題535.6棋盤覆蓋545.7刪除多余括號(hào)555.8聰明的質(zhì)監(jiān)員565.9模板585.10小結(jié)59第六單元?jiǎng)討B(tài)規(guī)劃606.1導(dǎo)例:數(shù)字三角形606.2區(qū)間問題:石子合并636.3坐標(biāo)問題656.4背包問題676.5編號(hào)問題676.6遞歸結(jié)構(gòu)問題686.7

10、DAG上的最短路徑716.8樹形動(dòng)態(tài)規(guī)劃*726.9狀態(tài)壓縮類問題:過河746.10Bitonic旅行766.11小結(jié)77第七單元背包專題787.1部分背包問題787.20/1背包問題!787.3完全背包問題797.4多重背包問題797.5二維費(fèi)用的背包問題807.6分組的背包問題817.7有依賴的背包問題817.8泛化物品817.9混合背包問題827.10特殊要求827.11背包問題的搜索解法837.12子集和問題84第八單元排序算法858.1常用排序算法858.2簡(jiǎn)單排序算法878.3線性時(shí)間排序888.4使用二叉樹的排序算法*898.5小結(jié)90第九單元基本數(shù)據(jù)結(jié)構(gòu)919.1線性表(順序結(jié)

11、構(gòu))919.2線性表(鏈?zhǔn)浇Y(jié)構(gòu))919.3棧939.4隊(duì)列949.5二叉樹959.6并查集!999.7小結(jié)102第十單元查找與檢索10410.1順序查找10410.2二分查找!10410.3查找第k小元素!10510.4二叉排序樹10610.5堆和優(yōu)先隊(duì)列*10810.6哈夫曼(Huffman)樹11010.7哈希(Hash)表111第十一單元數(shù)學(xué)基礎(chǔ)11611.1組合數(shù)學(xué)11611.2組合數(shù)的計(jì)算!11711.3排列和組合的產(chǎn)生(無重集元素)!11711.4排列和組合的產(chǎn)生(有重集元素)12011.5秦九韶算法12211.6進(jìn)制轉(zhuǎn)換(正整數(shù))12311.7高精度算法(壓位存儲(chǔ))!12311.

12、8快速冪!12811.9表達(dá)式求值12911.10解線性方程組*133第十二單元數(shù)論算法13512.1同余的性質(zhì)!13512.2最大公約數(shù)、最小公倍數(shù)!13512.3解不定方程axbyc!*13512.4同余問題*13612.5素?cái)?shù)和素?cái)?shù)表13612.6分解質(zhì)因數(shù)137第十三單元圖與圖論算法13913.1圖的實(shí)現(xiàn)13913.2圖的遍歷14113.3連通性問題14213.4歐拉回路 鄰接矩陣14613.5最小生成樹(MST)14713.6單源最短路問題(SSSP問題)14813.7每?jī)牲c(diǎn)間最短路問題(APSP問題)!15213.8拓?fù)渑判?5213.9關(guān)鍵路徑15513.10二分圖初步15713

13、.11小結(jié)160第十四單元 STL簡(jiǎn)介16414.1STL概述16414.2常用容器16414.3容器適配器17014.4常用算法17114.5迭代器17514.6示例:合并果子175附錄A思想和技巧177A.1時(shí)間/空間權(quán)衡177A.2試驗(yàn)、猜想及歸納177A.3模型化177A.4隨機(jī)化*178A.5動(dòng)態(tài)化靜態(tài)178A.6前序和!179A.7狀態(tài)壓縮*180A.8抽樣測(cè)試法*182A.9離散化*183A.10Flood Fill*184附錄B調(diào)試185B.1常見錯(cuò)誤類型185B.2調(diào)試過程185B.3調(diào)試功能185B.4符號(hào)DEBUG的應(yīng)用186B.5代碼審查表186B.6故障檢查表187B

14、.7命令行和批處理*188附錄C競(jìng)賽經(jīng)驗(yàn)和教訓(xùn)192C.1賽前兩星期192C.2賽前30分鐘192C.3解題表193C.4測(cè)試數(shù)據(jù)195C.5交卷前5分鐘196C.6避免偶然錯(cuò)誤196C.7騙分197附錄D學(xué)習(xí)建議198D.1學(xué)習(xí)方法198D.2學(xué)習(xí)能力198D.3關(guān)于清北學(xué)堂198附錄E競(jìng)賽簡(jiǎn)介199E.1從NOIP到IOI199E.2NOIP簡(jiǎn)介199E.3常用語201E.4第一次參加復(fù)賽202附錄FNOIP復(fù)賽知識(shí)點(diǎn)分布204附錄G資料推薦205G.1書籍205G.2網(wǎng)站205參考文獻(xiàn)206計(jì)算機(jī)專業(yè)是朝陽還是夕陽?207杜子德在CCF NOI2012開幕式上的講話209多數(shù)奧賽金牌得主

15、為何難成大器210第單元C+語言基礎(chǔ)第單元C+語言基礎(chǔ)1.1程序結(jié)構(gòu)(1) 程序框架 注釋:注釋有兩種,一種是“/”,另一種是“/* */”。“/”必須單獨(dú)放置一行,或代碼所在行的后面;而“/*”、“*/”成對(duì)存在,可以插入到代碼的任意位置。 引用頭文件:在代碼開頭寫“#include <頭文件名>”。如果想引用自己的頭文件,需要把尖括號(hào)(表示只從系統(tǒng)目錄搜索頭文件)換成雙引號(hào)(表示先從cpp所在文件夾搜索,然后再到系統(tǒng)文件夾搜索)。 命名空間:很多C+的東西都要引用std命名空間,所以代碼中會(huì)有“using namespace std;”。 main():所有程序都要從main(

16、)開始。在所有的算法競(jìng)賽中,main()的返回值必須是0,否則視為程序異常結(jié)束,得分為0分。 語句和語句塊:1. 語句:一般情況下,一條語句要用一個(gè)分號(hào)“;”結(jié)束。為了美觀和可讀性,可以把一條語句擴(kuò)展成幾行,也可以把多個(gè)語句寫到同一行上。2. 語句塊:用“”和“”包圍的代碼是語句塊。無論里面有多少代碼,在原則上,語句塊所在的整體都視為一條語句。(2) 選擇結(jié)構(gòu)1. if語句:if表示判斷。如果條件為真,就執(zhí)行接在if后的語句(語句塊),否則執(zhí)行else后的語句(語句塊)。如果沒有else,就直接跳過。if有以下幾種格式:if (條件)/ 如果條件成立,就執(zhí)行if后面的語句或語句塊。語句或語句塊

17、if (條件)/ 如果條件成立,就執(zhí)行if后面的A,否則執(zhí)行B。語句或語句塊Aelse語句或語句塊Bif (條件1)/ 實(shí)際上,這是if語句內(nèi)的if語句,即if的嵌套。所以else和if中間要有空格。語句或語句塊Aelse if (條件2)語句或語句塊Belse語句或語句塊N2. switch語句:switch表示選擇。它根據(jù)條件的不同取值來執(zhí)行不同的語句。格式如下:switch (表達(dá)式)case 值1:代碼段Abreak;case 值2:代碼段Bbreak;default:代碼段Nbreak;如果表達(dá)式的值是值1,就執(zhí)行代碼段A;如果表達(dá)式的值是值2,就執(zhí)行代碼段B否則執(zhí)行代碼段N。注意:

18、 default一部分可以省略。 如果不使用break,那么緊隨其后的case部分代碼也會(huì)被執(zhí)行,直到遇到break或switch語句結(jié)束為止! switch結(jié)尾要有一個(gè)分號(hào)。3. if、switch都可以嵌套使用?!締栴}描述】輸入一個(gè)日期,判斷它所在年份是否為閏年,并輸出所在月份的天數(shù)。閏年的判斷方法:四年一閏,百年不閏,四百年又閏。int year,month,day;bool b=false;cin>>year>>month>>day;/ 判斷是否為閏年if (n%400=0)b=true;else if (n%100!=0 && n%

19、4=0)b=true;if (b)cout<<y<<"是閏年。"<<endl;elsecout<<y<<"不是閏年。"<<endl;/ 判斷所在月份的天數(shù)switch (month)case 1: case 3: case 5: case 7: case 8: case 10: case 12:cout<<"這個(gè)月有31天。"<<endl;break;case 4: case 6: case 9: case 11:cout<<&

20、quot;這個(gè)月有30天。"<<endl;break;case 2:cout<<"這個(gè)月有"<<(b ? 29 : 28)<<"天。"<<endl;break;(3) 循環(huán)結(jié)構(gòu)1. while語句:如果條件成立,就繼續(xù)循環(huán),直到條件不成立為止。格式如下:while (條件)循環(huán)體(語句或語句塊)2. dowhile語句:如果條件成立,就繼續(xù)循環(huán),直到條件不成立為止。它與while的最大區(qū)別在于,dowhile循環(huán)中的語句會(huì)被執(zhí)行至少一次,而while中的語句可能一次都沒有被執(zhí)行。格式如

21、下:do循環(huán)體while (條件);/ 注意分號(hào)4. for語句:for分四部分,有初始條件、繼續(xù)循環(huán)的條件、狀態(tài)轉(zhuǎn)移的條件和循環(huán)體。格式如下:for (初始條件; 繼續(xù)循環(huán)的條件; 狀態(tài)轉(zhuǎn)移的條件)循環(huán)體轉(zhuǎn)換成while循環(huán),即:初始條件while (繼續(xù)循環(huán)的條件)循環(huán)體狀態(tài)轉(zhuǎn)移for后三個(gè)條件不是必需的,可以省略不寫,但分號(hào)必須保留。5. 在循環(huán)語句內(nèi)部使用break,可以跳出循環(huán);使用continue,可以忽略它后面的代碼,馬上進(jìn)入下一輪循環(huán)。注意,這兩個(gè)語句只對(duì)它所在的一層循環(huán)有效。6. 寫for循環(huán)時(shí),一定要注意: 不要把計(jì)數(shù)器的字母打錯(cuò),尤其是在復(fù)制/粘貼一段代碼的時(shí)候。 根據(jù)算

22、法要明確不等號(hào)是“<”、“>”,還是“<=”、“>=”。 逆序循環(huán)時(shí),不要把自減“-”寫成自增“+”!【問題描述】輸入n,輸出n!(n!1×2×3×4××n)。結(jié)果保證小于long long的范圍。當(dāng)輸入值為負(fù)數(shù)時(shí)結(jié)束程序。int n;long long r=1;cin>>n;while (n>-1)r=1;for (int i=1; i<=n; i+)r*=i;cout<<n<<"! = "<<r<<endl;cin>&g

23、t;n;(4) goto語句goto語句用于無條件跳轉(zhuǎn)。要想跳轉(zhuǎn),首先要定義標(biāo)簽(在代碼開頭的一段標(biāo)識(shí)符,后面緊跟冒號(hào)),然后才能goto那個(gè)標(biāo)簽。很多教程不提倡使用無條件跳轉(zhuǎn),因?yàn)樗茐牧顺绦蚪Y(jié)構(gòu),還容易給代碼閱讀者帶來麻煩。不過,這不代表goto沒有使用價(jià)值。goto的一個(gè)用途是跳出多層循環(huán):for (int i=0; i<9; i+)for (int j=0; j<9; j+)for (int k=0; k<9; k+)if (滿足某種條件) goto _exited;_exited:(5) C與C+的區(qū)別C+語言是以C語言為基礎(chǔ)開發(fā)出來的,C語言的大多數(shù)內(nèi)容被保留了下

24、來。在信息學(xué)競(jìng)賽領(lǐng)域,很多情況下C和C+可以互相轉(zhuǎn)化,甚至不用對(duì)代碼進(jìn)行任何修改。下面是信息學(xué)競(jìng)賽領(lǐng)域中C和C+的重要區(qū)別: C+支持用流輸入輸出,而C只能用scanf和printf再見了,%d! C+非常支持面向?qū)ο缶幊?,而C已經(jīng)“out”了。資料中的“高精度算法”就只能用C+完成,因?yàn)樵趕truct內(nèi)定義了成員函數(shù)。C+可以用更強(qiáng)大的string類處理字符串,而不必?fù)?dān)心發(fā)生某些低級(jí)錯(cuò)誤。 C+有強(qiáng)大的STL,而C沒有(有一個(gè)小小的qsort和bsearch算是補(bǔ)償了)。STL是很多人從C轉(zhuǎn)到C+的重要原因。 C的頭文件名仍然可以用在C+中,不過可能會(huì)收到警報(bào)應(yīng)該去掉“.h”,前面再加一個(gè)“

25、c”。如<stdio.h>應(yīng)該改成<cstdio>。 C程序運(yùn)行速度稍優(yōu)于C+。不過也沒快多少??傊?,C能做的一切事情,C+也能做;C+能做的一切事情,C不一定能做。1.2數(shù)據(jù)類型(1) 基本數(shù)據(jù)類型名稱占用空間別名數(shù)據(jù)范圍int4signed, signed int,long, long int2,147,483,6482,147,483,647unsigned int 一般都使用有符號(hào)整數(shù),除非范圍不夠大,或者你確定你的減法運(yùn)算不會(huì)出現(xiàn)“小數(shù)減大數(shù)”。4unsigned, unsignedlong,unsigned long int04,294,967,295cha

26、r1char128127unsigned char1unsigned char0255short 一般來說,使用int、long long更保險(xiǎn)一些,除非內(nèi)存不夠用。2short int,signed short int32,76832,767unsigned short2unsigned short int065,535long long 不要使用“_int64”!它是Visual C+特有的關(guān)鍵字。8signed long long9,223,372,036,854,775,8089,223,372,036,854,775,807 假如a是long long類型,把超過231的值賦給它時(shí)要

27、使用字面值LL(ULL):a=123456789012345LL。unsigned long long8018,446,744,073,709,551,615bool1true或falsechar1128127signed char1128127unsigned char10255float43.4E +/- 38 (7位有效數(shù)字)double8long double1.7E +/- 308 (15位有效數(shù)字)(2) 變量與常量1. 定義變量:“變量類型 標(biāo)識(shí)符”,如“int i;”定義了一個(gè)名字為i的整型變量。注意,此時(shí)i并未初始化,所以i的值是不確定的。2. 定義常量:“const 變量類

28、型 標(biāo)識(shí)符=初始值”,如:const int N=90;3. 合法的標(biāo)識(shí)符: 標(biāo)識(shí)符不能和關(guān)鍵字(在IDE中會(huì)變色的詞語)相同。 標(biāo)識(shí)符只能包括字母、數(shù)字和下劃線“_”,并且開頭只能是字母或下劃線。 標(biāo)識(shí)符必須先定義后使用。 在同一作用域內(nèi),標(biāo)識(shí)符不能重復(fù)定義(即使在不同作用域內(nèi)也不應(yīng)重復(fù),否則容易產(chǎn)生歧義)。 C+區(qū)分大小寫。所以A和a是兩個(gè)不同的標(biāo)識(shí)符。(3) 數(shù)組1. 定義一個(gè)一維數(shù)組:int a10;這個(gè)數(shù)組一共10個(gè)元素,下標(biāo)分別為09。訪問某個(gè)元素時(shí),直接用a加方括號(hào),如a5。2. 定義一個(gè)二維數(shù)組:int b53;這個(gè)數(shù)組一共5×315個(gè)元素,分別是b00、b01、b0

29、2、b10b42。訪問某個(gè)元素時(shí)要用兩個(gè)方括號(hào),如b21。多維數(shù)組的定義和使用方法與此類似。3. 數(shù)組名和元素的尋址:以上面的a、b為例 數(shù)組名是一個(gè)指針,指向整個(gè)數(shù)組第一個(gè)元素所在的地址。如a就是&a0、b就是&b00。 多維數(shù)組的本質(zhì)是數(shù)組的數(shù)組,所以b0實(shí)際上是b00、b01的數(shù)組名,b0就是&b00。 在內(nèi)存中,數(shù)組中每個(gè)元素都是緊挨著的,所以可以直接進(jìn)行指針的運(yùn)算。如a+3就是&a3,*(b+1)就是b10,*(*(b+3)+2)就是b32。 在競(jìng)賽中要盡可能回避這些功能。4. 字符串: 字符串實(shí)際上是char的數(shù)組。 字符串最后一位必須是'0

30、',否則會(huì)在進(jìn)行輸出、使用字符串函數(shù)時(shí)發(fā)生意外。 數(shù)組,包括字符串,不可以整體地賦值和比較。如果需要,應(yīng)使用memcpy和memcmp(字符串是strcpy和strcmp)。5. C+中數(shù)組的下標(biāo)只能從0開始(當(dāng)然可以閑置不用),并且int a10中a的最后一個(gè)元素是a9,不是a10!6. C+不檢查數(shù)組下標(biāo)是否越界!如果下標(biāo)越界,程序很有可能會(huì)崩潰!(4) 指針1. 取地址運(yùn)算符和取值運(yùn)算符: 取地址運(yùn)算符“&”:返回變量所在的地址。一般用于變量。(而數(shù)組名本身就是指針,無需“&”) 取值運(yùn)算符“*”:返回地址對(duì)應(yīng)的值,或用于改變指針?biāo)竷?nèi)存空間的值。只能用于指針。2

31、. 指針的意義:保存另一個(gè)變量的內(nèi)存地址。3. 定義指針:int *p;定義多個(gè)指針時(shí),每個(gè)字母的前面都要有“*”。注意,如果p沒有被初始化,它就會(huì)指向一個(gè)未知的內(nèi)存空間,而錯(cuò)誤地操作內(nèi)存會(huì)導(dǎo)致程序崩潰!4. 指針使用實(shí)例:int a = 0, b = 1; int c = 1,2,3,4,5,6,7,8,9,10;int *p;/ 定義一個(gè)指針p=&a;/ 讓p指向a(*p)=3;/ 相當(dāng)于a=3(*p)=b;/ 相當(dāng)于a=b,此時(shí)a等于1/ p=b;/ 非法操作,左邊是int *,右邊是int,類型不匹配。p=&b;/ 讓p指向b,從此p和a沒關(guān)系了p=c+6;/ 讓p指向

32、c6,p和b又沒關(guān)系了cout<<*p;/ 輸出p指向的變量的值,即c6p+;/ 現(xiàn)在p指向了c7;p=NULL;/ 表示p沒有指向任何變量cout<<*p;/ 由于NULL(0)是一段無意義的地址,所以程序極有可能崩潰。為了不在競(jìng)賽中把自己搞暈,請(qǐng)回避指針,對(duì)其敬而遠(yuǎn)之。(5) 引用通俗地講,引用是某個(gè)變量的別名。下面定義了一個(gè)叫p的引用,它實(shí)際上是f02。無論是改變p的值,還是改變f02的值,結(jié)果都是一樣的。int &p = f02;使用引用的好處是,在函數(shù)的形參中定義引用類型,可以直接修改變量的值,而不用考慮“&”和“*”運(yùn)算符。像上面一行代碼一樣

33、,如果頻繁調(diào)用f02,也可以用引用節(jié)省篇幅,提高代碼可讀性。引用與指針不同。引用被創(chuàng)建的同時(shí)也必須被初始化,并且必須與合法的存儲(chǔ)單元關(guān)聯(lián)。一旦引用被初始化,就不能改變引用的關(guān)系。而指針可以不立刻初始化,也可以改變所指向的內(nèi)存空間。(6) 結(jié)構(gòu)體 結(jié)構(gòu)體用struct定義。例如下面代碼定義了一個(gè)叫pack的結(jié)構(gòu)體,它有兩個(gè)成員,一個(gè)叫value,另一個(gè)叫weight。struct packint value, weight; 變量可以定義成上面的pack類型:pack p;/ 不必寫成struct pack p; 訪問pack的成員時(shí),用“.”運(yùn)算符(指針變量用“->”):p.value、

34、(&p)->value C+中結(jié)構(gòu)體可以像類一樣建立自己的構(gòu)造函數(shù)、成員函數(shù),也可以重載運(yùn)算符。 對(duì)于pack這個(gè)結(jié)構(gòu)體,它的內(nèi)部不允許再有pack類型的成員,但是可以有pack類型的指針。1.3運(yùn)算符(1) 運(yùn)算符的優(yōu)先級(jí)運(yùn)算符結(jié)合方式:無.(對(duì)象成員) ->(指針) (數(shù)組下標(biāo)) ()(函數(shù)調(diào)用)從左向右+ - (typecast)(強(qiáng)制類型轉(zhuǎn)換) sizeof ! +(一元) -(一元)*(取值運(yùn)算符) &(取地址運(yùn)算符) new delete從右向左.* ->*從左向右* / %(取余數(shù))從左向右+ -從左向右<<(左移) >>

35、(右移)從左向右< <= > >=從左向右=(判斷相等) !=(判斷不等)從左向右&(按位與)從左向右(異或)從左向右|(按位或)從左向右&&(條件與)從左向右|(條件或)從左向右?:(條件運(yùn)算符)從右向左= *= /= %= += -= &= = >>= <<=從右向左,從左向右(2) 常用運(yùn)算符的作用1. 算術(shù)運(yùn)算符:+、-、*、/、%分別表示加、減、乘、除、取余。兩個(gè)整數(shù)做除法時(shí),如果除不開,程序?qū)研?shù)部分直接截?cái)啵ú皇撬纳嵛迦耄<矗赫麛?shù)/整數(shù)整數(shù),浮點(diǎn)數(shù)/浮點(diǎn)數(shù)浮點(diǎn)數(shù)。學(xué)習(xí)過其他語言的同學(xué)要注意,C+中

36、沒有乘方運(yùn)算符,“”也不是乘方運(yùn)算符。2. 比較運(yùn)算符: >、>=、<、<=、=(相等)、!=(不等)用來判斷不等關(guān)系,返回值是true或false。小心,千萬不要把“=”寫成“=”! 永遠(yuǎn)不要對(duì)浮點(diǎn)數(shù)使用=和!=運(yùn)算符!正確的做法是:const double eps = 0.000001;/ 自己控制精度if (d>=2-eps && d<=2+eps) / 相當(dāng)于if (d=2) 不應(yīng)該判斷一個(gè)變量的值是否等于true。安全的做法是判斷它是否不等于false。3. 位運(yùn)算: &、|、分別表示按位與、按位或、按位異或,即兩個(gè)操作數(shù)上

37、每一個(gè)二進(jìn)制位都要進(jìn)行運(yùn)算。 表示按位求反。 <<、>>表示二進(jìn)制位的移動(dòng)。當(dāng)某一位數(shù)字移動(dòng)到二進(jìn)制位的外面之后,它就直接“消失”了。a<<n相當(dāng)于a×2n,a>>n相當(dāng)于a÷2n。4. 邏輯運(yùn)算符: &&、|、分別表示與、或、異或。!表示非。 ?:是條件運(yùn)算,它是C+唯一一個(gè)三目運(yùn)算符。它的格式如下:A ? B : C。如果A不為false,那么返回B,否則返回C??梢詫⑦@個(gè)運(yùn)算符理解為一個(gè)簡(jiǎn)化版的if。 |、&&、?:是短路運(yùn)算符 例如計(jì)算“a && b”,如果a為false

38、,那么實(shí)際上結(jié)果就是false不管b是什么,程序都不再計(jì)算了。不要在這三種運(yùn)算符內(nèi)調(diào)用函數(shù)或賦值,以免發(fā)生難以查出的錯(cuò)誤!5. 比較運(yùn)算符、位移運(yùn)算符、邏輯運(yùn)算符、條件運(yùn)算符的優(yōu)先級(jí)較低,所以使用時(shí)要多加括號(hào),以防出錯(cuò)。6. 自增(+)、自減(-)運(yùn)算符: 增量分別是1和-1。 這兩種運(yùn)算符只能用于數(shù)值類型的變量,不能用于非數(shù)值類型變量、常量、表達(dá)式和函數(shù)調(diào)用上。 前綴+、-和后綴+、-的作用效果不同:int i=0, j=8, k=5;j = j + (+i);/ i先自增,變成1,然后再和j相加。執(zhí)行之后i=1,j=9。k = k + (i+);/ i先和k相加,使k=6。然后i再自增。執(zhí)

39、行之后i=2,k=6。 前綴運(yùn)算符返回引用類型,后綴運(yùn)算符返回?cái)?shù)值類型。 為了避免錯(cuò)誤,不要讓+、-和其他能夠改變變量的操作在同一行出現(xiàn)!7. 賦值運(yùn)算符: 在C+中賦值是一種運(yùn)算符。所以你會(huì)看到i=j=0、dx=y、return c=i+j之類的代碼。 +=、-=、*=、可以簡(jiǎn)化書寫。例如a*=2+3相當(dāng)于a=a*(2+3)。(3) 真值表pqp && q (p & q)p | q (p | q)p q!p (p)true (1)true (1)true (1)true (1)false (0)false (0)true (1)false (0)false (0)tr

40、ue (1)true (1)false (0)false (0)true (1)false (0)true (1)true (1)true (1)false (0)false (0)false (0)false (0)false (0)true (1)(4) 類型強(qiáng)制轉(zhuǎn)換用一對(duì)小括號(hào)把數(shù)據(jù)類型包上,則它右側(cè)的變量或常量的值(變量本身不變)就變成了對(duì)應(yīng)的類型。如:int i=2;float c=6.4/(float)i;/ 把i的值變成float類型。兩個(gè)操作數(shù)進(jìn)行四則運(yùn)算,如果想保留小數(shù)位,那么兩個(gè)操作數(shù)應(yīng)該都是浮點(diǎn)數(shù)。上面的代碼就是這樣。1.4函數(shù)(1) 定義和使用函數(shù)1. 定義和調(diào)用函數(shù):

41、下面定義了一個(gè)函數(shù),返回值是double類型的,其中有兩個(gè)參數(shù)i、j,分別是int和float類型的。double foo(int j, float j) 如果函數(shù)不需要返回任何值,可定義為void類型。 函數(shù)的定義必須在函數(shù)調(diào)用的前面。只有在前面添加了函數(shù)定義,才能把具體實(shí)現(xiàn)放到調(diào)用的后面:double foo(int, float);/ 放到調(diào)用之前2. 返回值:return 值; 函數(shù)是void類型的,那么return后面除了分號(hào),什么都不跟。 調(diào)用之后,函數(shù)立刻結(jié)束。 不可以直接對(duì)函數(shù)名賦值(學(xué)過Pascal或Basic語言的同學(xué)要特別注意)。3. 如果你的函數(shù)需要返回指針或引用,你必

42、須注意:不要引用函數(shù)內(nèi)部的變量!因?yàn)楹瘮?shù)一結(jié)束,函數(shù)內(nèi)部的變量就煙消云散,不復(fù)存在了。正確做法是引用靜態(tài)變量(static)或全局變量。4. 內(nèi)聯(lián)函數(shù)(inline):當(dāng)一個(gè)函數(shù)內(nèi)部只有寥寥幾句時(shí),如“華氏度變攝氏度”,可以考慮將其定義成內(nèi)聯(lián)函數(shù),通知編譯器省略函數(shù)入棧等操作,直接展開函數(shù)內(nèi)容,以加快運(yùn)行速度。inline int FtoC(int f) return (f-32)/9*5; (2) 傳遞實(shí)參1. 按值傳遞:例如int foo(int n),在調(diào)用foo時(shí),程序會(huì)把參數(shù)復(fù)制一份給n。這樣,對(duì)n的任何修改都不會(huì)反映到調(diào)用foo的參數(shù)上面。對(duì)于按值傳遞數(shù)組,一定要慎重。因?yàn)閺?fù)制數(shù)組

43、的元素要浪費(fèi)很多時(shí)間。2. 傳遞指針:例如int foo(int *n)。對(duì)n的修改會(huì)反映到調(diào)用foo的參數(shù)上面。 修改n的值時(shí)要注意,必須用取值運(yùn)算符,否則改變的是n指向的內(nèi)存空間 使用const可防止n指向的內(nèi)存空間發(fā)生改變:int foo(const int *n)。這時(shí)再寫n=5之類的語句會(huì)被報(bào)錯(cuò)。 此外,這種方法可以用于傳遞數(shù)組調(diào)用時(shí)只需把數(shù)組名作為參數(shù)。這時(shí)不需要取值運(yùn)算符。3. 傳遞引用:例如int foo(int &n)。優(yōu)點(diǎn)是既可以直接修改調(diào)用foo的參數(shù),又不會(huì)帶來指針的麻煩(無需取值運(yùn)算符)。缺點(diǎn)是不能傳入常數(shù)或表達(dá)式。1.5輸入和輸出!(1) 使用標(biāo)準(zhǔn)輸入/輸出

44、頭文件:<cstdio>變量約定:FILE *fin, *fout;fin、fout分別代表輸入文件和輸出文件。把它們換成stdin和stdout,就是從屏幕輸入和從屏幕輸出。“1.5 字符串操作”也使用了同樣的變量。1. 輸出字符串或變量的值:printf("格式字符串", );或fprintf(fout, "格式字符串", );格式字符:“%”后連接一個(gè)字母。字符含義字符含義d整數(shù) 在Windows下調(diào)試時(shí),用“%I64d”輸出long long類型的值。交卷時(shí),由于用Linux測(cè)試,要改成“%lld”。e, E用科學(xué)記數(shù)法表示的浮點(diǎn)數(shù)u

45、無符號(hào)整數(shù)f浮點(diǎn)數(shù)o八進(jìn)制整數(shù)c字符x, X十六進(jìn)制整數(shù)(小寫、大寫)s字符串(字符數(shù)組)常見的修飾符: %5d:5位數(shù),右對(duì)齊。不足5位用空格補(bǔ)齊,超過5位按實(shí)際位數(shù)輸出。 %-5d:5位數(shù),左對(duì)齊。不足5位用空格補(bǔ)齊,超過5位按實(shí)際位數(shù)輸出。 %05d:5位數(shù),右對(duì)齊。不足5位用'0'補(bǔ)齊,超過5位按實(shí)際位數(shù)輸出。 %+d:無論是正數(shù)還是負(fù)數(shù),都要把符號(hào)輸出。 %.2f:保留2位小數(shù)。如果小數(shù)部分超過2位就四舍五入,否則用0補(bǔ)全。1. 輸入到變量 讀取不含空白的內(nèi)容:scanf("格式字符串", &);或fscanf(fin, "格式字

46、符串", &); 格式字符和printf基本一致。 不要忘記“&”!printf傳的是值,scanf傳的是地址! scanf和fscanf的返回值是:成功輸入的變量個(gè)數(shù)。fscanf返回EOF,表示文件結(jié)束。 scanf和fscanf忽略TAB、空格、回車。遇到這些字符它們就停止讀取。 讀取單個(gè)字符:fgetc(fin); 首先要判斷它是否為EOF(文件結(jié)束)。如果不是,就可以用強(qiáng)制類型轉(zhuǎn)換變成char。讀取到行末時(shí),要注意對(duì)換行符的處理。 Windows、Linux、Mac的回車字符是不同的。Linux是'n',Mac是'r',Win

47、dows下是兩個(gè)字符'r'和'n'。(2) 使用流輸入/輸出頭文件:<iostream>1. 輸入到變量:cin>>n;2. 輸出到屏幕上:cout<<a;可以連續(xù)輸入、輸出,如cin>>n>>m; cout<<a<<','<<b<<endl;3. 換行:cout<<endl;4. 格式化輸出:頭文件:<iomanip> 右對(duì)齊,長(zhǎng)度為n,不足的部分用空格補(bǔ)齊:cout.width(n);cout.fill('

48、; ');/ 如果想用“0”補(bǔ)齊,就可以把空格換成“0”cout<<a;前兩行代碼,每次輸出之前都要調(diào)用。 輸出成其他進(jìn)位制數(shù):8: cout<<oct<<a;16: cout<<hex<<a;其他進(jìn)位制需要自己轉(zhuǎn)換。5. 注意,數(shù)據(jù)規(guī)模很大時(shí),流的輸入輸出速度會(huì)變得很慢,甚至數(shù)據(jù)還沒讀完就已經(jīng)超時(shí)了。在進(jìn)行輸入輸出之前加入這樣一條語句:ios:sync_with_stdio(false);調(diào)用之后,用cin、cout輸入輸出的速度就和scanf、printf的速度一樣了。1.6其他常用操作!本資料常用的頭文件:<ios

49、tream>、<cstdlib>、<cstring>、<fstream>以及<algorithm>、<stack>、<queue>、<vector>等。C+的流、容器、算法等都需要引用std命名空間。所以需要在#include后面、你的代碼前面加上一句:using namespace std;(1) 庫函數(shù)1. 數(shù)組的整體操作:頭文件:<cstring> 將a初始化:memset(a, 0, sizeof(a);第二個(gè)參數(shù)應(yīng)該傳入0、-1或0x7F。傳入0或-1時(shí),a中每個(gè)元素的值都是0或-1

50、;如果傳入0x7F時(shí),那么a中每個(gè)元素的值都是0x7F7F7F7F(不是0x7F?。烧J(rèn)為是“無窮大”。 將a整體復(fù)制到b中:memcpy(b, a, sizeof(a); 判斷a和b是否等價(jià):memcmp(a, b, sizeof(a);/ 返回0表示等價(jià)2. 字符操作:頭文件:<cctype> tolower(c)、toupper(c):將c轉(zhuǎn)化為小寫或大寫。 isdight(c)、isalpha(c)、isupper(c)、islower(c)、isgraph(c)、isalnum(c):分別判斷c是否為十進(jìn)制數(shù)字、英文字母、大寫英文字母、小寫英文字母、非空格、字母或數(shù)字。

51、3. 最大值/最小值:頭文件:<algorithm>max(a,b)返回a和b中的最小值,min(a,b)返回a和b中的最大值。其實(shí)我們可以自己寫:4. 交換變量的值:swap(a,b)頭文件:<algorithm>其實(shí)我們可以自己寫:inline void swap(int &a, int &b) int t=a; a=b; b=t; 5. 執(zhí)行DOS命令或其他程序:system("命令行"); 頭文件:<cstdlib> 暫停屏幕:system("pause"); 競(jìng)賽交卷或OJ提交代碼之前必須刪除

52、system,否則會(huì)被視為作弊(如果是tyvj甚至都無法提交)。 如果使用輸入重定向,那么命令提示符不會(huì)接受任何鍵盤輸入直接用文件內(nèi)容代替鍵盤了。6. 立刻退出程序:exit(0);這種方法常用于深度優(yōu)先搜索。執(zhí)行后,程序立刻停止并返回0,所以在調(diào)用前應(yīng)該輸出計(jì)算結(jié)果。頭文件:<cstdlib>7. 計(jì)時(shí):double a = (double)clock() / (double)CLOCKS_PER_SEC;上面的a對(duì)應(yīng)一個(gè)時(shí)刻。而將兩個(gè)時(shí)刻相減,就是時(shí)間間隔。可用這種方法卡時(shí)。頭文件:<ctime>8. 斷言:assert(條件) 條件為假時(shí),程序立刻崩潰。 頭文件:

53、<cassert> 如果定義了NDEBUG符號(hào),那么它將不會(huì)起任何作用。 斷言和錯(cuò)誤處理不同:例如出現(xiàn)“人數(shù)為負(fù)數(shù)”的情況,如果責(zé)任在于用戶,那么應(yīng)該提示錯(cuò)誤并重新輸入,而不是用斷言;如果發(fā)生在計(jì)算過程,應(yīng)該用斷言來使程序崩潰,以幫助改正代碼中的錯(cuò)誤。換句話說,錯(cuò)誤處理防的是用戶的錯(cuò)誤,斷言防的是代碼的錯(cuò)誤。9. 快速排序:qsort(首項(xiàng)的指針, 待排序元素個(gè)數(shù), 每個(gè)元素所占字節(jié), 比較函數(shù)) 頭文件:<cstdlib> 這是留給C黨的快速排序,它比STL的排序算法啰嗦一些。 比較函數(shù)返回int類型,用于對(duì)兩個(gè)元素的比較。原型如下:int compare(const

54、 void *i, const void *j);如果*i*j,則應(yīng)返回一個(gè)小于0的數(shù);如果*i=*j則應(yīng)返回0,否則返回一個(gè)大于0的數(shù)。10. 隨機(jī)數(shù)發(fā)生器: 頭文件:<cstdlib> 產(chǎn)生隨機(jī)數(shù): 032767的隨機(jī)數(shù):rand() 粗略地控制范圍:rand()%范圍 注意,這種方法產(chǎn)生的隨機(jī)數(shù)的分布是不均勻的。 精確地控制范圍:(double)rand()/RAND_MAX*范圍 控制在a, b)之間:a + (int) (double)rand()/RAND_MAX*(b-a) 初始化隨機(jī)數(shù)種子: srand(數(shù)字):初始化隨機(jī)數(shù)種子。 注意,這條語句在程序開頭使用,并且最多用一次。同一程序、同一平臺(tái),srand中的參數(shù)相等,用rand()產(chǎn)生的隨機(jī)數(shù)序列相同。

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論