1、第5章 基礎(chǔ)題目選解第5章 基礎(chǔ)題目選解【教學(xué)內(nèi)容相關(guān)章節(jié)】5.1字符串 5.2高精度運算 5.3排序與檢索5.4數(shù)學(xué)基礎(chǔ) 5.5訓(xùn)練參考 【教學(xué)目標】（1）學(xué)會用常量表簡化代碼；（2）學(xué)會用狀態(tài)變量輔助字符串輸入；（3）學(xué)會用結(jié)構(gòu)體定義高精度整數(shù)，并設(shè)計構(gòu)造函數(shù)、復(fù)制構(gòu)造函數(shù)和輸入輸出方法；（4）學(xué)會為結(jié)構(gòu)體定義“小于”運算符，并用它定義其他比較運算符；（5）熟練掌握冒泡排序和順序搜索；（6）熟練掌握用qsort庫函數(shù)給整數(shù)和字符串排序的方法；（7）熟練掌握小規(guī)模素數(shù)表的構(gòu)造方法；（8）熟練掌握素因子分解的方法；（9）熟練掌握三角形有向面積的意義和計算方法；（10）完成一定數(shù)量的編程練習(xí)?！?/p>

2、教學(xué)要求】掌握字符串的操作，用狀態(tài)變量輔助字符串輸入；掌握高精度整數(shù)的計算；掌握有關(guān)排序與檢索的算法；掌握素數(shù)的計算和分解素因子方法；掌握有向三角形的面積的計算方法。【教學(xué)內(nèi)容提要】在算法競賽中，編程能力是非常重要的。算法設(shè)計得再好，如果程序?qū)懖怀鰜砭褪橇惴?；即使程序?qū)懗鰜砹?，也可能會因為細小的錯誤導(dǎo)致丟失大量的得分。本章通過一定數(shù)量和類型的例題和習(xí)題熟悉常見的編程技巧，為接下來的算法學(xué)習(xí)打下堅實的基礎(chǔ)。在本章中，程序的正確性是第一位的?！窘虒W(xué)重點、難點】教學(xué)重點：（1）掌握字符串的操作，用狀態(tài)變量輔助字符串輸入；（2）掌握高精度整數(shù)的計算；（3）掌握有關(guān)排序與檢索的算法；（4）掌握素數(shù)的計算

3、和分解素因子方法；（5）掌握有向三角形的面積的計算方法。教學(xué)難點：（1）掌握高精度整數(shù)的計算；（2）掌握有關(guān)排序與檢索的算法；（3）掌握素數(shù)的計算和分解素因子方法。【課時安排（共5學(xué)時）】5.1字符串 5.2高精度運算 5.3排序與檢索5.4數(shù)學(xué)基礎(chǔ) 5.5訓(xùn)練參考 5.1 字符串5.1.1 WERTYU把手放在鍵盤上時，稍不注意就會往右錯一位。這樣的話，Q會變成W，J會變成K等。輸入一個錯位敲出的字符串，輸出打字員本來想打出的句子。樣例輸入：O S,GOMR YPFSU/樣例輸出：I AMFINE TODAY.【分析】每輸入一個字符，都可以直接輸出一個字符。但是對輸入的字符轉(zhuǎn)換成輸出的字符的

4、一種較好的方法是使用常量數(shù)組。完整的程序如下：#include <stdio.h>char *s = "1234567890-=QWERTYUIOPASDFGHJKL;'ZXCVBNM,./"int main() int i,c; while (c = getchar() != EOF) for (i=1; si && si!=c; i+) ; /* 空語句 */ if (si) putchar(si-1); else putchar(c); return 0;說明：現(xiàn)將getchar函數(shù)與EOF總結(jié)如下：（1）對于getchar的兩點總

5、結(jié)getchar是以行為單位進行存取的。當(dāng)用getchar進行輸入時，如果輸入的第一個字符為有效字符(即輸入是文件結(jié)束符EOF，Windows下為組合鍵Ctrl+Z，Unix/Linux下為組合鍵Ctrl+D)，那么只有當(dāng)最后一個輸入字符為換行符'n'(也可以是文件結(jié)束符EOF)時，getchar才會停止執(zhí)行，整個程序?qū)聢?zhí)行。譬如下面程序段：while(c = getchar() != EOF)    putchar(c);執(zhí)行程序，輸入：abc，然后回車。則程序就會去執(zhí)行puchar(c)，然后輸出abc，這個地方不要忘了，系統(tǒng)輸出的還有一個回車。然

6、后可以繼續(xù)輸入，再次遇到換行符的時候，程序又會把那一行的輸入的字符輸出在終端上。對于getchar必須讀到一個換行符或者文件結(jié)束符EOF才進行一次輸出。對這個問題的一個解釋是，在大師編寫C的時候，當(dāng)時并沒有所謂終端輸入的概念，所有的輸入實際上都是按照文件進行讀取的，文件中一般都是以行為單位的。因此，只有遇到換行符，那么程序會認為輸入結(jié)束，然后采取執(zhí)行程序的其他部分。同時，輸入是按照文件的方式存取的，那么要結(jié)束一個文件的輸入就需用到EOF (Enf Of File)，這也就是為什么getchar結(jié)束輸入退出時要用EOF的原因。getchar()的返回值一般情況下是字符，但也可能是負值，即返回EO

7、F。getchar函數(shù)的返回值類型不是char類型，而是int類型。其原型如下：int getchar(void);需要強調(diào)的是getchar函數(shù)通常返回終端所輸入的字符，這些字符系統(tǒng)中對應(yīng)的ASCII值都是非負的。因此，很多時候，我們會寫這樣的兩行代碼：char c;c = getchar();這樣就很有可能出現(xiàn)問題。因為getchar函數(shù)除了返回終端輸入的字符外，在遇到Ctrl+D(Linux下)即文件結(jié)束符EOF時，getchar()的返回EOF，這個EOF在函數(shù)庫里一般定義為-1。因此，在這種情況下，getchar函數(shù)返回一個負值，把一個負值賦給一個char型的變量是不正確的。導(dǎo)致這種

8、錯誤的責(zé)任并不是用戶，是函數(shù)getchar函數(shù)誤導(dǎo)了使用者。為了能夠讓所定義的變量能夠包含getchar函數(shù)返回的所有可能的值，正確的定義方法為：int c;c = getchar();（2）EOF的兩點總結(jié)(主要指普通終端中的EOF)EOF作為文件結(jié)束符時的情況EOF雖然是文件結(jié)束符，但并不是在任何情況下輸入Ctrl+D(Windows下Ctrl+Z)都能夠?qū)崿F(xiàn)文件結(jié)束的功能，只有在下列的條件下，才作為文件結(jié)束符。(a)遇到getcahr函數(shù)執(zhí)行時，要輸入第一個字符時就直接輸入Ctrl+D，就可以跳出getchar(),去執(zhí)行程序的其他部分；(b)在前面輸入的字符為換行符時，接著輸入Ctrl

9、+D；(c)在前面有字符輸入且不為換行符時，要連著輸入兩次Ctrl+D，這時第二次輸入的Ctrl+D起到文件結(jié)束符的功能，至于第一次的Ctrl+D的作用將在下面介紹。其實，這三種情況都可以總結(jié)為只有在getchar()提示新的一次輸入時，直接輸入Ctrl+D才相當(dāng)于文件結(jié)束符。EOF作為行結(jié)束符時的情況，這時候輸入Ctrl+D并不能結(jié)束getchar(),而只能引發(fā)getchar()提示下一輪的輸入。這種情況主要是在進行g(shù)etchar()新的一行輸入時，當(dāng)輸入了若干字符(不能包含換行符)之后，直接輸入Ctrl+D，此時的Ctrl+D并不是文件結(jié)束符，而只是相當(dāng)于換行符的功能，即結(jié)束當(dāng)前的輸入。

10、以上面的代碼段為例，如果執(zhí)行時輸入abc，然后Ctrl+D，程序輸出結(jié)果為：abcabc注意：第一組abc為從終端輸入的，然后輸入Ctrl+D，就輸出第二組abc，同時光標停在第二組字符的c后面,然后可以進行新一次的輸入。這時如果再次輸入Ctrl+D，則起到了文件結(jié)束符的作用，結(jié)束getchar（）。如果輸入abc之后，然后回車，輸入換行符的話，則終端顯示為：abc       /第一行，帶回車abc       /第二行          /第

11、三行其中第一行為終端輸入，第二行為終端輸出，光標停在了第三行處，等待新一次的終端輸入。從這里也可以看出Ctrl+D和換行符分別作為行結(jié)束符時，輸出的不同結(jié)果。EOF的作用也可以總結(jié)為：當(dāng)終端有字符輸入時，Ctrl+D產(chǎn)生的EOF相當(dāng)于結(jié)束本行的輸入，將引起getchar()新一輪的輸入；當(dāng)終端沒有字符輸入或者可以說當(dāng)getchar()讀取新的一次輸入時，輸入Ctrl+D，此時產(chǎn)生的EOF相當(dāng)于文件結(jié)束符，程序?qū)⒔Y(jié)束getchar()的執(zhí)行。5.1.2 TeX括號在TeX中，左雙引號，右雙引號"。輸入一篇篇包含雙引號的文章，你的任務(wù)是把它轉(zhuǎn)換成TeX的格式。樣例輸入："To

12、be or not to be,"quoth the Bard, "that is the question".樣例輸出：To be or not to be,"quoth the Bard, that is the question''.【分析】本題的關(guān)鍵是，如何判斷一個雙引號是“左”雙引號還是“右”雙引號。方法很簡單，使用一個標志變量即可。完整的程序如下：#include <stdio.h>int main() int c, q = 1; while(c= getchar() != EOF) if(c = '&qu

13、ot;') printf("%s", q ? "" : "''"); q = !q; else printf("%c", c); return 0;5.1.3 周期串如果一個字符串可以由某個長度為k的字符串重復(fù)多次得到，我們說該串以為周期。例如，abcabcabcabc以3為周期（注意，它也以6和12為周期）。輸入一個長度不超過80的串，輸出它的最小周期。樣例輸入：HoHoHo樣例輸出：2【分析】字符串可能會有多個周期。但因為只需求出最小的一個，可以從小到在枚舉各個周期，一旦符合條件就立即輸

14、出。下面的程序用到了一個新的語法：臨時定義變量，例如，變量i和j只定義在循環(huán)體內(nèi)，因此在循環(huán)體后無法訪問到它們。完整的程序如下：#include <stdio.h>#include <string.h>int main() char word100;scanf("%s", word);int len = strlen(word);for (int i = 1; i <= len; i+)if (len % i = 0) /確定word的長度len為i的整數(shù)倍int ok = 1;for (int j = i; j < len; j+)if

15、 (wordj != wordj % i)/判斷是否與word0wordi-1相等ok = 0; break;if (ok) printf("%dn", i);break; return 0;5.2 高精度運算在介紹C語言時，已經(jīng)看到了很多整數(shù)溢出的情形。如果運算結(jié)果真的很大，需要用所謂的高精度算法，用數(shù)組來儲存整數(shù)，模擬手算的方法進行四則運算。5.2.1 小學(xué)生算術(shù)在學(xué)習(xí)加法是時，發(fā)現(xiàn)“進位”特別容易出錯。你的任務(wù)是計算兩個整數(shù)在相加時需要多少次進位。你編制的程序應(yīng)當(dāng)可以連續(xù)處理多組數(shù)據(jù)，直到讀到兩個0（這是輸入結(jié)束標記）。假設(shè)輸入的整數(shù)都不超過9個數(shù)字。樣例輸入：123

16、 456555 555 123 594 0 0樣例輸出：0 3 1【分析】注意int的上限約是2000000000，可以保存所有9位整數(shù)，因此可以用整數(shù)來保存輸入每次把a和b分別模10就能獲取它們的個位數(shù)。完整的程序如下：#include <stdio.h>int main() int a, b; while (scanf("%d%d",&a,&b) = 2) if (!a && !b) return; /* 輸入0和0結(jié)束 */ int c = 0, ans = 0; /* c儲存進位的標志，ans儲存進位的次數(shù) */ for

17、(int i = 9; i >= 0; i-) c = (a%10 + b%10 + c) > 9 ? 1 : 0; ans += c; a /= 10; b /= 10; printf(“%dn”, ans); return 0;5.2.2 階乘的精確值輸入不超過1000的正整數(shù)n，輸出n!=1×2×3××n的精確結(jié)果。樣例輸入：30樣例輸出：265252859812191058636308480000000【分析】為了保存結(jié)果，先分析1000!大約等于4×102567，因此可以用一個3000個元素的數(shù)組f保存。讓f0保存結(jié)果的個

18、位，f1是十位，f2是百位，,則每次只需要模似手算即可完成n!。在輸出時需要忽略前導(dǎo)0。注意，如果結(jié)果本身就是0，那么忽略所有前導(dǎo)0后將什么都不輸出。所幸n!肯定不等于0，因本題可以忽略這個細節(jié)。01234567i=110000000i=220000000i=360000000i=442000000i=502100000i=602700000i=704050000完整的程序如下：#include <stdio.h>#include <string.h>const int maxn = 3000;int fmaxn;int main() int i, j, n; scan

19、f("%d", &n); memset(f, 0, sizeof(f); f0 = 1; for(i = 2; i <= n; i+) /* 乘以i */ int c = 0; for(j = 0; j < maxn; j+) int s = fj * i + c;/c表示進位 fj = s % 10; c = s / 10; for(j = maxn-1; j >= 0; j-) if(fj) break; /* 忽略前導(dǎo)0 */ for(i = j; i >= 0; i-) printf("%d", fi); prin

20、tf("n"); return 0;5.2.3 高精度運算類bign雖然前面的代碼能實現(xiàn)高精度運算，但是代碼不能重用。如果寫一個“高精度函數(shù)庫”，實現(xiàn)“代碼模板”，這樣現(xiàn)成、好用的代碼在測試中更加方便。所以，設(shè)計一個結(jié)構(gòu)體bign來儲存高精度非負整數(shù)：const int max = 1000;struct bign int len,smaxn; bign() memset(s, 0, sizeof(s); len = 1; ;其中，len表示位數(shù)，而s數(shù)組就是具體的各個數(shù)字。上面的結(jié)構(gòu)體中有一個函數(shù)，稱為構(gòu)造函數(shù)（Constructor）。構(gòu)造函數(shù)是C+中特有的，作用是進行

21、初始化。說明：（1）C+語言對C語言的struct進行了改造，使其也可以像class那樣支持成員函數(shù)的定義，從而使struct變成真正的抽象數(shù)據(jù)類型（ADT，Abstract Data Type）。（2）在C+語言中，如果不特別指明，struct的成員的默認訪問說明符為public，而class的成員的默認訪問說明符為private。實際上就C+語言來講，struct和class除了“默認的成員訪問說明符”這一點外，沒有任何區(qū)別。（3）C+的struct和class差別很小，其實class就是從struct發(fā)展出來的。struct定義的結(jié)構(gòu)體在C+中也是一個類，結(jié)構(gòu)體可以有class的任何東西

22、。 現(xiàn)在來重新定義賦值運算（注意，下面的函數(shù)要寫在bign結(jié)構(gòu)體定義的內(nèi)部，千萬不要寫在外面）：bign operator = (const char* num) len = strlen(num); for(int i = 0; i < len; i+) si = numlen-i-1 - '0' return *this;說明：每個類實例化一個對象后，就會有一個this指針，指向當(dāng)前實例本身。this 是由編譯器自動產(chǎn)生的，在類的成員函數(shù)中有效。this 是一個常量，不允許對其賦值。可以用x= "1234567898765432123456789"

23、給x賦值，它會也這個字符串轉(zhuǎn)化為“逆序數(shù)組+長度”的內(nèi)部表示法。為了支持x=1234的賦值方式，再定義另外一種賦值運算（定義在結(jié)構(gòu)體內(nèi)部）：bign operator = (int num) char smaxn; sprintf(s, "%d", num); *this = s; return *this; 可以用“bign x; x=100;”來聲明一個x并給它賦值，卻不能寫成“bign x=100;”。原因在于，bign x=100是初始化，而非普通的賦值操作。為了讓代碼支持“初始化”操作，需要增加兩個函數(shù)（定義在結(jié)構(gòu)體內(nèi)部）：bign(int num) *this

24、= num; bign(const char* num) *this = num; 下面需要提供一個函數(shù)把它轉(zhuǎn)化為字符串：string str() const string res = "" for(int i = 0; i < len; i+) res = (char)(si + '0') + res; if(res = "") res = "0" return res;說明：任何不會修改數(shù)據(jù)成員（即函數(shù)中的變量）的函數(shù)都應(yīng)該聲明為const 類型。如果在編寫const 成員函數(shù)時，不慎修改了數(shù)據(jù)成員，或者調(diào)用

25、了其它非const 成員函數(shù)，編譯器將指出錯誤，這無疑會提高程序的健壯性。接下來，重新定義<<和>>運算符，讓輸入輸入出流直接支持bign結(jié)構(gòu)體（這兩個孫函數(shù)要定義在結(jié)構(gòu)體bign的外邊，不在寫在里面）：istream& operator >> (istream &in, bign& x) string s; in >> s; x = s.c_str(); return in;ostream& operator << (ostream &out, const bign& x) out &

26、lt;< x.str(); return out;5.2.4 重載bign的常用運算符加法寫成函數(shù)（定義在結(jié)構(gòu)體內(nèi)部）：bign operator + (const bign& b) const bign c; c.len = 0; for(int i = 0, g = 0; g | i < max(len, b.len); i+) int x = g; if(i < len) x += si; if(i < b.len) x += b.si; c.sc.len+ = x % 10; g = x / 10; return c;兩個數(shù)中只要任何一個數(shù)還有數(shù)字，加法

27、就要繼續(xù)，即使兩個數(shù)都加完了，也不要忘記處理進位。注意，上面的算法并沒有假設(shè)s數(shù)組中“當(dāng)前沒有用到的數(shù)字都是0”。如果事先已經(jīng)清零，就可以把循環(huán)體的前3行簡化為int x=si+b.si=g。甚至可以直接把循環(huán)次數(shù)設(shè)置max(len,b.len)+1，然后檢查最終結(jié)果是否有前導(dǎo)零。如果有，則把len減1。為了讓使用簡單，可以重新定義+=運算符（定義在結(jié)構(gòu)體內(nèi)部）：bign operator += (const bign& b) *this = *this + b; return *this;接下來，實現(xiàn)“比較”操作（定義在結(jié)構(gòu)體內(nèi)部）：bool operator < (const

28、 bign& b) const if(len != b.len) return len < b.len; for(int i = len-1; i >= 0; i-) if(si != b.si) return si < b.si; return false;一開始就比較兩個bign的位數(shù)，如果不相等則直接返回，否則比較兩個數(shù)組的逆序的字典序。注意，這樣做的前提是兩個數(shù)都沒有前導(dǎo)零，如果不注意的話，很可能出現(xiàn)“運算結(jié)果都沒有問題，但一比較就錯”的情況。用“小于（<）”符號，就可用它來定義其他所有比較運算符：bool operator > (const bi

29、gn& b) const return b < *this;bool operator <= (const bign& b) return !(b > *this);bool operator >= (const bign& b) const return !(*this< b );bool operator != (const bign& b) return b < *this) | *this < b;bool operator = (const bign& b) return !(b < *this)

30、 && !(*this < b);后面如果要用到高精度運算的題目中，將直接使用bign類中的所有運算。5.3 排序與檢索數(shù)據(jù)處理是計算機的強項，包括排序、檢索和統(tǒng)計等。下面舉一些例子，展示排序和檢索引的技巧。5.3.1 6174問題假設(shè)你有一個各位數(shù)字互不相同的四位數(shù)，把所有數(shù)字從到小排序后得到a，從小到大排序后得到b，然后a-b替換原來的數(shù)，并且繼續(xù)操作。例如，從1234出發(fā)，依次可以得到4321-1234=3087、8730-378=8352、8532-2358=6174。有趣的是，7641-1467=6174，回到了它自己。輸入一個n位數(shù)，輸出操作序列，直到出現(xiàn)循環(huán)

31、（即新得到的數(shù)曾經(jīng)得到過）。輸入保證在循環(huán)之前最多只會產(chǎn)生1000個整數(shù)。樣例輸入：1234樣例輸出：1234->3087->8352->6174->6174【分析】要解決本問題需要解決下面兩個問題：（1）需要把各個數(shù)字排序，因此首先需要把各個數(shù)字提取出來。下面的函數(shù)使用“冒泡排序”的方法，可以方便地把一個數(shù)組按照從大到小的或者從小到大的順序排序：int get_next(int x) int a, b, n; char s10; /轉(zhuǎn)換成字符串 sprintf(s, "%d", x); n = strlen(s); /冒泡排序 for(int i

32、= 0; i < n; i+) for(int j = i+1; j < n; j+) if(si > sj) char t = si; si = sj; sj = t; sscanf(s, "%d", &b);/將s以%d形式存入b中 /字符串反轉(zhuǎn) for(int i = 0; i < n/2; i+) char t = si; si = sn-1-i; sn-1-i = t; sscanf(s, "%d", &a); return a - b;（2）逐個生成各個數(shù)，并判斷是否曾經(jīng)生成過。常用的方法是用數(shù)組：in

33、t num2000, count;int main() scanf("%d", &num0); printf("%d", num0); count = 1; for(;) /生成并輸出下一個數(shù) numcount = get_next(numcount-1); printf(" -> %d", numcount); /在數(shù)組num中尋找新生成的數(shù) int found = 0; for(int i = 0; i < count; i+) if(numi = numcount) found = 1; break; /如果

34、找到，則退出循環(huán) if(found) break; count+; printf("n"); return 0;5.3.2 字母重排輸入一個字典（用*結(jié)尾），然后再輸入若于單詞。每輸入一個單詞w，你需要在字典中找出所有可以用w的字母重排后得到的單詞，并按照字典序從小到大的順序在一行中輸出（如果不存在，輸出:()。輸入單詞之間用空格或空行隔開，且所有輸入單詞都不超過6個小寫字母組成。注意，字典中的單詞不一定按字典序排列。樣例輸入：tarp given score refused only trap work earn course pepper part*resco nfud

35、re aptr sett oresuc樣例輸出：scorerefundpart tarp trap:(course【分析】首先需要把字典讀入并保存下來?？捎萌缦路椒ǎ海?）每讀入一個單詞，就和字典中的所有單詞比較，看看是否可以通過重排得到。（2）把可以重排得到的單詞放在一個數(shù)組中。（3）把這個數(shù)組排序后輸出。下面簡化上面的3個步驟如下：（1）判斷兩個單詞可以通過重排得到的方法是：把各個字母排序，然后直接比較即可。所以可以在讀入時就把每個單詞按照字母排好序，就不必每次重排。（2）不必把重排的單詞保存下來再排序，只要在讀入字典之后把所有單詞排序，就可以每遇到一個滿足條件的單詞就立刻輸出。完整程序如

36、下：#include <stdio.h>#include <stdlib.h>#include <string.h>int n;char word200010, sorted200010;/字符比較函數(shù)int cmp_char(const void* _a, const void* _b) char* a = (char*)_a; char* b = (char*)_b; return *a - *b;/字符串比較函數(shù)int cmp_string(const void* _a, const void* _b) char* a = (char*)_a; cha

37、r* b = (char*)_b; return strcmp(a, b);int main() n = 0; for(;) scanf("%s", wordn); if(wordn0 = '*') break; /遇到結(jié)束標志就終止循環(huán) n+; qsort(word, n, sizeof(word0), cmp_string); /給所有單詞排序 for(int i = 0; i < n; i+) strcpy(sortedi, wordi); /給每個單詞排序 qsort(sortedi, strlen(sortedi), sizeof(char)

38、, cmp_char); char s10; while(scanf("%s", s) = 1) /持續(xù)讀取到文件結(jié)尾 qsort(s, strlen(s), sizeof(char), cmp_char); /給輸入單詞排序 int found = 0; for(int i = 0; i < n; i+) if(strcmp(sortedi, s) = 0) found = 1; printf("%s ", wordi); /輸出原始單詞，而不排序后的 if(!found) printf(":("); printf("

39、;n"); return 0;說明：（1）不管把字符串中的各個字符排序還是把所有字符串排序，上面的代碼都用到了stdlib.h中的排序函數(shù)qsort。使用庫函數(shù)排序的代碼量并不比用冒泡排序法小，但速度卻快很多。（2）下面來說明一下qsort函數(shù)的使用。在實際應(yīng)用中更多的采用qsort函數(shù)進行排序。qsort函數(shù)是C/C+語言的庫函數(shù)（包含在頭文件stdlib.h中），采用快速排序算法實現(xiàn)，其效率比插入排序、冒泡排序和簡單選擇排序的效率都高得多。qsort函數(shù)的原型為：void qsort(void *base,int num,in width,int (*compare)(const

40、 void *elem1,const void *elem2)它有四個參數(shù)，其含義為：base：參與排序的元素存儲空間的首地址，它是空類型指針。num：參與排序的元素個數(shù)。width：參與排序的每個元素所占字節(jié)數(shù)（寬度）。第四個參數(shù)為一個函數(shù)指針，這個函數(shù)需要用戶自己定義，用來實現(xiàn)排序時對元素之間的大小關(guān)系進行比較。compare函數(shù)的兩個參數(shù)都是空類型指針，在實現(xiàn)時必須強制轉(zhuǎn)換成參與排序的元素類型的指針。如果是按從小到大的順序（即升序）排序，compare函數(shù)的返回值的含義為：第1個參數(shù)所指向的元素小于第2個參數(shù)所指向的元素，則返回值<0。第1個參數(shù)所指向的元素等于第2個參數(shù)所指向的元

41、素，則返回值=0。第1個參數(shù)所指向的元素大于第2個參數(shù)所指向的元素，則返回值>0。如果需要按從大到小的順序（降序）排序，compare函數(shù)的返回值具有相反的含義：當(dāng)?shù)?個元素大于第2個元素，則返回值<0；當(dāng)?shù)?個元素小于第2個元素，則返回值<0。以下分別介紹對于不同數(shù)據(jù)類型、不同排序要求時qsort函數(shù)的使用方法。對基本數(shù)據(jù)類型的數(shù)組排序如果數(shù)組元素是int型，且按從小到大的順序（升序）排序，compare函數(shù)可以編寫成：int compare(const void *elem1,const void *elem2) return *(int *)elem1-*(int *)

42、elem2;這樣如果在qsort函數(shù)實現(xiàn)排序的過程中調(diào)用compare函數(shù)比較67和89這兩個元素，compare函數(shù)的返回值為-22，即<0。如果需要按從大到小的順序（降序）排序，只需把compare函數(shù)中的語句改寫成：return *(int *)elem2-*(int *)elem1;即可。這樣調(diào)用compare函數(shù)比較67和89這兩個元素，compare函數(shù)的返回值為22，即>0。另外，compare函數(shù)也可以編寫成（按從小到大順序排序）：int compare(const void *elem1,const void *elem2) return (*(int *)ele

43、m1<*(int *)elem2)?-1:(*(int *)elem1>*(int *)elem2)?1:0;compare函數(shù)定義好后，就可以用下面的代碼段實現(xiàn)一個整型數(shù)組的排序：int num100; /輸入100個數(shù)組元素的值qsort(num,100,sizeof(num0),compare); /調(diào)用qsort函數(shù)進行排序?qū)har、double等其他基本數(shù)據(jù)類型數(shù)組的排序，只需把上述compare函數(shù)代碼中的int型指針（int *）改成其他類型指針即可。對結(jié)構(gòu)體的一級排序所謂結(jié)構(gòu)體，就是把不同類型的數(shù)據(jù)組合成一個整體，比如一個學(xué)生的數(shù)據(jù)包括：姓名、年齡、分數(shù)。則可按如

44、下方式聲明一個student結(jié)構(gòu)體：struct student char name20; /姓名 int age; /年齡 double score; /分數(shù);聲明好student結(jié)構(gòu)體以后，就可以像用int、char等基本數(shù)據(jù)類型一樣去定義變量、數(shù)組了，如下面的例子：struct student s1; /定義結(jié)構(gòu)體變量struct student s10; /定義結(jié)構(gòu)體數(shù)組struct student ps=&s1; /定義結(jié)構(gòu)體指針，指向s1其中s1為student類型的變量，它包含了3個成員：name、age和score；s為student類型的數(shù)組，它有10個元素，每個元素

45、都包含了3個成員；ps為student類型的指針變量，指向s1。要引用結(jié)構(gòu)體變量中的成員，需要使用成員運算符“.”，如下面的例子。s1.age=20; /給s1的age成員變量賦值為20strcpy(,"WangLin"); /將字符串"WangLin"拷貝到s1的name成員如果通過結(jié)構(gòu)體指針變量引用它所指向的結(jié)構(gòu)體變量的成員，需要使用指向運算符“->”，如下面的例子：ps->age=20; /相當(dāng)于s1=20;所謂對結(jié)構(gòu)體一級排序，是指對結(jié)構(gòu)體中的某一個成員的大小關(guān)系排序。例如對上述的student數(shù)組s中的元素以其age成

46、員的大小關(guān)系按從大到小的順序（升序）排序。Compare函數(shù)可定義成：int compare(const void *elem1,const void *elem2) return (student *)elem1)->age-(student *)elem2)->ag;qsost函數(shù)調(diào)用形式為：qsort(s,10,sizeof(s0),compare); 對結(jié)構(gòu)體二級排序所謂對構(gòu)體二級排序，含義是先按某個成員的大小關(guān)系排序，如果成員大小相等，再按另一個成員的大小關(guān)系進行排序。比如上面的student數(shù)組s，可以先按age成員從小到大的順序排序，如果age成員大小相等，再按sco

47、re成員從小到大的順序排序。int compare(const void *elem1,const void *elem2) student *p1=(student *)elem1; student *p2=(student *)elem2; if(p1->age!=p2->age) return p1->age-p2->age; else return p1->score-p2->score;也就是說，如是兩個元素s1和s2的age成員不等，compare返回的是它們age成員的大小關(guān)系；如果它們的age成員大小相等，返回的是它們的score成員的大小關(guān)

48、系。qsort函數(shù)調(diào)用形式為：qsort(s,10,sizeof(s0),compare); 補充1：strcmp()函數(shù)介紹原型：extern int strcmp(const char *s1,const char * s2);所在頭文件：string.h功能：比較字符串s1和s2。一般形式：strcmp(字符串1，字符串2)說明：當(dāng)s1<s2時，返回值<0當(dāng)s1=s2時，返回值=0當(dāng)s1>s2時，返回值>0即：兩個字符串自左向右逐個字符相比（按ASCII值大小相比較），直到出現(xiàn)不同的字符或遇'0'為止。如："A"<&quo

49、t;B" "a">"A" "computer">"compare"特別注意：strcmp(const char *s1,const char * s2)這里面只能比較字符串，不能比較數(shù)字等其他形式的參數(shù)。補充2：strcpy()函數(shù)介紹原型聲明：extern char *strcpy(char dest,const char *src);頭文件：#include <string.h>功能：把從src地址開始且含有NULL結(jié)束符的字符串復(fù)制到以dest開始的地址空間說明：src和de

50、st所指內(nèi)存區(qū)域不可以重疊且dest必須有足夠的空間來容納src的字符串。返回指向dest的指針。5.4 數(shù) 學(xué) 基 礎(chǔ)數(shù)學(xué)是算法的基石，在入門時要重視數(shù)學(xué)，逐步積累各種技巧。5.4.1 Cantor的數(shù)表如下列數(shù)，第一項是1/1，第二項是1/2，第三項是2/1，第四項是3/1，第五項是2/2,。輸入n，輸出第n項。1/1 1/2 1/3 1/4 1/52/1 2/2 2/3 2/4 3/1 3/2 3/34/1 4/25/1 樣例輸入： 314712345樣例輸出：2/12/41/459/994【分析】數(shù)表提示需按照斜線分類。第1條斜線有1個數(shù)，第2條斜線有2個數(shù)，第3條斜線有3個數(shù)，第i條

51、斜線有i個數(shù)。所以，前i條斜線一共有S(k)=1+2+3+k=k(k+1)/2個數(shù)。第n項在哪條斜線上呢？只要找到一個最小的正整數(shù)k，使得nS(k)，那么n就是第k條斜線上的倒數(shù)第S(k)-n+1個元素（最后一個元素是倒數(shù)第1個元素，而不是倒數(shù)第0個元素）。所以，第k條斜線的倒數(shù)第i個元素是i/(k+1-i)。完整程序如下：#include <stdio.h>int main() int n; while(scanf("%d", &n) = 1) int k = 1, s = 0; for(;) s += k; if(s >= n) /所求項是第k

52、條對角線的倒數(shù)第s-n+1個元素 printf("%d/%dn", s-n+1, k-s+n); break; k+; return 0;下面利用代數(shù)知識，還可以簡化：注意到總是正數(shù)，因此，換句話說，可以直接求出。為了避免浮點數(shù)，下面的程序用到了一點小技巧：#include <stdio.h>#include <math.h>int main() int n; while(scanf("%d", &n) = 1) int k = (int)floor(sqrt(8.0*n+1)-1)/2-1e-9)+1; int s =

53、k*(k+1)/2; printf("%d/%dn", s-n+1, k-s+n); return 0;思路二：#include<iostream>using namespace std;int main()int n;while(cin>>n)for(int k=1;k+)/確定最小的kif(k*(k+1)/2>=n)break;int x=k*(k+1)/2-n;if(k%2=0)/k為偶數(shù)時cout<<k-x<<"/"<<1+x<<endl;else/k為奇數(shù)時cout&

54、lt;<1+x<<"/"<<k-x<<endl;return 0;5.4.2 因子和階乘輸入正整數(shù)n（2n100），把階乘n!=1×2×3××n分解成素因子相乘的形式，從小到大輸出各個素數(shù)（2、3、5、）的指數(shù)。例如825=3×52×11應(yīng)表示成(0,1,2,0,1)，表示分別有0、1、2、0、1個2、3、5、7、11。你的程序應(yīng)忽略比最大素因子更大的素數(shù)（否則末尾會有無窮多個0）。樣例輸入： 553樣例輸出：5!=3 1 153!=49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1【分析】因為am·an=am+n,只需把所有素因子對應(yīng)的指數(shù)累加起來。注意到n100，這些素因子不會超過100，輸出時忽略到最后的0即可。完整程序如下：#include <stdio.h>#include <string.h>/