《主题sorting（排序）》由会员分享，可在线阅读，更多相关《主题sorting（排序）（30页珍藏版）》请在金锄头文库上搜索。
1、1,主題: Sorting (排序),解題技巧什麼是 sorting？基本的 sorting 方法如何使用 qsort例題講解: A.299歷年題目,2,什麼是 sorting？,將給定的資料按照特定的順序排列好由小到大由大到小例：1, 7, 9, 5, 3由小到大：1, 3, 5, 7, 9由大到小：9, 7, 5, 3, 1,3,什麼是 sorting？,只有數字能比大小嗎？John Bob小明 小華只要能定義大小關係，就可以 sortJ 在 B 之後 John Bob“明”筆畫比“華”少 小明 d) return (1); else if (c = d) return (0); else
2、 return (-1);qsort(tbl, sizeof(tbl) / sizeof(tbl0), sizeof(tbl0), comp_func);,陣列指標,要 sort 的個數,每個要 sort 的 element 的大小,compare function,16,Example: qsort,char tbl10 = “Hello”, “OK”, “Test”, “BBS”, “Book”, “C”;int comp_func( const void *a, const void *b) char *c, *d; c = (char *)(a); d = (char *)(b); r
3、eturn (strcmp(c, d);qsort(tbl, sizeof(tbl) / sizeof(tbl0), sizeof(tbl0), comp_func);,17,Example: qsort,#include int num5 = 1, 7, 9, 5, 3 ;int comp_func(const void *a, const void *b)int c, d;c = *(int *)(a); d = *(int *)(b); return ( c d );int main(void)qsort(num, sizeof(num)/sizeof(num0), sizeof(num
4、0), comp_func);/* qsort(num, 5, sizeof(num0), comp_func); */return 0;,18,qsort and bubble sort,bubble sort執行速度較慢程式好寫好記，不容易忘qsort執行速度較快需要自己寫 compare function不熟的話容易忘記格式,19,例題講解: A.299(http:/acm.uva.es/p/v2/299.html),有一列火車總共有 L 節車廂，每節車廂都有個編號(從 1 L)。現在車廂的順序亂掉了，而站長希望能把車廂的順序由 1 到 L 排好。唯一能做的方法是把相鄰的兩個車廂順序對調
5、，請問，最少需要做幾次的車廂順序對調工作，而能讓車廂的順序由 1 到 L 排好。L 最大到 50,20,Sample input/output,Sample input:331 3 244 3 2 122 1Sample output:Optimal train swapping takes 1 swaps.Optimal train swapping takes 6 swaps.Optimal train swapping takes 1 swaps.,總共會有幾組 test case,車廂的長度,車廂的編號,21,讀進 input 需要的資料結構,int case_num總共有幾個 tes
6、t caseint L車廂的長度int num50每個車廂的編號因為 L 最大只有50，所以開一個長度50的整數陣列就夠了,22,分析,1 3 2noswap ( 1, 3) 1 3 2 swap ( 2, 3) 1 2 3noswap ( 1, 2) 1 2 34 3 2 1swap ( 4, 3) 3 4 2 1swap ( 4, 2) 3 2 4 1swap ( 4, 1) 3 2 1 4swap ( 3, 2) 2 3 1 4swap ( 3, 1) 2 1 3 4swap ( 2, 1) 1 2 3 4,23,解法,換火車車廂的順序跟 bubble sort 的順序是一樣的照著 bu
7、bble sort 的方法去做，每當 swap 發生的時候就在總次數的地方加一，最後得到的數字就是最少需要換的次數,24,Program structure,read_case_num();for ( i = 0; i case_num; i+)read_train_length();read_train_number();bubble_sort();/ 每次 swap 時把 counter 往上加output_optimal_solution();,25,Program,#include #define swap( x, y) ( t) = ( x) , ( x) = ( y), ( y)
8、= ( t)int main(void)int i, j, k, t, L, case_num, counter, num50;freopen(“data.in”, “r”, stdin); /若是要送到acm online judge，則這行要拿掉scanf(“%d”, ,26,例題講解: H.88.4http:/www.cc.nccu.edu.tw/info_race88/Q.pdf,了解題意input 格式、範圍，output 格式、要求分析解法，需要什麼資料結構架構程式，上機實作,27,漏洞與陷阱,漏洞題目寫著“金、銀、銅牌的分配約為 1: 2: 3”，那要是人數不是 6 的倍數怎麼辦
9、？要是有同分的人落在金、銀牌之間的分界處，該怎麼解決？Output 格式，欄位有多寬？不然該怎麼對齊？輸出 3 中，如果有得獎牌數一樣的國家，該 output 一個或是全部 output？有順序分別嗎？陷阱人名有可能中間有空白字元分開，讀 input 時要特別小心,28,解法,依照得分高低排序只要能正確的讀入 input，排序，再 output 就好計算各種獎牌數量加個 counter 計算一下獎牌數量找出得獎牌最多的國家用陣列計算每個國家得獎的數量計算平均數、最高分、最低分和全距簡單的數學式,29,解題重點,如何正確的讀入 input C 有許多內建的 string function 可以利
10、用，請期待明天的教學,30,歷年題目,練習題A.10008 Whats Cryptanalysishttp:/acm.uva.es/p/v100/10008.htmlA.10057 A Mid-summer Nights Dreamhttp:/acm.uva.es/p/v100/10057.htmlA.612 DNA Sortinghttp:/acm.uva.es/p/v6/612.html挑戰題A.10125 Sumsetshttp:/acm.uva.es/p/v101/10125.html其他歷年題目H.88.4 http:/www.cc.nccu.edu.tw/info_race88/Q.pdfH.89.1 對對碰http:/www.cc.nccu.edu.tw/info_race89/doc/final_program.doc,
