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 sweep.- Shakespeare清華大學 ACM 集訓隊培訓資料(內(nèi)部使用)一、 C+ 基礎基本知識所有的 C+ 程序都是有函數(shù)組成的， 函數(shù)又叫做子程序，且每個 C+ 程序必須包含一 個 main 函數(shù)，編譯器(能夠把源代碼轉換成目標代碼的程序)把翻譯后的目標代碼和一些

2、 啟動代碼組合起來，生成可執(zhí)行文件， main 函數(shù)就是可執(zhí)行文件的入口，所以，每個 C+ 程序有且只有一個 main 函數(shù)。下面我們看一個最簡單 C+ 程序。 (程序 1.1)程序 1.1 int main()return 0;在這個程序中，如果缺少任何一個字符，編譯器就無法將其翻譯成機器代碼。此外，C+是對大小寫敏感的，這就意味著，如果我將mian()函數(shù)拼為Main(),哪么，編譯器在編譯這段程序的時候就會出錯。編輯源文件 能夠提共管理程序開發(fā)的所有步驟，包括編輯的程序成為集成開發(fā)環(huán)境(integrateddevelopment evironments, IDE )。在 windows

3、系統(tǒng)下，使用較為廣泛的有 Microsoft Visual C+ 、 Dev-Cpp 等，在 UNIX 系統(tǒng)下，有 Vim 、 emacs、 eclipes 等。這些程序都能提供一個較好的 開發(fā)平臺， 使我們能夠方便的開發(fā)一個程序， 接下我們所要了解的都是標準 C+ ，所有源代 碼都在 Dev-cpp 下編寫，能夠編譯通過。如果我們修改程序1.1中的main()函數(shù)的名稱，將其改為 Main()，那么，IDE就會給出 錯誤信息，比如" Linker error undefined referenee to 'WinMain16' ”，因為編譯器沒有找 到 main 函

4、數(shù)。接下來，我們來看一個經(jīng)典的C+例子(程序1.2)程序 1.2#inelude<iostream> using namespaee std;int main(void)eout<<"Hello Wrold!"<<endl;return 0;運行結果Hello World!程序說明第一行"#include<iostream> ”，是一句預處理命令，相當于把"iostream”這個文件的所 有內(nèi)容復制到當前位置，替換該行。因為在輸出操作中需要做很多事，C+編譯器就提供了很多已經(jīng)寫好的函數(shù)(成為C+標準庫)，我

5、們做的只是拿來用就可以了。第二行的“usingnamespace std;”是使用標準命名空間，因為我們在程序中用到了在標準命名空間里的函數(shù) 和對象。 目前可以不了解其具體如何實現(xiàn)， 在以后的程序設計中可以再對其進行了解。 在明 函數(shù)中“ cout<< "Hello World! "<<e ndl; ”是在屏幕上打印“ Hello World!”，“ en dl ”表明打印 完這句話之后需要換行。如果我們替換引號內(nèi)的內(nèi)容，程序的輸出就會相應改變。另外一個 C+ 程序例子/ ourfunc.cpp - defining your own functio

6、n#include <iostream>void simon(int); / function prototype for simon()int main()using namespace std;simon(3);/ call the simon() functioncout << "Pick an integer: "int count;cin >> count;simon(count); / call it againcout << "Done!" << endl;return 0;voi

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

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

9、imple = simon(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;下面是運行情況：Enter the weight in sone: 1414 stone = 196 pounds.程序通過cin語句給stone提供一個值，然后在main函數(shù)中，把這個值傳遞給 stonetolb()函數(shù)，這個植被賦給sts之后，stonetolb()用return 將14*sts返回給 main()。函數(shù)頭

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

12、條指令必須清楚，不具模糊性。d. 有限性。如果跟蹤算法的指令，那么對于所有的情況，算法經(jīng)過有限步以后終止。e. 有效性。每條指令必須非常基礎，原則上使用筆和紙就可以實現(xiàn)例選擇排序void Select ion Sort(Type a, int n)/Sort the arrat a1: n into non decreas ing order.for (int i=1; i<=n; i+)int j=1;for (i nt k=i+1; k<=n; k+)if (ak < aj)j = k;Type t = ai;ai = aj;aj = t;使用該函數(shù)時，應將Type替換為

13、C+中的數(shù)據(jù)類型3 性能分析Select ion Sort程序P所用時間定義為 T(P), T(P)是編譯時間和運行時間之和。 下面我們計算一下選擇排序運行時所要花費的時間C1nC2nnC3二(n - i)itimes costfor (int i=1; i<=n; i+)int j=1;for (i nt k=i+1; k<=n; k+)nif (ak < aj)C4'、(ni)k4j = k；C5tiType t = ai; ai =aj; aj = t;C6n那么該算法運行的時間nnT n =5n C2n C3' (ni) C4' (ni) C5

14、ti C6ni 二idn那么，在最壞的條件下，ti的值應該是a (n-i)i -1所以，算法的運行時間為111 1 2T n i=(G C2 C6C34C4C5)n (C3 C4 C5)n2 2 2 24 漸進符號定義：大O函數(shù)f(n) =0(g( n),念做f(n)是g(n)的大”oh”當且僅當存在正常數(shù) c和n°，使得對于所有的n(n_n°)，有f (n )c g(n)。例對于所有n - 2有3n 2乞4n，所以3n - 2 =0(n)。對于所有 n - 6有 100n6 101n，所以 100n 6 = O( n)對于所有 n _100有 1000n2 100n -6

15、 豈 1001 n2，所以 1000n2 100n -6 =O(n2)當然對于所有 n 2有 100n2 4n 2 _10n4，所以 10n2 4n 2 =O(n4)定義：Q函數(shù)f(n) =C(g( n)，念做f(n)是g(n)的”omega”當且僅當存在正常數(shù) c和n°,使得對于所有的n(nn°)，有f (n )_c g(n)。例對于所有有6 2n - n2-2n，所以 6 2n - n2f】(2n)。當然 62n n2-門(n)，但是門(n)T2n)。現(xiàn)然無論是O還是Q,都不能精確的描述一個函數(shù)定義：創(chuàng)函數(shù)f(n)=O(g(n)，念做f(n)是g(n)的”theta”，

16、當且僅當存在正常數(shù) c1,c2和no，使得對于所有的n(n _ n°)，有Gg(n)乞f (n)乞c?g(n)。例對于 n _ 2有 3n 2 _ 3n 且 3n 2 乞 4n，所以 3n 2 - c-j (n)記號要比O和Q都要精確。排列生成器0( n!)void Perm(Type a, int k, int n)if (k=n) /Output permutati on.for (i nt i-1; i<n; i+) cout<<ai<<""else ak:n has more than one permutation. / G

17、en erate these recursively.for (i nt i=k; i<=n; i+)Type t=ak; ak=ai; ai=t;Perm(a, k+1, n);/All permutati ons of ak+1: n t=ak; ak=ai; ai=t;對于下面的程序else#in clude<iostream>using n amespace std;void Perm(i nt a, int k, int n)if (k< n-1)int i, t;for (i=k; i<n; i+)t = ak;ak = ai; ai = t;Perm

18、(a, k+1, n); t = ak;ak = ai; ai = t;int i;for (i=0; i<n; i+)cout<<ai<<'t'cout<<e ndl;int main( void)int a3 = 1,2, 3;Perm(a, 0, 3);return 0;1.a: 1 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 2

19、k: 2排列生成器的另外一個版本他將輸出給定n個布爾變量的所有可能的組合該程序的運行結果為1 231 322 132 313 213 12那么，該函數(shù)就完成了對一個數(shù)組進行全排列的操作 下面，分析該程序，我用圓圈代表每次函數(shù)的調用 每次函數(shù)的調用都用序號表示k=0k=2285369107void 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); 在上次冬季賽上有這么一道題 競賽真理JUNNY 在經(jīng)歷了無數(shù)次學科競賽的失敗以后，得

20、到了一個真理：做一題就要對一題！但是 要完全正確地做對一題是要花很多時間（包括調試時間） ，而競賽的時間有限。所以開始做 題之前最好先認真審題， 估計一下每一題如果要完全正確地做出來所需要的時間，然后選擇一些有把握的題目先做。 當然，如果做完了預先選擇的題目之后還有時間，但是這些時間 又不足以完全解決一道題目，應該把其他的題目用貪心之類的算法隨便做做，爭取“騙” 一點分數(shù)。根據(jù)每一題解題時間的估計值， 確定一種做題方案 （即哪些題目認真做， 哪些題目 “騙”分， 哪些不做），使能在限定的時間內(nèi)獲得最高的得分。INPUT FORMAT:從標準輸入（ cin,scanf 等）讀入數(shù)據(jù)。數(shù)據(jù)有多組，

21、先輸入K （ K 組數(shù)據(jù)）。每組第一行有兩個正整數(shù)N和T,表示題目的總數(shù)以及競賽的時限（單位秒）。以下的N行，每行4個正整數(shù) W1i 、T1i 、W2i 、T2i ，分別表示第 i 題：完全正確做出來的得分，完全正確做出 來所花費的時間（單位：秒），“騙”來的分數(shù)，“騙”分所花費的時間（單位秒）。其中，3 <N < 30, 2 < T < 1080000, 1 < W1i、W2i < 30000, 1 < T1i、T2i < T。OUTPUT FORMA T: 直接把所求得的最高得分輸出。數(shù)據(jù)之間需換行。SAMPLE INPUT:24 10800

22、18 3600 3 180022 4000 12 300028 6000 0 300032 8000 24 60003 720050 5400 10 90050 7200 10 90050 5400 10 900SAMPLE OUTPUT :5070下面我們對問題進行簡化。我們只要考慮是做題還是不做題。從標準輸入（ cin,scanf 等）讀入數(shù)據(jù)。數(shù)據(jù)只有一組,先輸入 K（ K 組數(shù)據(jù)）。每組第一行 有兩個正整數(shù) N和T,表示題目的總數(shù)以及競賽的時限（單位秒） 。以下的N行，每行2個 正整數(shù) Wi、Ti，分別表示第i題：做出來的得分和做出來所花費的時間 （單位：秒），OUTPUT FORMA

23、T:直接把所求得的最高得分輸出。數(shù)據(jù)之間需換行。SAMPLE INPUT:5 101 205 104 153 202 10void work(bool a, int n)int x;int time=0, score=0;for (x=0; x<n; x+)if (ax) 通過一個排列生成器將所有的可能送入 最高的分數(shù)。int main(void)bool a30;int n, c;cin>>n>>tSum;m = 0;for (c=0; c<n; c+)cin>>tc0;cin>>tc1;f(a, 0, n);cout<<

24、;m<<endl;return 0;work() 函數(shù)內(nèi)，然后 work 函數(shù)找到在時間范圍內(nèi)的SAMPLE OUTPUT :65下面是用全排列生成器完成的代碼 #include<iostream> using namespace std;int m;int t202;int tSum;void work(bool a, int n);void f(bool a, int k, int n) if (k < n)ak = true; f(a, k+1, n); ak = false; f(a, k+1, n);elsework(a, n);score += tx1; time += tx0;if (time <= tSum)if (score > m)m = score;現(xiàn)在我們將其優(yōu)化，將 work() 和 f() 合并，就能得到更好的程序int m;using namespace std;#include<iostream>int t202; int tSum;int main(void)int n, c; cin>>n>>tSum;m = 0;for (c=0; c<n; c+) cin>>tc0;cin>>