电话号码对应英语单词

问题描述

电话的号码盘一般可以用于输入字母。如用可以输入A、B、C，用3可以输入D、E、F等。对于号码5869872，可以依次输出其代表的所有字母组合。如：JTMWTPA、JTMWTPB......

      1. 你是否可以根据这样的对应关系设计一个程序，尽可能快地从这些字母组合中找到一个有意义的单词来表述一个电话号码呢？如：可以用单词“computer”来描述号码26678837.

     2. 对于一个电话号码，是否可以用一个单词来代表呢？怎样才是最快的方法呢？显然，肯定不是所有的电话号码都能够对应到单词上去。但是根据问题1的解答，思路相对比较清晰。

问题分析

每个电话号都有自己独一无二的排列组合，每个电话号对应的每一位数字都有对应的特定的字符串。每个数字一次只能代表一个字符。因此我们可以生成所有组合结果，在查看是否符合一个单词的要求。

关键问题如何有规律的去做排列组合，并用程序实现。

实现方式如下：

循环实现

在此我将不写程序的思路，注释中已经给出

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

int main()
{
    //将每一个数字对应的字符进行存储
    char c[10][10] = {  "", "", "ABC",  "DEF",  "GHI",  "JKL",  "MNO",  "PQRS", "TUV",  "WXYZ" };
    int total[10] = { 0,0,3,3,3,3,3,4,3,4 };        //存储对应数字，所对应的字符长度
    int number[12] = { 0 };                         //电环号码的长度，不超过12
    int answer[12] = { 0 };                         //对应电话数，对应字符的当前位置
    cout << "请输入电话号的位数：";
    int num;
    cin >> num;
    cout << endl;
    cout << "请输入电话号，每个电话号自建用空格：";
    cout << endl;
    for (int i = 0;i < num;i++)
    {
        cin >> number[i];
    }
    cout << endl;
    while (true)
    {   //此for循环是为了输出，已经确定了电话号码，并且确定电话号每一位数代表的字符的当前位置
        for (int i = 0;i < num;++i)
        {
            cout << c[number[i]][answer[i]];
        }
        cout << endl;
        int k = num - 1;
        //此循环是为了，确定电话号的某一位数的对应字符串的当前位置的
        while (k >= 0)
        {
            //这个判断是核心，当电话号的当前位数，的当前位置不是最后一位，则向后移动一位
            if (answer[k] < total[number[k]] - 1)
            {
                answer[k]++;
                break;
            }
            else
            {
                //当前字符是最后一位，则重置当前字符的位置为初始位置，且将电话号的当前位数向前移一位
                answer[k] = 0;
                k--;
            }
        }
        if (k < 0)
            break;
    }
}

递归实现

#include<iostream>
#include<string>
using namespace std;
void RecursiveSearch(int *number, int *answer, int index, int n);
//将每一个数字对应的字符进行存储
char c[10][10] = { "",  "", "ABC",  "DEF",  "GHI",  "JKL",  "MNO",  "PQRS", "TUV",  "WXYZ" };
int total[10] = { 0,0,3,3,3,3,3,4,3,4 };        //存储对应数字，所对应的字符长度
int main()
{
    
    int number[12] = { 0 };                         //电环号码的长度，不超过12
    int answer[12] = { 0 };                         //对应电话数，对应字符的当前位置
    cout << "请输入电话号的位数：";
    int num;
    cin >> num;
    cout << endl;
    cout << "请输入电话号，每个电话号自建用空格：";
    cout << endl;
    for (int i = 0;i < num;i++)
    {
        cin >> number[i];
    }
    cout << endl;
    RecursiveSearch(number, answer, 0, num);

}
//此递归函数，利用了树的分层思想，index每加一次1就相当于加一层
//整体用了深度优先的思想，左递归
void RecursiveSearch(int *number, int *answer, int index, int n)
{
    if (index == n)
    {
        for (int i = 0;i<n;i++)
        {
            cout << c[number[i]][answer[i]];
        }
        cout << endl;
        return;
    }
    else
    {
        //此处的for循环是为了，横向扩展的相当于，移动当前号码位所代表字符的当前位置
        for (answer[index] = 0;answer[index]<total[number[index]];answer[index]++)
        {
            RecursiveSearch(number, answer, index + 1, n);
        }
    }
}

捕获.PNG