問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1731思路:
求全排列，這個問題本身挺簡單，不過題目要求: a. 不能重復(fù)；b. 有序輸出
記得曾經(jīng)做過這題，當(dāng)時偷懶用STL過的(真要自己寫，估計當(dāng)時也不會(*^__^*) 嘻嘻……)
現(xiàn)在，決心棄用C++來做題，好好鍛煉基本功，所以就硬著頭皮自己慢慢寫
好在前段時間對于搜索題有了一定的積累，否則相信自己肯定還是不知道怎么寫的
找個例子，畫出遞歸調(diào)用樹，對于理解有很大幫助
純C遞歸實現(xiàn)如下:
代碼:
1 /* 364K 454MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 201
6 char str[MAX_LEN];
7 int len;
8
9 int
10 compare(const void *arg1, const void *arg2) /* for qsort */
11 {
12 return *((char *)arg1) - *((char *)arg2);
13 }
14
15 void
16 swap(char *seq, int i, int j) /* exchange */
17 {
18 char tmp = seq[i];
19 seq[i] = seq[j];
20 seq[j] = tmp;
21 }
22
23 void
24 perm(char *seq, int begin, int end)
25 {
26 int i, j, tmp;
27 char pre=0;
28 if(begin >= end) {
29 printf("%s\n", seq);
30 return;
31 }
32 for(i=begin; i<=end; i++) {
33 if(i>begin && seq[i]==seq[begin]) /* avoid duplicates */
34 continue;
35 if(pre == seq[i]) /* avoid duplicate */
36 continue;
37 /* in order to keep the alphabetical order */
38 tmp = seq[i];
39 for(j=i; j>begin; j--)
40 seq[j] = seq[j-1];
41 seq[begin] = tmp;
42 perm(seq, begin+1, end);
43 tmp = seq[begin];
44 for(j=begin; j<i; j++)
45 seq[j] = seq[j+1];
46 seq[i] = tmp;
47 /*
48 swap(seq, begin, i);
49 perm(seq, begin+1, end);
50 swap(seq, begin, i);
51 */
52 pre = seq[i];
53 }
54 }
55
56 int
57 main(int argc, char **argv)
58 {
59 while(scanf("%s", str) != EOF) {
60 len = strlen(str);
61 qsort(str, len, sizeof(char), compare);
62 perm(str, 0, len-1);
63 }
64 }