一个 C 语言的初级练习题,我想了很久也没想到合适的算法和结构,求教各位

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 2324 天前的主题，其中的信息可能已经有所发展或是发生改变。

如图是一个数字与字母对照表,用来将一个给定的 7 位的电话号码(不允许且不考虑出现 0 或者 1 的情况)转为所有可能的字母组合(3 的 7 次方种).要求一行一种可能将所有组合列出...
在列出的过程中实在是让我头疼,以三位号码 234 来说,有 27 种可能..
如果是人来画树状图,那么第一列先写一个 A,B,C,然后 A 拉出三个分叉写第二列,DEF,B 拉出三个分叉 DEF...
但是在编程的时候,要求一行一个组合,不可能搞成树状图的形式
也就是说要先向一个文本文件写入 9 个 A,9 个 B,9 个 C
然后 9 个 A 里 3 个 D,3 个 E,3 个 F
三个 D 再 G,H,I...

『也就是说要先向一个文本文件写入 9 个 A,9 个 B,9 个 C
然后 9 个 A 里 3 个 D,3 个 E,3 个 F
三个 D 再 G,H,I...』
就是这一步应该怎么用程序去表达,并将它改造位 7 位号码甚至 n 位号码都能处理的情况呢...自己也试了很多次但都以失败告终,求解答.谢谢

号码

def

分叉

写入

11 条回复 • 2017-12-27 16:52:05 +08:00

maosengshulei

2017-12-27 13:47:18 +08:00 via Android

DFS?

coderluan

2017-12-27 14:19:08 +08:00

我感觉想多了，没提复杂度，直接套循环就完了，3 的 7 次方也就 2000 多行而已，想让代码好看你弄个递归。

coderluan

2017-12-27 14:21:24 +08:00

PS : 你的分析我一个都看不明白，一行一个对着问题有啥影响，存文本又是闹哪样，你先把结果存个数组里不行吗？

rrfeng

2017-12-27 14:25:32 +08:00 via Android

这玩意儿需要什么数据结构？？！

hoyixi

2017-12-27 14:40:37 +08:00

lz 截图该把题干截完整，你转述是你自己的理解和你自己的语言。

MSilen

2017-12-27 14:41:04 +08:00 via Android

void wtf(String phone,String result){
if(null==phone||phone.equals("")){
打印 result;
return;
}
char a=获取 phone 第一个 char;
遍历 a 对应的三个字母{
wtf(phone 去掉第一个，result 加上遍历的字母);
}

}

差不多这样吧

GeruzoniAnsasu

2017-12-27 14:57:30 +08:00

这东西是递归解的，这么说明不明白？

Encode( prefix,numberSeries )
{
if(numberSeries == end()){
output(prefix);
return;
}
curNumber = numberSeries[0];
for(letter in letterTable[curNumber]){
prefix=prefix+letter;
Encode( prefix,numberSeries+1 );
}
}

ZZZZone

2017-12-27 16:21:07 +08:00

三种情况暴搜吧，数字转字符处理一下就行。

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;

string s;
int len;

void dfs(string t, int tot){
if(tot == len){
cout << t << endl;
return;
}
int x = (s[tot] - '0');
x = (x - 2) * 3;
dfs(t + (char)(x+'A'), tot + 1);
dfs(t + (char)(x+1+'A'), tot + 1);
dfs(t + (char)(x+2+'A'), tot + 1);
}

int main(){
cin >> s;
len = s.length();
dfs("", 0);
}

SaulLawliet

2017-12-27 16:29:55 +08:00

类似问题 https://leetcode.com/problems/letter-combinations-of-a-phone-number/discuss/
建议去那里看讨论

ofblyt

2017-12-27 16:31:25 +08:00

这个就是 dfs 和 backtrace 吧，正好最近在看 leetcode

zhujinliang

2017-12-27 16:52:05 +08:00

我一般这样解决：
把结果看作 3 进制的数字，0,1,2 分别对应三个字母，对整个数字不断自增 1，最终就可以遍历所有的可能
比如 234，是 "ABC" "DEF" "GHI" 的所有可能组合
0 对应 3 进制 000 第一位 0 对应 A 第二位 0 对应 D 第三位 0 对应 G
1 对应 3 进制 001 第一位 1 对应 B 第二位 0 对应 D 第三位 0 对应 G
2 对应 3 进制 002 第一位 2 对应 C 第二位 0 对应 D 第三位 0 对应 G
3 对应 3 进制 010 第一位 0 对应 A 第二位 1 对应 E 第三位 0 对应 G
4 对应 3 进制 011 第一位 1 对应 B 第二位 1 对应 E 第三位 0 对应 G
依次类推

手头没有 C 工具，用 go 撸了个
https://play.golang.org/p/ibNWC9QhBcj