1、Time will pierce the surface or youth, will be on the beauty of the ditch dug a shallow groove ; Jane will eat rare!A born beauty, anything to escape his sickle sweepShakespeare清華大學(xué) ACM 集訓(xùn)隊(duì)培訓(xùn)資料(內(nèi)部使用)一、C+基礎(chǔ)基本知識(shí)所有的C+程序都是有函數(shù)組成的，函數(shù)又叫做子程序，且每個(gè) C+程序必須包含一C+個(gè) main 函數(shù)，編譯器(能夠把源代碼轉(zhuǎn)換成目標(biāo)代碼的程序)把翻譯后的目標(biāo)代碼和一些 啟動(dòng)代碼組合起

2、來(lái)，生成可執(zhí)行文件， main 函數(shù)就是可執(zhí)行文件的入口，所以，每個(gè) 程序有且只有一個(gè) main 函數(shù)。下面我們看一個(gè)最簡(jiǎn)單 C+程序。(程序1.1)程序 1.1int main()return 0;在這個(gè)程序中，如果缺少任何一個(gè)字符，編譯器就無(wú)法將其翻譯成機(jī)器代碼。此外，C+是對(duì)大小寫(xiě)敏感的，這就意味著，如果我將mian()函數(shù)拼為Main(),哪么，編譯器在編譯這段程序的時(shí)候就會(huì)出錯(cuò)。編輯源文件能夠提共管理程序開(kāi)發(fā)的所有步驟，包括編輯的程序成為集成開(kāi)發(fā)環(huán)境(integrateddevelopment evironments, IDE )。在 windows 系統(tǒng)下，使用較為廣泛的有 Mic

3、rosoft Visual C+ 、 Dev-Cpp 等，在 UNIX 系統(tǒng)下，有 Vim、 emacs、 eclipes 等。這些程序都能提供一個(gè)較好的 開(kāi)發(fā)平臺(tái)，使我們能夠方便的開(kāi)發(fā)一個(gè)程序，接下我們所要了解的都是標(biāo)準(zhǔn)C+，所有源代碼都在 Dev-cpp 下編寫(xiě)，能夠編譯通過(guò)。如果我們修改程序1.1中的main()函數(shù)的名稱，將其改為 Main()，那么，IDE就會(huì)給出 錯(cuò)誤信息，比如" Linker error undefined referenee to 'WinMain16' ” 因?yàn)榫幾g器沒(méi)有找 到 main 函數(shù)。接下來(lái)，我們來(lái)看一個(gè)經(jīng)典的 C+ 例子（

4、程序 1.2）程序 1.2#include<iostream> using namespace std;int main(void)cout<<"Hello Wrold!"<<endl; return 0;運(yùn)行結(jié)果Hello World!程序說(shuō)明第一行"#include<iostream> ”是一句預(yù)處理命令，相當(dāng)于把"iostream”這個(gè)文件的所 有內(nèi)容復(fù)制到當(dāng)前位置，替換該行。因?yàn)樵谳敵霾僮髦行枰龊芏嗍拢珻+編譯器就提供了很多已經(jīng)寫(xiě)好的函數(shù)（成為C+標(biāo)準(zhǔn)庫(kù)），我們做的只是拿來(lái)用就可以了。第二行的“u

5、singnames pace std;”是使用標(biāo)準(zhǔn)命名空間，因?yàn)槲覀冊(cè)诔绦蛑杏玫搅嗽跇?biāo)準(zhǔn)命名空間里的函數(shù) 和對(duì)象。 目前可以不了解其具體如何實(shí)現(xiàn)， 在以后的程序設(shè)計(jì)中可以再對(duì)其進(jìn)行了解。 在明 函數(shù)中“ cout<< "Hello World! ”<e ndl; ”是在屏幕上打印“ Hello World!” “ en dl "表明打印 完這句話之后需要換行。如果我們替換引號(hào)內(nèi)的內(nèi)容，程序的輸出就會(huì)相應(yīng)改變。另外一個(gè) C+ 程序例子/ ourfunc.cpp - defining your own function#include <iostream

6、>void simon(int);/ function prototype for simon() int main() using namespace std;simon(3); / call the simon() function cout << "Pick an integer: "int count;cin >> count;simon(count); / call it again cout << "Done!" << endl;return 0;void simon(int n)/ de

7、fine the simon() functionusing namespace std;cout << "Simon says touch your toes " << n << " times." << endl;/ void functions don't need return statements下面試運(yùn)行情況：Simon says touch your toes 3 times.Pick an integer: 512Simon says touch your toes 512 time

8、s. Done!程序中包含了 cin 語(yǔ)句來(lái)從鍵盤(pán)上獲取數(shù)據(jù)。該程序中包含了除 main 函數(shù)以外的另一個(gè)函數(shù) simon() ，他和 main 函數(shù)定義的格式相 同，函數(shù)的統(tǒng)一格式如下： type functionname (argumentlist)statements注意，定義 simo n()的代碼在 main()函數(shù)的后面，C+中不允許將函數(shù)定義在另一個(gè)函 數(shù)內(nèi)。每個(gè)函數(shù)的定義都是獨(dú)立的，所有的函數(shù)的創(chuàng)建都是平等的。simo n()函數(shù)的函數(shù)頭定義如下：void simon(int n)以void開(kāi)頭表明simon()沒(méi)有返回值，因此我們不能類是這樣的使用它。simple = sim

9、on(3);有返回值的函數(shù)如下/ convert.cpp - converts stone to pounds #include <iostream>int stonetolb(int); / function prototypeint main()using namespace std;int stone;cout << "Enter the weight in stone: " cin >> stone;int pounds = stonetolb(stone);cout << stone << "

10、stone = "cout << pounds << " pounds." << endl; return 0;int stonetolb(int sts)return 14 * sts;下面是運(yùn)行情況：Enter the weight in sone: 14 14 stone = 196 pounds.程序通過(guò)cin語(yǔ)句給stone提供一個(gè)值，然后在main函數(shù)中，把這個(gè)值傳遞給 stonetolb() 函數(shù)，這個(gè)植被賦給 sts 之后， stonetolb() 用 return 將 14*sts 返回給 main()。函數(shù)頭

11、中的int表明stonetolb()將返回一個(gè)整數(shù)。除了 int 類型之外，C+ 的內(nèi)置數(shù)據(jù)類型還有：unsigned Iong、long、unsigned int、unsigned short、 short、 char、 unsigned char、 signed char、 bool、 float、 double、 long double。對(duì)于數(shù)據(jù)的輸入和輸出有幾道練習(xí)題 至二、算法基礎(chǔ)1. 什么是算法算法 是完成特定任務(wù)的有限指令集。 所有的算法必須滿足下面的標(biāo)準(zhǔn)：a.b.c.d.輸入 。由外部題共零個(gè)或多個(gè)輸入量。 輸出 。至少產(chǎn)生一個(gè)輸出量。 明確性 。有限性 。每條指令必須清楚，不

12、具模糊性。如果跟蹤算法的指令，那么對(duì)于所有的情況，算法經(jīng)過(guò)有限步以后終止。e.有效性 。每條指令必須非常基礎(chǔ)，原則上使用筆和紙就可以實(shí)現(xiàn)例 選擇排序void SelectionSort(Type a, int n)/Sort the arrat a1:n into nondecreasing order.for (int i=1; i<=n; i+)int j=1;for (int k=i+1; k<=n; k+)if (ak < aj) j = k;Type t = ai;ai = aj;aj = t;使用該函數(shù)時(shí)，應(yīng)將 Type替換為C+中的數(shù)據(jù)類型 3.性能分析程序P所

13、用時(shí)間定義為T(mén)(P), T(P)是編譯時(shí)間和運(yùn)行時(shí)間之和。 下面我們計(jì)算一下選擇排序運(yùn)行時(shí)所要花費(fèi)的時(shí)間Select ion Sortcosttimesfor (int i=1; i<=n; i+)ciint j=1;C2for (i nt k=i+1; k<=n; k+)C3nZ (n-i)if (ak < aj)C4nZ (n-i)j = k;C5tiC6Type t = ai; ai = aj; aj = t;那么該算法運(yùn)行的時(shí)間nT(n)=c1 n+c2n+。3送(n -i)+C4S (n -Q+Cstj+Ceni =1i ztn那么，在最壞的條件下，ti的值應(yīng)該是送

14、(n-i)i rn所以，算法的運(yùn)行時(shí)間為111 22c4-產(chǎn))n+2(c3+c4+c5)n1T(n ) =(& +C2 + Ce -;C34 -匚 C424.漸進(jìn)符號(hào)定義：大O函數(shù)f(n) =O(g( n),念做f(n)是g(n)的大”oh”，當(dāng)且僅當(dāng)存在正常數(shù) c和n。，使得對(duì)于所有的n(n 3no)，有f (n)蘭"g(n)。對(duì)于所有n >2有3n+ 2 <4n，所以3n +2 =0(n)。對(duì)于所有>6有 100n +6<101 n，所以 100n +6= 0(n)對(duì)于所有>100有 1000n? +100n -6 <1001 n2，所

15、以 1000n2 +100n -6 = 0(n2)當(dāng)然對(duì)于所有>2有 100n2 +4n + 2 <10n4，所以 10n2 +4n + 2 =0(n4)定義：Q函數(shù)f(n) =O(g(n), 念做f(n)是g(n)的"omega”當(dāng)且僅當(dāng)存在正常數(shù) c和n。，使得對(duì)于所有的 n(n>n0)，有f (n )>cxg (n)。對(duì)于所有 n >1 有6x2n + n2 >2n，所以 6x2n + n2 =0(2")。當(dāng)然 6>c2n + n2 =C(n)，但是 O(nQ(2n)。現(xiàn)然無(wú)論是0還是Q,都不能精確的描述一個(gè)函數(shù)定義：創(chuàng)函數(shù)f

16、(n)=0(g(n)，念做f(n)是g(n)的”theta”，當(dāng)且僅當(dāng)存在正常數(shù) c1,c2和 n0，使得對(duì)于所有的 n(n > n。)，有 &§(n) < f (n) Ec2g(n)。對(duì)于 n >2有 3n + 2 >3n 且 3n +2 <4n，所以 3n + 2 =0(n)記號(hào)要比O和Q都要精確。排列生成器( n!)void P erm(T ype a, int k, int n)if (k=n) /Out put p ermutati on.for (i nt i-1; i<n; i+) cout<<ai<<

17、" ”；else /ak:n has more tha n one p ermutati on. / Gen erate these recursively.for (i nt i=k; i<=n; i+)Type t=ak; ak=ai; ai=t;Perm(a, k+1, n);/All p ermutati ons of ak+1: n t=ak; ak=ai; ai=t; elseint i;for (i=0; i<n; i+)if (k<n-1)int i, t;for (i=k; i<n; i+)cout<<ai<<'

18、;t't = ak;ak = ai; cout<<endl;ai = t;Perm(a, k+1, n);int main(void)t = ak; ak = ai;int a3 = 1, 2, 3;Perm(a, 0, 3); return 0;對(duì)于下面的程序#include<iostream> using namespace std;void Perm(int a, int k, int n)ai = t;該程序的運(yùn)行結(jié)果為33那么，該函數(shù)就完成了對(duì)一個(gè)數(shù)組進(jìn)行全排列的操作 下面，分析該程序，我用圓圈代表每次函數(shù)的調(diào)用 每次函數(shù)的調(diào)用都用序號(hào)表示1.a: 1

19、 2 3k: 06.a: 2 1 3k: 22.a: 1 2 3k: 17.a: 2 3 1k: 23.a: 1 2 3k: 28.a: 3 2 1k: 14.a: 1 3 2k: 29.a: 3 2 1k: 25.a: 2 1 3k: 110.a: 3 1 2k: 2排列生成器的另外一個(gè)版本他將輸出給定n個(gè)布爾變量的所有可能的組合void Perm (bool a, int k, int n) if (k = n)/stateme nt elseak = true;Perm(a, k+1, n); ak = false;Perm(a, k+1, n); 在上次冬季賽上有這么一道題競(jìng)賽真理JU

20、NNY在經(jīng)歷了無(wú)數(shù)次學(xué)科競(jìng)賽的失敗以后，得到了一個(gè)真理：做一題就要對(duì)一題！但是 要完全正確地做對(duì)一題是要花很多時(shí)間（包括調(diào)試時(shí)間），而競(jìng)賽的時(shí)間有限。所以開(kāi)始做題之前最好先認(rèn)真審題， 估計(jì)一下每一題如果要完全正確地做出來(lái)所需要的時(shí)間，然后選擇一些有把握的題目先做。當(dāng)然，如果做完了預(yù)先選擇的題目之后還有時(shí)間，但是這些時(shí)間又不足以完全解決一道題目，應(yīng)該把其他的題目用貪心之類的算法隨便做做，爭(zhēng)取“騙”-點(diǎn)分?jǐn)?shù)。 根據(jù)每一題解題時(shí)間的估計(jì)值， 確定一種做題方案 （即哪些題目認(rèn)真做， 哪些題目 “騙”分， 哪些不做），使能在限定的時(shí)間內(nèi)獲得最高的得分。INPUT FORMAT: 從標(biāo)準(zhǔn)輸入（ cin,s

21、canf 等）讀入數(shù)據(jù)。數(shù)據(jù)有多組，先輸入 兩個(gè)正整數(shù)N和T,表示題目的總數(shù)以及競(jìng)賽的時(shí)限（單位秒） 整數(shù) W1i 、 T1i 、 W2i 、 T2i ，分別表示第 i 題： 來(lái)所花費(fèi)的時(shí)間 （單位： 秒） ，“騙”來(lái)的分?jǐn)?shù)， “騙”N < 30, 2 < T < 1080000, 1 < W1i 、W2iK （ K 組數(shù)據(jù)）。每組第一行有 。以下的N行，每行4個(gè)正 完全正確做出來(lái)的得分，完全正確做出 分所花費(fèi)的時(shí)間（單位秒）。其中，3 << 30000,< T1i 、T2i < T。OUTPUT FORMA T: 直接把所求得的最高得分輸出。數(shù)

22、據(jù)之間需換行。SAMPLE INPUT:24 1080018 3600 3 180022 4000 12 300028 6000 0 300032 8000 24 60003 720050 5400 10 90050 7200 10 90050 5400 10 900SAMPLE OUTPUT :5070下面我們對(duì)問(wèn)題進(jìn)行簡(jiǎn)化。我們只要考慮是做題還是不做題。 從標(biāo)準(zhǔn)輸入（ cin,scanf 等）讀入數(shù)據(jù)。數(shù)據(jù)只有一組，先輸入 有兩個(gè)正整數(shù)N和T,表示題目的總數(shù)以及競(jìng)賽的時(shí)限（單位秒） 正整數(shù)Wi、Ti，分別表示第i題：做出來(lái)的得分和做出來(lái)所花費(fèi)的時(shí)間 FORMAT:直接把所求得的最高得分輸出

23、。數(shù)據(jù)之間需換行。K 組數(shù)據(jù)）。每組第一行。以下的N行，每行2個(gè)1 （單位：秒），OUTPUTSAMPLE INPUT:5 101 205 104 153 202 10SAMPLE OUTPUT :65下面是用全排列生成器完成的代碼#include<iostream>using namespace std;score += tx1;time += tx0;int m;int t202;int tSum;void work(bool a, int n);void f(bool a, int k, int n)if (k < n)if (time <= tSum)if (s

24、core > m)m = score;ak = true; f(a, k+1, n); ak = false; f(a, k+1, n);voidwork(bool a, int n)elsework(a, n);int main(void)bool a30; int n, c; cin>>n>>tSum;m = 0;for (c=0; c<n; c+) int x;int time=0, score=0;cin>>tc0;cin>>tc1;for (x=0; x<n; x+) if (ax) 通過(guò)一個(gè)排列生成器將所有的可能送入 最高的分?jǐn)?shù)。 f(a, 0, n); cout<<m<<endl; return 0;work() 函數(shù)內(nèi)，然后 work函數(shù)找到在時(shí)間范圍內(nèi)的現(xiàn)在我們將其優(yōu)化，將work()和f()合并，就能得到更好的程序#include<iostream>using namespace std;if (k < n) int m;int t202; int tSum;dfs(k+1,n, cScore , cTime);voi