一道很有挑战性的题目, 看你的算法了.

xwdok 2006-12-27 04:31:47

手机上的每个数字对应几个字母，给你一串数字，请你输出所有可能的字母串。要求是最好的算法

...全文

782 17 打赏收藏转发到动态举报

写回复

用AI写文章

17 条回复

切换为时间正序

请发表友善的回复…

发表回复

oo 2007-01-23

打赏
举报

楼上：手机里 ‘2’对应‘ABC’，按一次2只能得到A，不会得到B或C，只有连按2次‘2’才能得到B，连按3次‘2’才能得到‘C’，所以输入‘23’只能得到‘AD’不会有其他的结果。

QuickKeyBoard 2007-01-21

打赏
举报

#include <iostream>
using namespace std;

#define MAX 1000

char lib[10][5]=
{
"",
"",
"ABC",
"DEF",
"GHI",
"JKL",
"MNO",
"PQRS",
"TUV",
"WXYZ",
};
char s[MAX];
int n;
char out[MAX];

void fill(int k)
{
if(k==n)
{
out[n]='\0';
cout<<out<<endl;
return;
}
int i;
for(i=0;lib[s[k]-'0'][i];i++)
{
out[k]=lib[s[k]-'0'][i];
fill(k+1);
}
}

int main()
{
cin>>s;
n=strlen(s);
fill(0);
return 0;
}
这样。不写解释了。lz大约可以看懂。
输入23
则得
AD
AE
AF
BD
BE
BF
CD
CE
CF

Sco_field 2007-01-20

打赏
举报

呵呵，越狱

心中那自由的世界 2007-01-20

打赏
举报

这个题目本质上是求元素的组合的全排列,假定每个按键必须按下,也就是必须产生一个字符.例如
2--(a,b,c)
3--(d,e,f)
4--(g,h,i)
那么对于a,d,g这三个字符会有(a,d,g), (a,g,d), (d,a,g),(d,g,a),(g,d,a),(g,a,d)这种可能的字符串.而三个字符的可能组合是可以用枚举求出来的,这里可能的就有
(a,d,g),(a,e,h),(a,f,i),
(b,d,g),(b,e,h),(b,f,i)
(c,d,g),(c,e,h),(c,f,i)
这样子求出所有的字符组合就不难了.

至于二楼的程序,只是列出了三个数字可能产生的组合

wokiss 2007-01-20

打赏
举报

我感觉楼主的意思是,手机上的10个数字(0-9)对应着26个字母,例如数字1对应字母(a,b,c),
然后给出数字窜,比如"321",让程序输出可能的字符窜组合.
不过我也只能想出楼主那样的方法,呵呵.用多个for循环,.

马哲 2007-01-20

打赏
举报

越狱II---之算法版

Silent_Spring 2007-01-20

打赏
举报

USACO上的题吧

iambic 2007-01-19

打赏
举报

>>楼上的好好学学数据结构, 知道什么叫时间复杂度?
遇到你不能理解的东西就沉默点，你还没资格在我面前叫嚣数据结构。仔细看下楼上的意见。

oo 2007-01-19

打赏
举报

一楼的程序看起来不太对，
只有相同数字出现时才有必要算各种可能，如果不同数字则是唯一的。
如果有相同数字出现，则输出的字母个数可能是1-n个的，n为连续数字个数。
例如223，可能是BD也可能是AAD

jiangbin00cn 2007-01-19

打赏
举报

顶
要求太低，算法没有意义
加一个要求：
输入的数字都可以组成一个英文单词，求最优算法
例如
输入
6284

正解 math

珍惜生命远离CPP 2006-12-27

打赏
举报

结果都一样，没什么最优

xwdok 2006-12-27

打赏
举报

楼上的好好学学数据结构, 知道什么叫时间复杂度?

iambic 2006-12-27

打赏
举报

晕——复杂不高……是常数。

xwdok 2006-12-27

打赏
举报

我认为关键是数据结构设计最重要

yisea123 2006-12-27

打赏
举报

最好的算法?

估计这就是最好的算法了

因为本来就有那么多的组合

xwdok 2006-12-27

打赏
举报

楼上的跟我想的有些相似,我也想用数组来存储字母(具体我是用字符串存的)
这样实现上是可以穷举的,但是算法的复杂度很高.
还有没有?

lastwish 2006-12-27

打赏
举报

我想到一个:但估计不是怎么好,各位赐教
每个数字对应几个字母,用一个数组来存,以3个数字为例,
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
{
string str;
str+=a[i];
str+=b[j];
str+=c[k];
textout(str);
}