手机上的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 阅读(394)
评论(0) 编辑 收藏 引用 所属分类:
算法基础