原文鏈接：

http://www.wutianqi.com/?p=1181

大家在學習C++編程時，一般在輸入方面都是使用的cin.
而cin是使用空白（空格，制表符和換行符）來定字符串的界的。
這就導致了對于帶有空格的字符串，比如”I Love www.CppLeyuan.com”
只能讀入”I”，后面的都無法讀入。
這時怎么辦？

 一.對于字符數組：
方法一：getline()
讀入整行數據，它使用回車鍵輸入的換行符來確定輸入結尾。
調用方法: cin.getline(str, len);
第一個參數str是用來存儲輸入行的數組名稱，第二個參數len是要讀取的字符數。

方法二：get()

調用方法：cin.get(str, len);

那么兩者有何區別？
兩者都讀取一行輸入，直至換行符。
然后，getline將丟棄換行符，而get()將換行符保留在輸入序列里。
所以，再使用cin.get()輸入多行數據時，中間可以使用get()消除換行符。

因為get(str, len)和get()都是cin的類成員，所以可以合并起來寫：

(歡迎大家去我論壇學習:C++奮斗樂園：http://www.cppleyuan.com/)

二.對于string類
方法一:getline(cin, str)

這說明這里的getline不是類方法。

PS:以后如果對輸入方面還有更多了解，會繼續補充，希望大家支持，多多交流。

原創鏈接：http://www.wutianqi.com/?p=1162

上次論壇里一個會員問的。
感覺這個程序作為DFS入門是很理想的，大家應該都能看懂。
貼出來和大家分享：

 

 1#include<iostream>
 2using namespace std;
 3int a[100] = {0};
 4int n;
 5int count=0; 
 6void dfs(int k)
 7{
 8   if(k >= n)
 9   {
10      for(int i = 0;i < n;i++)
11      {
12         cout<<a[i]<<" ";
13      }
14      count++;
15      cout<<endl;
16   }     
17   else
18   {
19      for(int i = 1;i <= n;i++)
20      {
21         a[k] = i; 
22         dfs(k + 1);        
23      }       
24   }    
25}
26int main()
27{
28   while(cin>>n)
29   {
30      count=0;
31      int k = 0;
32      dfs(k);  
33      cout<<count<<endl;             
34   }    
35}

 

---

http://www.wutianqi.com/?p=1157

---

集合A的冪集是由集合A的所有子集所組成的的集合。

 

如：A={1，2，3}，則A的冪集P（A）={{1，2，3}，{1，2}，{1，3}，{1}，{2，3}，{2}，{3}，{ }}。

求一個集合的冪集就是求一個集合的所有的子集，方法有窮舉法，分治法，回溯等，這里主要介紹一下回溯法。

回溯法是設計遞歸過程的一種重要的方法，它的求解過實質上是一個先序遍歷一棵“狀態樹”的過程，只是這棵樹不是遍歷前預先建立的，而是隱含在遍歷過程中的。

冪集中的每個元素是一個集合，它或是空集，或含集合A中一個元素，或含集合A中兩個元素…… 或等于集合A。反之，從集合A 的每個元素來看，它只有兩種狀態：它或屬冪集的無素集，或不屬冪集的元素集。則求冪集p(A)的元素的過程可看成是依次對集合A中元素進行“取”或“舍”的過程，并且可以用一棵二叉樹來表示過程中冪集元素的狀態變化過程，樹中的根結點表示冪集元素的初始狀態（空集）；葉子結點表示它的終結狀態，而第i層的分支結點，則表示已對集合A中前i-1個元素進行了取舍處理的當前狀態（左分支表示取，右分支表示舍 ）。因此求冪集元素的過程即為先序遍歷這棵狀態樹的過程。

具體算法如下：

C/C++描述：

 1#include <iostream>
 2#include <cstring>
 3#include <ctype.h>
 4#include <stdlib.h>
 5#include <string>
 6using namespace std;
 7 
 8char a[100];
 9char b[100];
10 
11void GetPowerSet(int i, char a[])
12{
13    char x;
14    int k;
15    int len = strlen(a);
16    if(i >= len)
17    {
18        if(b[0])
19            cout << b <<  endl;
20        else
21            cout << "XX" << endl;  // 表示空集
22    }
23    else
24    {
25        x = a[i];
26        k = strlen(b);
27        b[k] = x;
28        GetPowerSet(i+1, a);
29        b[k] = 0;
30        GetPowerSet(i+1, a);
31    }
32}
33 
34 
35int main()
36{
37    while(scanf("%s", a) != EOF)
38    {
39        printf("%s的冪集是:\n", a);
40        printf("------------\n");
41        GetPowerSet(0, a);
42        printf("------------\n");
43    }
44}

原文鏈接：
http://www.wutianqi.com/?p=1028

          回憶起以前我看這本書，聯系自己學編程這一年多，感觸頗多。記得這本書剛出來時，我就在中關村圖書大廈買了一本。至今已經快一年了。故事情節依稀記得一點。

          里面講到了BOSS 絕的奮斗史，讀大學時和寢室一伙人到處折騰，給別人裝機子，去小公司找工作，以及后來的作為招聘人員去自己學校招員工，私下接外掛破解，和女友的坎坷經歷直到最后的分手。

          絕影的人生并不好走，雖然大學還未畢業就找到工作了，但是可以看出他的艱辛，經常熬夜趕項目；節假日不能陪家人，結果女友也要求分手了。

          我不知道該說什么好，別人都說嫁人要嫁程序員，程序員只關心電腦，不會在外面過那種花花綠綠的生活，這是褒義，還是貶義？也許只有說這話的人心里才清楚。

          我大學是讀自動化的，連我都不知道我為何要報自動化，我只知道，高考沒考到自己預想的分數，考了一個半吊子的分數：568分，而一本分數線是548.就這么高不高，低不低的。連我老爸當年讀的中南財經政法大學都讀不了，于是我也懶得管了，直接讓我父母報，結果第一志愿是北京化工大學的機械工程及其自動化，第二志愿是北京化工大學的自動化。最后第一志愿沒錄取，于是我到了北化的自動化系。雖然讀了兩年大學，我還不知道我這個專業到底是干啥的，只知道這個專業是一個萬金油，啥都行~~~

           大一剛進校，因為高考完在家天天玩網游，開學了還沒回過神來，別人都忙于互相認識，一起游覽北京的一些旅游景點，而我卻忙于在網吧與寢室兩地顛簸。那時剛開學，班級和學校有許多的活動，我一個都沒參加，記得開學就有學校和院的各個部門招人手，我那時沒認識到德育分的重要性，也沒有刻意去培養自己的結交能力(不過我的朋友還是非常多的~~在學校，許多人都和我很熟悉，因為我個人性格是比較活潑開朗的，且喜歡開玩笑，所以都比較隨和。)，但學校又要求每人都得報2項，所以其中一項我沒去，另外一項別人打電話過來了，我也說沒時間~~~（是不是很拽？）其實也不是不給他們面子，只是在我眼中，我不喜歡這些權勢及口頭上的較量，靠嘴皮子進去，一點用都沒，而且在我看來，這些東西都是無聊至極的，一群把自己當成官一樣來看待的，讓我感覺很不舒服。我喜歡那種靠自己真實實力較量的生活。并且在我看來，等工作了這些權勢競爭的生活多的是，在大學去浪費時間花在這上面太不值得了。就這么渾渾噩噩的一個學期快過完了，臨近寒假，發現別人雖然分一部分心思去弄學校各個部門的活，但是也確實培養了他們的個人能力，而我呢？除了會去網吧，還是去網吧。雖然那時成績不差，在班級30人中還能排在第10名。但是自己缺乏了其他獨特的能力。因為我接觸計算機很早，是從小學5年級開始的，所以我想到了從計算機這方面發展，剛開始對編程一竅不通，買了基本PS,FLASH,DW的書看，結果自己就是在美術細胞上太過于匱乏，始終弄不好，就這樣折騰了3個多月，最終放棄了，那時也知道了C語言，且知道下學期要學C語言，所以就提前自學了。我的編程生涯也就是從這個時候開始的（起步很晚~~）。

           剛開始學C語言，我就被吸引了，作為男生，我相信好多人都很YM那些開發軟件的人，我也不例外，而接觸了C語言，我才知道，這就是可以開發出軟件的東東，于是，我埋頭苦學…汗，其實也算不上苦學，就是把自己的課程都丟了，天天只看C語言的書，因為我不是計算機專業的，沒人教我，也沒人給我經驗，我就只能靠自己，計算機編程這方面的書都很貴的，還好有父母的經濟支持，這樣算一算，我10個月在買書上就花了2000元。我到現在都不知道怎么花的，反正牛人的書我都買了，還訂了好多雜志。記得看了譚老的《C語言程序》，《C Primer Plus》, 《The C Programming Language》 《C陷阱與缺陷》 《C專家編程》等等~~~太多了，我經常沒去上課，一個人抱著書和電腦去圖書館學。結果自己專業沒顧著，大二下學期還弄了個年級300人，倒數10幾名~~

           大二上學期我報了等級考試的三級數據庫，也順利的一次通過。呵呵，現在想來，也沒啥高興的，畢竟那些都是虛的，只需要靠2本書死記就過的，沒有一點技術含量，不值得高興。到了現在，數據庫的一些知識也快忘光了。

           大二上學期的暑假，我開始學習C++了。那時學了一段時間，寂寞了，于是建了幾個QQ群，在網上召集了一批C++愛好者一起交流，也就是那個時候，有了創辦一個論壇讓大家一起交流學習的想法。也就是在大二下學期開學后，隨著群的人越來越多，許多人也提議弄一個專門學習交流的地方，于是我買了空間和域名，辦了一個論壇。因為我覺得人生就要奮斗，我們學習編程，何嘗不是在為以后而奮斗，所以我給群，以及論壇取名叫C++奮斗樂園。域名我也選擇了cppleyuan。

           最開始接觸ACM不知道是在什么時候，應該實在大一下學期或大二上學期吧。那時就覺得這挺有趣的，但是也沒買書學習算法，就這么直接找上了POJ，經常把題目看懂就花了1個小時，然后做不出來，再分析別人代碼又是幾個小時~~~汗…后來覺得這東西不是我這種人弄的，就放棄了。不過還好，只是暫時放棄，在大二下學期開學后1個月，也就是2010年4月份左右吧。我又開始搞ACM了，因為學習C和C++也有一段時間了，對于編程也有了一定的認識，不再是那個初入編程大門，懵懵懂懂亂學的人了，我買了劉如佳老師的《算法學習經典入門》，《算法藝術與信息學競賽》，吳文虎老師的《世界大學生程序設計競賽》以及算法的圣經—-《算法導論》。就這么開始一個人在算法的海洋里探索了。也就是這個時候，因為自己對這方面有了解，并且覺得論壇不能只搞C++方面，所以我把論壇一部分分給了算法。畢竟算法是程序的靈魂。但是POJ對于我這個剛起步的小菜來說還是難了些。所以我開始轉向HDOJ了，7月10號注冊的。今天是8月17號，已經刷了210道水題了。我感覺，每AC一道題目，就感覺自己快樂了一分。也許這就是算法的魅力把，也可能這就是男人喜歡對事物的絕對掌控，感覺自己學懂了這個算法，就感覺自己多了一項能力。

           假期我給論壇弄了C/C++小項目和ACM刷題活動。當時我還到處找資料，花了一下午為C/C++小項目的第一個寫了一個詳細的流程圖，結果到最后無人問津，只有個別人做了，wujing的就做的很好，贊一個。不過還好，ACM刷題活動倒是很受歡迎，每天都有一批人和我一起刷，包括MiYu,大帥，蘿莉，timest,ac-quest等等。當然，amb教主我就不多說了，我只能YM。小白就是專門和我競爭的家伙。。。最近被他趕超了10題。郁悶。不過假期確實還是很開心的。畢竟結交了一群志同道合的朋友。

          現在假期也快結束了，8月20號返校，還得搬校區。

         看的書很多，想的也很多。喜歡思考編程，思考人生哲理。平時除了編程的書，我就最喜歡看自然科學和人生哲理了，《當下的力量》，《遇見心想事成的自己》，《秘密》這些書都很好，教會了我很多道理。感覺這些書就和算法一樣，講的都是內涵。人生就像編程，編的是人生，讓人生合理，規劃好人生，人生才能成功。

           最后，我想感謝C++奮斗樂園的各位斑竹，感謝假期陪我刷題的哥們，感謝支持我的論壇會員們。Orz

         以上算是發泄自己的情感，也算是傾述自己的經歷，或算是總結自己的經驗。不求能給大家什么幫助，只求大家能一起多交流點自己的經驗，互相借鑒，互相學習。
                                                                                                                                                                                                
                                                                                                                                                                          TankyWoo    
                                                                                                                                                                    2010年8月7號
我的博客：http://www.wutianqi.com/ 希望大家多多交流。

（原創鏈接：http://www.wutianqi.com/?p=264）
思想：對于不超過n的每個非負整數P，刪除2*P, 3*P…，當處理

完所有數之后，還沒有被刪除的就是素數。

若用vis[i]==1表示已被刪除，則代碼如下：
—————————————————–
代碼一：

1memset(vis, 0, sizeof(vis));
2for(int i = 2; i <= 100; i++)
3    for(int j = i*2; j <= 100; j += i)
4        vis[j] = 1;

上面的代碼效率已經很高了。
但還可以繼續優化。
看一個改進的代碼：
——————————————————
代碼二：

 1int m = sqrt(double(n+0.5));
 2 
 3for(int i = 2; i <= m; i++)
 4    if(!vis[i])
 5    {
 6        prime[c++] = i;
 7        for(int j = i*i; j <= n; j += i)
 8        {
 9            vis[j] = 1;
10        }
11    }

——————————————————
先分析代碼一：
這個代碼就是簡單的將Eratosthenes篩選法描述出來。不用多說。
分析代碼二：
考慮幾點：
1.為何從i=2~m?
因為下面的j是從i*i開始的。
2.為何j從i*i開始？
因為首先在i=2時，偶數都已經被刪除了。
其次，“對于不超過n的每個非負整數P”， P可以限定為素數，
為什么？
因為，在 i 執行到P時，P之前所有的數的倍數都已經被刪除，若P

沒有被刪除，則P一定是素數。
而P的倍數中，只需看：
(p-4)*p, (p-2)*p, p*p, p*(p+2), p*(p+4)
（因為P為素數，所以為奇數，而偶數已被刪除，不需要考慮p*(p

-1)等）（Tanky Woo的程序人生）
又因為(p-4)*p 已在 (p-4)的p倍中被刪去，故只考慮：
p*p, p*(p+2)….即可
這也是i只需要從2到m的原因。
當然，上面 p*p, p*(p+2)…的前提是偶數都已經被刪去，而代碼

二若改成 j += 2*i ,則沒有除去所有偶數，所以要想直接 加2*i

。只需在代碼二中memset()后面加：
for(int i = 4; i <= n; i++)
if(i % 2 == 0)
vis[i] = 1;
這樣，i只需從3開始，而j每次可以直接加 2*i.
------------------------------------------------------
這里用代碼二給大家一個完整的代碼：

 1//版本二
 2//Author: Tanky Woo
 3//Blog: www.wutianqi.com
 4 
 5#include <stdio.h>
 6#include <string.h>
 7#include <math.h>
 8int vis[100];
 9int prime[100];
10int c = 0;
11int n;
12int main()
13{
14    scanf("%d", &n);
15    int cnt = 1;
16 
17    memset(vis, 0, sizeof(vis));
18    int m = sqrt(double(n+0.5));
19 
20    for(int i = 2; i <= m; i++)
21        if(!vis[i])
22        {
23            prime[c++] = i;
24            for(int j = i*i; j <= n; j += i)
25            {
26                vis[j] = 1;
27                //printf("%d\n", j);
28            }
29        }
30 
31    for(int i = 2; i < n; i++)
32    {
33        if(vis[i] == 0)
34        {
35            printf("%d ", i);
36            cnt++;
37            if(cnt % 10 == 0)
38                printf("\n");
39        }
40    }
41    printf("\ncnt = %d\n", cnt);
42    return 0;
43}

完畢。

---

歡迎大家和我交流。(我的博客:http://www.wutianqi.com/)

背包之01背包、完全背包、多重背包詳解

PS：大家覺得寫得還過得去，就幫我頂博客，謝謝。

首先說下動態規劃，動態規劃這東西就和遞歸一樣，只能找局部關系，若想全部列出來，是很難的，比如漢諾塔。你可以說先把除最后一層的其他所有層都移動到2，再把最后一層移動到3，最后再把其余的從2移動到3，這是一個直觀的關系，但是想列舉出來是很難的，也許當層數n=3時還可以模擬下，再大一些就不可能了，所以，諸如遞歸，動態規劃之類的，不能細想，只能找局部關系。

1.漢諾塔圖片

（引至杭電課件:DP最關鍵的就是狀態，在DP時用到的數組時，也就是存儲的每個狀態的最優值，也就是記憶化搜索）

要了解背包，首先得清楚動態規劃：

動態規劃算法可分解成從先到后的4個步驟：

1. 描述一個最優解的結構；

2. 遞歸地定義最優解的值；

3. 以“自底向上”的方式計算最優解的值；

4. 從已計算的信息中構建出最優解的路徑。

其中步驟1~3是動態規劃求解問題的基礎。如果題目只要求最優解的值，則步驟4可以省略。

背包的基本模型就是給你一個容量為V的背包

在一定的限制條件下放進最多(最少?)價值的東西

當前狀態→ 以前狀態

看了dd大牛的《背包九講》(點擊下載)，迷糊中帶著一絲清醒，這里我也總結下01背包，完全背包，多重背包這三者的使用和區別，部分會引用dd大牛的《背包九講》，如果有錯，歡迎指出。

(www.wutianqi.com留言即可)

首先我們把三種情況放在一起來看：

01背包（ZeroOnePack）: 有N件物品和一個容量為V的背包。（每種物品均只有一件）第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

完全背包(CompletePack): 有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

多重背包(MultiplePack): 有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

比較三個題目，會發現不同點在于每種背包的數量，01背包是每種只有一件，完全背包是每種無限件，而多重背包是每種有限件。

——————————————————————————————————————————————————————————–：

01背包（ZeroOnePack）: 有N件物品和一個容量為V的背包。（每種物品均只有一件）第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

把這個過程理解下：在前i件物品放進容量v的背包時，

它有兩種情況：

第一種是第i件不放進去，這時所得價值為:f[i-1][v]

第二種是第i件放進去，這時所得價值為：f[i-1][v-c[i]]+w[i]

（第二種是什么意思？就是如果第i件放進去，那么在容量v-c[i]里就要放進前i-1件物品）

最后比較第一種與第二種所得價值的大小，哪種相對大，f[i][v]的值就是哪種。

（這是基礎，要理解！）

這里是用二位數組存儲的，可以把空間優化，用一位數組存儲。

用f[0..v]表示，f[v]表示把前i件物品放入容量為v的背包里得到的價值。把i從1~n(n件)循環后，最后f[v]表示所求最大值。

*這里f[v]就相當于二位數組的f[i][v]。那么，如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]？（重點！思考）
首先要知道，我們是通過i從1到n的循環來依次表示前i件物品存入的狀態。即：for i=1..N
現在思考如何能在是f[v]表示當前狀態是容量為v的背包所得價值，而又使f[v]和f[v-c[i]]+w[i]標簽前一狀態的價值？

逆序！

這就是關鍵！

1for i=1..N
2   for v=V..0
3        f[v]=max{f[v],f[v-c[i]]+w[i]};
4

分析上面的代碼：當內循環是逆序時，就可以保證后一個f[v]和f[v-c[i]]+w[i]是前一狀態的！
這里給大家一組測試數據：

測試數據：
10,3
3,4
4,5
5,6

這個圖表畫得很好，借此來分析：

C[v]從物品i=1開始，循環到物品3，期間，每次逆序得到容量v在前i件物品時可以得到的最大值。（請在草稿紙上自己畫一畫）

這里以一道題目來具體看看：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=2602

代碼在這里：http://www.wutianqi.com/?p=533

分析：

具體根據上面的解釋以及我給出的代碼分析。這題很基礎，看懂上面的知識應該就會做了。

——————————————————————————————————————————————————————————–

完全背包：

完全背包(CompletePack): 有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

完全背包按其思路仍然可以用一個二維數組來寫出：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

同樣可以轉換成一維數組來表示：

偽代碼如下：



for i=1..N
    for v=0..V
        f[v]=max{f[v],f[v-c[i]]+w[i]}

順序！

想必大家看出了和01背包的區別，這里的內循環是順序的，而01背包是逆序的。
現在關鍵的是考慮：為何完全背包可以這么寫？
在次我們先來回憶下，01背包逆序的原因？是為了是max中的兩項是前一狀態值，這就對了。
那么這里，我們順序寫，這里的max中的兩項當然就是當前狀態的值了，為何？
因為每種背包都是無限的。當我們把i從1到N循環時，f[v]表示容量為v在前i種背包時所得的價值，這里我們要添加的不是前一個背包，而是當前背包。所以我們要考慮的當然是當前狀態。
這里同樣給大家一道題目：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=1114

代碼：http://www.wutianqi.com/?p=535

（分析代碼也是學習算法的一種途徑，有時并不一定要看算法分析，結合題目反而更容易理解。）

——————————————————————————————————————————————————————————–

多重背包

多重背包(MultiplePack): 有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可，因為對于第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值，則有狀態轉移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

這里同樣轉換為01背包：

普通的轉換對于數量較多時，則可能會超時，可以轉換成二進制（暫時不了解，所以先不講）

對于普通的。就是多了一個中間的循環，把j=0~bag[i]，表示把第i中背包從取0件枚舉到取bag[i]件。

給出一個例題：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=2191

代碼：http://www.wutianqi.com/?p=537

因為限于個人的能力，我只能講出個大概，請大家具體還是好好看看dd大牛的《背包九講》。

暫時講完后，隨著以后更深入的了解，我會把資料繼續完善，供大家一起學習探討。(我的博客：www.wutianqi.com如果大家有問題或者資料里的內容有錯誤，可以留言給出，謝謝您的支持。)

原文下載地址：（Word版）
http://download.csdn.net/sour

個人原創，轉載請注明本文鏈接：http://www.wutianqi.com/?p=539

學校太讓人失望了，居然連POJ都上不去了，還好今天ambition在我用百練AC掉這題后送來了另外一個POJ的網址，雙喜臨門，害我興奮了半天，沒有POJ的日子痛苦啊。畢竟題目來源還得靠它。

這是曾經沒有AC掉的題目，不過在《程序設計導引及在線實踐》上看過，看書寫代碼還是沒親自做的效果好。今天給假期題目來源找題，看中了這題，再次做，強化了一些基本功。

分析幾點：

一。A~Z對應一個Hash數組

二。在每輸入一個數據時就對數據進行處理，轉換字母，去掉’-’

三。qsort的運行，具體看MSDN，這里就講一點。

    一個是二位數組的qsort用法：

1
            2
            3
            4
            5
            6
            

 int compare( const void *arg1, const void *arg2 )
            {
            return strcmp((char*)arg1, (char*)arg2 );
            }
            int arr[n][11];
            qsort(arr, n, sizeof(arr[0]), compare);

  二是qsort的幾個參數，這里一直不是記得很清楚。

1
            2
            3
            4
            5
            6
            

 void qsort(
            void *base,
            size_t num,
            size_t width,
            int (__cdecl *compare )(const void *, const void *)
            );

  注意：width: Element size in bytes

               cmp函數：如果是升序，則e1 > e2應返回1，e1 = e2 應返回0， e1 < e2 應返回-1.降序則相反。

直接發代碼了：

時間有點大，是600多MS。

看見網上還有其他方法，大家可以去看看。

題目地址：

http://124.205.79.250/JudgeOnline/problem?id=1002

1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            21
            22
            23
            24
            25
            26
            27
            28
            29
            30
            31
            32
            33
            34
            35
            36
            37
            38
            39
            40
            41
            42
            43
            44
            45
            46
            47
            48
            49
            50
            51
            52
            53
            54
            55
            56
            57
            58
            59
            60
            61
            62
            63
            64
            65
            66
            67
            68
            69
            70
            71
            72
            73
            74
            

 // POJ 487-3279
            // Author: Tanky Woo
            #include <iostream>
            using namespace std;
             
            char hash[] = "22233344455566670778889990";
             
            char telphone[100001][20];
            char temp[20];
             
            int compare( const void *arg1, const void *arg2 )
            {
            return strcmp((char*)arg1, (char*)arg2 );
            }
             
            // www.wutianqi.com
            int main()
            {
            //freopen("input.txt", "r", stdin);
            int flag = 0;
            int nCases;
            scanf("%d", &nCases);
            for(int i = 0; i < nCases; ++i)
            {
            getchar();
            scanf("%s", telphone[i]);
            int len = strlen(telphone[i]);
            int t = 0;
            for(int j = 0; j < len; ++j)
            {
            if(telphone[i][j] >= 'A' && telphone[i][j] <= 'Z')
            temp[t++] = hash[telphone[i][j]-'A'];
            else if(telphone[i][j] >= '0' && telphone[i][j] <= '9')
            temp[t++] = telphone[i][j];
            else if(telphone[i][j] == '-')
            ;
            }
            strcpy(telphone[i], temp);
            }
             
            qsort(telphone, nCases, sizeof(telphone[0]), compare);
             
             
            for(int i = 0; i < nCases; ++i)
            {
             
            int cnt = 1;
            strcpy(temp, telphone[i]);
            int j;
            for(j = i+1; j < nCases; ++j)
            {
            if(strcmp(temp, telphone[j]) == 0)
            cnt++;
            else
            break;
            }
            if(cnt > 1)   //這個地方沒處理好，麻煩。。。
            {
            flag = 1;
            for(int k = 0; k < 3; ++k)
            printf("%c", temp[k]);
            printf("-");
            for(int k = 3; k < 7; ++k)
            printf("%c", temp[k]);
            printf(" %d\n", cnt);
            }
            i = j-1;
            }
            if(flag == 0)
            printf("No duplicates.\n");
             
             
            return 0;
            }