問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1731思路:
求全排列，這個(gè)問(wèn)題本身挺簡(jiǎn)單，不過(guò)題目要求: a. 不能重復(fù)；b. 有序輸出
記得曾經(jīng)做過(guò)這題，當(dāng)時(shí)偷懶用STL過(guò)的(真要自己寫，估計(jì)當(dāng)時(shí)也不會(huì)(*^__^*) 嘻嘻……)
現(xiàn)在，決心棄用C++來(lái)做題，好好鍛煉基本功，所以就硬著頭皮自己慢慢寫
好在前段時(shí)間對(duì)于搜索題有了一定的積累，否則相信自己肯定還是不知道怎么寫的
找個(gè)例子，畫出遞歸調(diào)用樹，對(duì)于理解有很大幫助
純C遞歸實(shí)現(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 }