Dqsscha清華大學(xué)ACM集訓(xùn)隊(duì)企業(yè)培訓(xùn)資料全

1、. .PAGE11 / NUMPAGES11Time 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清華大學(xué)ACM集訓(xùn)隊(duì)培訓(xùn)資料（部使用）一、C+基礎(chǔ)基本知識所有的C+程序都是有函數(shù)組成的， 函數(shù)又叫做子程序，且每個C+程序必須包含一個main函數(shù)，編譯器（能夠把源代碼轉(zhuǎn)換成目標(biāo)代碼的程序）把翻

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

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

4、amespace std;int main(void)coutHello Wrold!endl;return 0;運(yùn)行結(jié)果Hello World!程序說明第一行“#include”，是一句預(yù)處理命令，相當(dāng)于把“iostream”這個文件的所有容復(fù)制到當(dāng)前位置，替換該行。因?yàn)樵谳敵霾僮髦行枰龊芏嗍拢珻+編譯器就提供了很多已經(jīng)寫好的函數(shù)(成為C+標(biāo)準(zhǔn)庫)，我們做的只是拿來用就可以了。第二行的“using namespace std;”是使用標(biāo)準(zhǔn)命名空間，因?yàn)槲覀冊诔绦蛑杏玫搅嗽跇?biāo)準(zhǔn)命名空間里的函數(shù)和對象。目前可以不了解其具體如何實(shí)現(xiàn)，在以后的程序設(shè)計中可以再對其進(jìn)行了解。在明函數(shù)中“cout”H

5、ello World!”endl;”是在屏幕上打印“Hello World!eHeH”，“endl”表明打印完這句話之后需要換行。如果我們替換引號的容，程序的輸出就會相應(yīng)改變。另外一個C+程序例子/ ourfunc.cpp - defining your own function#include void simon(int); / function prototype for simon()int main() using namespace std; simon(3); / call the simon() function cout count; simon(count); / call

6、 it again cout Done! endl; return 0;void simon(int n) / define the simon() function using namespace std; cout Simon says touch your toes n times. endl; / void functions dont need return statements下面試運(yùn)行情況：Simon says touch your toes 3 times.Pick an integer: 512Simon says touch your toes 512 times.Done

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

8、rt.cpp - converts stone to pounds#include int stonetolb(int); / function prototypeint main() using namespace std; int stone; cout stone; int pounds = stonetolb(stone); cout stone stone = ; cout pounds pounds. endl; return 0;int stonetolb(int sts) return 14 * sts;下面是運(yùn)行情況：Enter the weight in sone: 141

9、4 stone = 196 pounds.程序通過cin語句給stone提供一個值，然后在main函數(shù)中，把這個值傳遞給stonetolb()函數(shù)，這個植被賦給sts之后，stonetolb()用return將 14*sts返回給main()。函數(shù)頭中的int表明stonetolb()將返回一個整數(shù)。除了int類型之外，C+的置數(shù)據(jù)類型還有：unsigned long、long、unsigned int、unsigned short、short、char、unsigned char、signed char、bool、float、double、long double。對于數(shù)據(jù)的輸入和輸出有幾道練

10、習(xí)題 什么是算法算法是完成特定任務(wù)的有限指令集。所有的算法必須滿足下面的標(biāo)準(zhǔn)：輸入。由外部題共零個或多個輸入量。輸出。至少產(chǎn)生一個輸出量。明確性。每條指令必須清楚，不具模糊性。有限性。如果跟蹤算法的指令，那么對于所有的情況，算法經(jīng)過有限步以后終止。有效性。每條指令必須非?；A(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

11、)j = k;Type t = ai;ai = aj;aj = t;使用該函數(shù)時，應(yīng)將Type替換為C+中的數(shù)據(jù)類型3性能分析程序P所用時間定義為T(P), T(P)是編譯時間和運(yùn)行時間之和。下面我們計算一下選擇排序運(yùn)行時所要花費(fèi)的時間SelectionSortcosttimesfor (int i=1; i=n; i+)c1SKIPIF 1 0 int j=1;c2SKIPIF 1 0 for (int k=i+1; k=n; k+)c3SKIPIF 1 0 if (ak aj)c4SKIPIF 1 0 j = k;c5SKIPIF 1 0 Type t = ai; ai = aj; aj

12、= t;c6SKIPIF 1 0 那么該算法運(yùn)行的時間SKIPIF 1 0 那么，在最壞的條件下，SKIPIF 1 0 的值應(yīng)該是SKIPIF 1 0 所以，算法的運(yùn)行時間為SKIPIF 1 0 4漸進(jìn)符號定義： 大O函數(shù)SKIPIF 1 0 ，念做SKIPIF 1 0 是SKIPIF 1 0 的大”oh”，當(dāng)且僅當(dāng)存在正常數(shù)SKIPIF 1 0 和SKIPIF 1 0 ，使得對于所有的SKIPIF 1 0 ，有SKIPIF 1 0 。例對于所有SKIPIF 1 0 有SKIPIF 1 0 ，所以SKIPIF 1 0 。對于所有SKIPIF 1 0 有SKIPIF 1 0 ，所以SKIPIF

13、1 0 對于所有SKIPIF 1 0 有SKIPIF 1 0 ，所以SKIPIF 1 0 當(dāng)然對于所有SKIPIF 1 0 有SKIPIF 1 0 ，所以SKIPIF 1 0 定義： 函數(shù)SKIPIF 1 0 ，念做SKIPIF 1 0 是SKIPIF 1 0 的”omega”，當(dāng)且僅當(dāng)存在正常數(shù)SKIPIF 1 0 和SKIPIF 1 0 ，使得對于所有的SKIPIF 1 0 ，有SKIPIF 1 0 。例對于所有SKIPIF 1 0 有SKIPIF 1 0 ，所以SKIPIF 1 0 。當(dāng)然SKIPIF 1 0 ，但是SKIPIF 1 0 ?，F(xiàn)然無論是O還是，都不能精確的描述一個函數(shù)定義：

14、 函數(shù)SKIPIF 1 0 ，念做SKIPIF 1 0 是SKIPIF 1 0 的”theta”，當(dāng)且僅當(dāng)存在正常數(shù)SKIPIF 1 0 和SKIPIF 1 0 ，使得對于所有的SKIPIF 1 0 ，有SKIPIF 1 0 。例對于SKIPIF 1 0 有SKIPIF 1 0 且SKIPIF 1 0 ，所以SKIPIF 1 0 記號要比O和都要精確。排列生成器(n!)void Perm(Type a, int k, int n)if (k=n) /Output permutation.for (int i-1; in; i+) coutai ;else /ak:n has more than

15、 one permutation. / Generate these recursively.for (int i=k; i=n; i+)Type t=ak; ak=ai; ai=t;Perm(a, k+1, n);/All permutations of ak+1:nt=ak; ak=ai; ai=t;對于下面的程序#includeusing namespace std;void Perm(int a, int k, int n)if (kn-1)int i, t;for (i=k; in; i+)t = ak;ak = ai;ai = t;Perm(a, k+1, n);t = ak;ak

16、 = ai;ai = t;elseint i;for (i=0; in; i+)coutait;coutendl;int main(void)int a3 = 1, 2, 3;Perm(a, 0, 3);return 0;該程序的運(yùn)行結(jié)果為123132213231321312那么，該函數(shù)就完成了對一個數(shù)組進(jìn)行全排列的操作下面，分析該程序，我用圓圈代表每次函數(shù)的調(diào)用每次函數(shù)的調(diào)用都用序號表示12853467910k=0k=1k=2a: 1 2 3 k: 0a: 1 2 3 k: 1a: 1 2 3k: 2a: 1 3 2k: 2a: 2 1 3k: 1a: 2 1 3k: 2a: 2 3 1k:

17、 2a: 3 2 1k: 1a: 3 2 1k: 2a: 3 1 2k: 2排列生成器的另外一個版本他將輸出給定n個布爾變量的所有可能的組合void Perm (bool a, int k, int n)if (k = n)/statementelseak = true; Perm(a, k+1, n);ak = false;Perm(a, k+1, n);在上次冬季賽上有這么一道題競賽真理 JUNNY在經(jīng)歷了無數(shù)次學(xué)科競賽的失敗以后，得到了一個真理：做一題就要對一題！但是要完全正確地做對一題是要花很多時間（包括調(diào)試時間），而競賽的時間有限。所以開始做題之前最好先認(rèn)真審題，估計一下每一題如果要

18、完全正確地做出來所需要的時間，然后選擇一些有把握的題目先做。 當(dāng)然，如果做完了預(yù)先選擇的題目之后還有時間，但是這些時間又不足以完全解決一道題目，應(yīng)該把其他的題目用貪心之類的算法隨便做做，爭取“騙”一點(diǎn)分?jǐn)?shù)。 根據(jù)每一題解題時間的估計值，確定一種做題方案（即哪些題目認(rèn)真做，哪些題目“騙”分，哪些不做），使能在限定的時間獲得最高的得分。 INPUT FORMAT: 從標(biāo)準(zhǔn)輸入（cin,scanf等）讀入數(shù)據(jù)。數(shù)據(jù)有多組，先輸入K（K組數(shù)據(jù)）。每組第一行有兩個正整數(shù)N和T，表示題目的總數(shù)以與競賽的時限（單位秒）。以下的N行，每行個正整數(shù)W1i 、T1i 、W2i 、T2i ，分別表示第i題：完全正確

19、做出來的得分，完全正確做出來所花費(fèi)的時間（單位：秒），“騙”來的分?jǐn)?shù)，“騙”分所花費(fèi)的時間（單位秒）。其中，3 N 30，2 T 1080000，1 W1i 、W2i 30000，1 T1i 、T2i T。 OUTPUT FORMAT: 直接把所求得的最高得分輸出。數(shù)據(jù)之間需換行。 SAMPLE INPUT: 2 4 10800 18 3600 3 1800 22 4000 12 3000 28 6000 0 3000 32 8000 24 6000 3 7200 50 5400 10 900 50 7200 10 900 50 5400 10 900 SAMPLE OUTPUT : 50 7

20、0下面我們對問題進(jìn)行簡化。我們只要考慮是做題還是不做題。從標(biāo)準(zhǔn)輸入（cin,scanf等）讀入數(shù)據(jù)。數(shù)據(jù)只有一組，先輸入K（K組數(shù)據(jù)）。每組第一行有兩個正整數(shù)N和T，表示題目的總數(shù)以與競賽的時限（單位秒）。以下的N行，每行個正整數(shù)Wi 、Ti，分別表示第i題：做出來的得分和做出來所花費(fèi)的時間（單位：秒），OUTPUT FORMAT: 直接把所求得的最高得分輸出。數(shù)據(jù)之間需換行。 SAMPLE INPUT: 5 101 205 104 153 202 10SAMPLE OUTPUT : 65下面是用全排列生成器完成的代碼#includeusing namespace std;int m;int

21、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);void work(bool a, int n)int x;int time=0, score=0;for (x=0; xn; x+)if (ax)score += tx1;time += tx0;if (time m)m = score;int main(void)bool a30;int n, c;cinntSum;m = 0;for (c=0; ctc0;cintc1;f(a, 0, n);coutmendl;return 0;通過一個排列生成器將所有的可能送入work()函數(shù)，然后work函數(shù)找到在時間圍的最高的分?jǐn)?shù)。現(xiàn)在我們將其優(yōu)化，將work()和f()合并，就能得到更好的程序#includeusing namespace std;int m;int t202;