手機上的T9鍵盤每個數字按鍵對應若干個字母，要求輸入一個電話號碼，輸出所有的可能的字母組合。
比如：
1 char *hash[10] = {"", "", "ABC", "DEF", "GHI",
2 "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
可以知道數字2對應著A,B,C三個字母，數字3對應著D,E,F三個字母，以此類推。那么對于電話號碼345，可能的字母組合有27種，如果要我們手寫的話可能會這么寫，先寫ADG，再寫BDG，再寫CDE，然后在寫AEG，然后是BEG，然后是CEG等等。同樣，寫程序也可以按照這個思路來，只不過對每個數字，我們都需要記錄當前打印到那個字母了。根據手寫過程可以很容易的理解下面的程序：
1 void find_all_words(int *call_num, int n) {
2 int i;
3 if (call_num == NULL || n <= 0) {
4 return;
5 }
6
7 char *hash[10] = {"", "", "ABC", "DEF", "GHI",
8 "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
9
10 int cur_index[n];
11 memset(cur_index, 0, sizeof(cur_index) * n);
12
13 int total_amount[10];
14 for (i = 0; i < 10; ++i) {
15 total_amount[i] = strlen(hash[i]);
16 }
17
18 while (1) {
19 for (i = 0; i < n; ++i) {
20 printf("%c", hash[call_num[i]][cur_index[i]]);
21 }
22 printf("\n");
23
24 int index = 0;
25 while (index < n) {
26 if (cur_index[index] >= total_amount[call_num[index]] - 1) {
27 cur_index[index] = 0;
28 index++;
29 } else {
30 cur_index[index]++;
31 break;
32 }
33 }
34 if (index == n) {
35 break;
36 }
37 }
38 }
如果是遞歸算法的話也比較簡單，如下 ：
1 char *hash[10] = {"", "", "ABC", "DEF", "GHI",
2 "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
3
4 #define MAX_LEN 100
5 int cur_index[MAX_LEN];
6 int total_amount[10];
7
8 void find_all_words(int *call_num, int n, int index) {
9 int i;
10 if (index == n) {
11 for (i = 0; i < n; ++i) {
12 printf("%c", hash[call_num[i]][cur_index[i]]);
13 }
14 printf("\n");
15 } else {
16 for (cur_index[index] = 0;
17 cur_index[index] < total_amount[call_num[index]];
18 ++cur_index[index]) {
19 find_all_words(call_num, n, index + 1);
20 }
21 }
22 }
別忘了初始化cur_index和totla_amount數組。
posted on 2012-09-03 22:25
myjfm 閱讀(447)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎