C++ 中的手机数字键盘问题

2025 年 5 月 17 日 | 阅读 13 分钟

移动数字键盘问题是一个图遍历组合问题，其动机来源于手机数字键盘的约束（布局和移动）。因此，该问题在于在严格遵循邻近规则的情况下，可以形成指定长度为 n 的数字的唯一序列的数量。典型的手机数字键盘布局如下：

在此数字键盘布局中，我们将按键定义为图的节点，并将相邻的按键定义为共享水平、垂直或对角线边的按键。假设按键 5 与 2、4、6 和 8 相邻，而按键 0 仅与 8 相邻。形成序列时按键之间的有效转换由这些邻近关系决定。

问题在于找到可以定义的长度为 n 的序列的数量，使得从数字键盘上的任何数字开始，所有邻近约束都成立。如果 n=2，5 会产生有效的序列 52、54、56、58 等。可以使用大 O 符号来证明。随着 n 的增长，可能的序列数量呈指数级增长，因此问题变得更加困难。

该问题在各个领域都有实际应用，包括：

电信：分析基于数字键盘的输入模式，这对于创建用户友好的移动界面至关重要。
机器人和图遍历：按键及其邻居构成了一个图，这是图论路径算法的一个基础问题。
游戏设计和安全：应用于模式识别、游戏机制或构建安全输入系统，可以理解数字键盘上移动的可能序列。

通过将数字键盘表示为图，其中节点代表每个按键，边连接相邻的按键，来解决移动数字键盘问题。最后，我们使用动态规划方法来解决这个问题。对于任何给定的序列长度 n，我们都可以有效地计算链接序列的数量。具体来说，状态定义为当前按键和序列长度，并且利用先前序列长度计算出的结果来构建更长的序列解决方案。

方法一：蛮力法（递归回溯）

移动数字键盘问题首先通过蛮力法解决，即从数字键盘的每个数字开始，探索每个长度的序列。此方法将数字键盘表示为图，其中每个数字是一个节点，相邻按键之间的有效移动由边定义。该算法通过遍历此图，使用递归和回溯来生成所有可能的序列。

我们使用递归函数，该函数接收起始数字，移动到其有效的邻居，并在每一步减少序列长度。当长度变为 1 时，它会记录一个有效的序列。通过回溯，该算法保证涵盖所有可能的组合，因为当创建一个路径后，我们可以回溯并仅探索其他选项。

程序

让我们通过一个使用蛮力法的 C++ 示例来说明移动数字键盘问题。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Function to display the keypad layout (for clarity)
void displayKeypadLayout() {
    cout << "Mobile Numeric Keypad Layout:" << endl;
    cout << "1  2  3" << endl;
    cout << "4  5  6" << endl;
    cout << "7  8  9" << endl;
    cout << "   0" << endl;
}
// Function to get the neighbors of a given digit
vector<int> getNeighbors(int digit) {
    // Define the neighbors for each digit
    vector<vector<int>> neighbors = {
        {0, 8},        // Neighbors of 0
        {1, 2, 4},     // Neighbors of 1
        {2, 1, 3, 5},  // Neighbors of 2
        {3, 2, 6},     // Neighbors of 3
        {4, 1, 5, 7},  // Neighbors of 4
        {5, 2, 4, 6, 8}, // Neighbors of 5
        {6, 3, 5, 9},  // Neighbors of 6
        {7, 4, 8},     // Neighbors of 7
        {8, 5, 7, 9, 0}, // Neighbors of 8
        {9, 6, 8}      // Neighbors of 9
    };
    // Return the neighbors for the given digit
    return neighbors[digit];
}
// Function to display all neighbors for debugging
void displayNeighbors(int digit) {
    vector<int> neighbors = getNeighbors(digit);
    cout << "Neighbors of " << digit << ": ";
    for (int neighbor : neighbors) {
        cout << neighbor << " ";
    }
    cout << endl;
}
// Function to validate the input length
bool validateInputLength(int n) {
    if (n <= 0) {
        cout << "Invalid input! Sequence length must be greater than 0." << endl;
        return false;
    }
    return true;
}
// Function to display the current sequence
void displaySequence(const vector<int>& sequence) {
    for (int digit : sequence) {
        cout << digit;
    }
    cout << endl;
}
// Recursive function to generate sequences of the given length
int generateSequences(int currentDigit, int remainingLength, vector<int>& currentSequence) {
    // Base case: When the sequence length becomes 1
    if (remainingLength == 1) {
        // Display the sequence for debugging
        displaySequence(currentSequence);
        return 1;
    }
    // Get all neighbors of the current digit
    vector<int> neighbors = getNeighbors(currentDigit);
    // Initialize a count for the total number of sequences
    int totalCount = 0;
    // Traverse each neighbor and recursively generate sequences
    for (int neighbor : neighbors) {
        // Add the neighbor to the current sequence
        currentSequence.push_back(neighbor);
        // Recursive call with updated sequence length
        totalCount += generateSequences(neighbor, remainingLength - 1, currentSequence);
        // Backtrack: Remove the last digit after processing
        currentSequence.pop_back();
    }
    // Return the total count of sequences from this digit
    return totalCount;
}
// Function to calculate the total number of sequences of a given length
int calculateTotalSequences(int n) {
    // Validate input
    if (!validateInputLength(n)) {
        return 0;
    }
    // Initialize the total count of sequences
    int totalCount = 0;
    // Traverse all starting digits on the keypad
    for (int digit = 0; digit <= 9; ++digit) {
        // Debugging: Display neighbors of the current digit
        cout << "Processing digit: " << digit << endl;
        displayNeighbors(digit);
        // Initialize a sequence for tracking the current path
        vector<int> currentSequence = {digit};
        // Generate sequences starting from the current digit
        totalCount += generateSequences(digit, n, currentSequence);
        // Debugging: Print progress
        cout << "Completed processing for digit " << digit << endl;
    }
    // Return the total count of sequences
    return totalCount;
}
// Function to explain the process in detail (for user clarity)
void explainProcess() {
    cout << "This program calculates the total number of sequences of a specified length\n";
    cout << "that can be formed on a mobile numeric keypad. The rules are as follows:\n";
    cout << "1. You can start from any digit on the keypad.\n";
    cout << "2. You can only move to adjacent keys (up, down, left, or right).\n";
    cout << "3. The keypad layout and movement constraints are modeled as a graph.\n";
    cout << "4. The result is the total number of valid sequences following these rules.\n";
}
// Main function
int main() {
    // Display program explanation
    explainProcess();
    // Display the keypad layout
    displayKeypadLayout();
    // Input: Get the sequence length from the user
    int n;
    cout << "Enter the length of the sequences to generate: ";
    cin >> n;
    // Calculate the total number of sequences
    int result = calculateTotalSequences(n);
    // Output the result
    cout << "Total number of sequences of length " << n << " is: " << result << endl;  
    // End of program
    cout << "Program execution completed. Thank you!" << endl;
    return 0;
}

输出

This program calculates the total number of sequences of a specified length
that can be formed on a mobile numeric keypad. The rules are as follows:
1. You can start from any digit on the keypad.
2. You can only move to adjacent keys (up, down, left, or right).
3. The keypad layout and movement constraints are modeled as a graph.
4. The result is the total number of valid sequences following these rules.
Mobile Numeric Keypad Layout:
1  2  3
4  5  6
7  8  9
   0
Enter the length of the sequences to generate: 2
Processing digit: 0
Neighbors of 0: 0 8 
00
08
Completed processing for digit 0
Processing digit: 1
Neighbors of 1: 1 2 4 
11
12
14
Completed processing for digit 1
Processing digit: 2
Neighbors of 2: 2 1 3 5 
22
21
23
25
Completed processing for digit 2
Processing digit: 3
Neighbors of 3: 3 2 6 
33
32
36
Completed processing for digit 3
Processing digit: 4
Neighbors of 4: 4 1 5 7 
44
41
45
47
Completed processing for digit 4
Processing digit: 5
Neighbors of 5: 5 2 4 6 8 
55
52
54
56
58
Completed processing for digit 5
Processing digit: 6
Neighbors of 6: 6 3 5 9 
66
63
65
69
Completed processing for digit 6
Processing digit: 7
Neighbors of 7: 7 4 8 
77
74
78
Completed processing for digit 7
Processing digit: 8
Neighbors of 8: 8 5 7 9 0 
88
85
87
89
80
Completed processing for digit 8
Processing digit: 9
Neighbors of 9: 9 6 8 
99
96
98
Completed processing for digit 9
Total number of sequences of length 2 is: 36
Program execution completed. Thank you!

说明

数字键盘被视为一个图，包括数字节点和相邻按键之间的有效移动（边）。此方法使用递归和回溯来为给定图生成所有可能的数字序列。

关键组件

数字键盘表示：数字键盘由邻接列表表示，该列表定义了每个数字的有效邻居。例如，数字 5 的邻居是 2、4、6、8 和 5 本身。
递归函数：递归函数 generateSequences 是实现的核心。它以一个起始数字开始，遍历其所有邻居，并在每一步减少序列长度。如果剩余长度此时变为 1，则形成一个有效的序列，并进行计数。
回溯：此方法使用回溯来确保探索所有可能的序列。该函数在将数字放入序列后迭代地探索路径，然后回溯，通过移除末尾的数字并探索其他路径来执行新的操作。
序列跟踪：在遍历过程中，我们将当前序列存储在一个向量中。此向量有助于调试并实际跟踪序列中生成的内容。
输入验证和可视化：实现会验证输入，以确保序列长度大于零。它还可视化数字键盘并提供有关每个邻居的详细信息，以帮助用户更好地理解正在发生的事情。
计算：它从数字键盘上的每个数字开始，并通过所有有效序列递归地进行。所有起始数字的总和，并累加它们的序列总数。

复杂度分析

时间复杂度

上述蛮力法的时间复杂度可以根据从数字键盘上的每个数字开始的所有可能序列的递归探索来分析。

关键观察
每个数字最多可以有 5 个邻居，除了边缘数字（如 1、3、7 和 9），它们可能拥有更少（没有邻居、1 个邻居或 2 个邻居）。序列长度 n 与递归深度相同。函数在递归的每个级别探索当前数字的所有有效邻居。
递归调用
长度为 n 的序列中的每个数字最多会产生 5 次递归调用。结果是，每次递归调用都会为下一级别添加另一个递归调用，这意味着调用次数呈指数级增长。

空间复杂度

递归栈
递归栈所需的最大空间（即递归深度）为 O(n)。
当前序列向量
一个向量跟踪当前序列的下溢。由于它需要存储当前序列的数字，因此它还需要 O(n) 的空间复杂度。
最终计算
结合递归栈和序列向量，整体空间复杂度为 O(n)。

方法二：广度优先搜索 (BFS) 方法

广度优先搜索 (BFS) 是一种图遍历策略，它从起始节点（或数字键盘上的裸数字）开始，逐层遍历所有可能的路径并向外扩展。BFS 用于生成长度为 n 的有效序列，给定任何数字作为移动数字键盘问题的起始位置。每个数字（0-9）在图中表示为一个节点，数字之间的允许移动构成边。BFS 的特点是它应该按步骤（层）探索序列。每一步，每一层都比前一步多一个数字的序列。

程序

让我们通过一个使用广度优先搜索 (BFS) 方法的 C++ 示例来说明移动数字键盘问题。

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
// Define keypad mapping to its valid neighbors
unordered_map<int, vector<int>> keypad = {
    {0, {0, 8}},               // Key 0 has neighbors 0, 8
    {1, {1, 2, 4}},            // Key 1 has neighbors 1, 2, 4
    {2, {1, 2, 3, 5}},         // Key 2 has neighbors 1, 2, 3, 5
    {3, {2, 3, 6}},            // Key 3 has neighbors 2, 3, 6
    {4, {1, 4, 5, 7}},         // Key 4 has neighbors 1, 4, 5, 7
    {5, {2, 4, 5, 6, 8}},      // Key 5 has neighbors 2, 4, 5, 6, 8
    {6, {3, 5, 6, 9}},         // Key 6 has neighbors 3, 5, 6, 9
    {7, {4, 7, 8}},            // Key 7 has neighbors 4, 7, 8
    {8, {5, 7, 8, 0}},         // Key 8 has neighbors 5, 7, 8, 0
    {9, {6, 8, 9}}             // Key 9 has neighbors 6, 8, 9
};
// Structure to represent the state of a sequence
struct SequenceState {
    int digit;   // Current digit in the sequence
    int length;  // Length of the current sequence
};
// Function to initialize BFS with starting digits and a sequence length
void initializeBFS(queue<SequenceState>& bfsQueue, int sequenceLength) {
    for (int i = 0; i < 10; ++i) {
        bfsQueue.push({i, 1});  // Start with length 1 for each digit
    }
}
// Function to explore neighbors and expand sequences
void exploreNeighbors(queue<SequenceState>& bfsQueue, int currentDigit, int currentLength, int targetLength) {
    // If the current sequence reaches the target length, stop exploring further
    if (currentLength == targetLength) {
        return;
    }
    // Otherwise, explore all neighbors of the current digit
    for (int neighbor : keypad[currentDigit]) {
        bfsQueue.push({neighbor, currentLength + 1});
    }
}
// Function to count sequences of a given length using BFS
int countSequences(int n) {
    // Queue for BFS, stores pairs of (current_digit, current_length)
    queue<SequenceState> bfsQueue;
    int totalSequences = 0;
    // Initialize BFS with sequences of length 1 for each digit
    initializeBFS(bfsQueue, n);
    // Perform BFS to explore all sequences
    while (!bfsQueue.empty()) {
        auto [digit, length] = bfsQueue.front();
        bfsQueue.pop();
        // If the sequence has reached length n, count it
        if (length == n) {
            totalSequences++;
        }
        // Otherwise, explore all valid neighbors and add to queue
        else {
            exploreNeighbors(bfsQueue, digit, length, n);
        }
    }
    return totalSequences;
}
// Function to print the keypad for visualization
void printKeypad() {
    cout << "Keypad Layout:" << endl;
    cout << "1 2 3" << endl;
    cout << "4 5 6" << endl;
    cout << "7 8 9" << endl;
    cout << "  0" << endl;
}
// Function to validate the input sequence length
bool validateInput(int n) {
    if (n <= 0) {
        cout << "Error: Sequence length must be greater than 0!" << endl;
        return false;
    }
    return true;
}
// Function to handle user interaction and output
void handleUserInput() {
    int n;
    cout << "Enter the length of the sequences (positive integer): ";
    cin >> n;
    // Validate the input length
    if (!validateInput(n)) {
        return;
    }
    // Print the keypad layout for visualization
    printKeypad();
    // Call BFS function to calculate number of valid sequences of length n
    int result = countSequences(n);
    // Output the result
    cout << "Total number of sequences of length " << n << ": " << result << endl;
}
int main() {
    // Start the program by handling user input
    handleUserInput();
    return 0;
}

输出

Enter the length of the sequences (positive integer): 3
Keypad Layout:
1 2 3
4 5 6
7 8 9
  0
Total number of sequences of length 3: 130

说明

数字键盘表示

我们有一个无序映射（unordered_map<int, vector<int>>），键 -> 有效的邻居键（0-9）。例如：

按键 0 可以移动到 0 和 8。按键 1 可以访问 1、4、2。

结构

SequenceState：BFS 中的序列状态由结构 SequenceState 表示。它包含两个属性：

digit：序列的最新数字。
length：当前序列的长度。

辅助函数

initializeBFS
该函数从 0 到 9 的按键开始，并将长度为 1 的序列放入 BFS 队列中。BFS 队列使用 0 到 9 的每个数字的 SequenceState 进行初始化，数字和序列长度为 1。
exploreNeighbors
此函数遍历数字的邻居，并生成一个长度递增的序列。对于给定的序列长度 n，如果当前序列长度也为 n，则停止该序列的进一步探索。否则，它会将有效的邻居数字移入 BFS 队列。

复杂度分析

时间复杂度

移动数字键盘问题的广度优先搜索 (BFS) 方法的时间复杂度与 BFS 遍历生成的可能序列的数量有关。

初始状态
因此，10 个初始序列（长度均为 1）被放入队列中，从 0 到 9 开始。
BFS 遍历
BFS 查看每个数字的可能值及其有效邻居，从而生成新的序列，使每个数字的序列长度增加 1。在 BFS 的每个级别，我们可以根据每个具有最多 5 个邻居的现有序列生成最多 5 个新序列。
级别数量
该算法按递增级别创建序列，即逐级生成序列，每个级别包含给定长度的序列。该序列对于长度 n 的级别添加了一个代表序列中另一个数字的额外级别，因此总共是 n 层深。
序列总数
在每个级别，每个序列最多可以生成 5 个新序列。因此，长度为 n 的所有序列的数量约为 5^n，因为每个数字最多有 5 个可能的邻居。
序列的生成占主导地位的时间复杂度，相对于处理的序列数量。由于在最坏情况下我们探索 5^n 个序列，因此该算法的整体时间复杂度为 O(5^n)。

空间复杂度

BFS 方法的空间复杂度主要在于队列中序列的存储，这直接与图中节点的数量有关。

队列存储
正在探索的序列存储在队列中。在最坏的情况下，对于每个可能的数字组合，队列的长度最多可以达到 5^n，每个序列一个。
内存使用
序列是数字对和序列长度，每个序列占用恒定空间。因此，有必要预留与队列中序列总数成比例的总空间。

下一个主题C++ 中的 std::assoc_laguerre 方法

C++ 中的手机数字键盘问题

方法一：蛮力法（递归回溯）

程序

说明

关键组件

复杂度分析

方法二：广度优先搜索 (BFS) 方法

程序

说明

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中的手机数字键盘问题

方法一：蛮力法（递归回溯）

程序

说明

关键组件

复杂度分析

方法二：广度优先搜索 (BFS) 方法

程序

说明

复杂度分析

相关帖子

C++ 中如何使用 const_iterator 遍历 set？

C++ 中范围 [l, r] 内的对称数字数量（对称数字 III）

C++ 俄罗斯农民乘法算法

C++ 中的 std::midpoint

C++ std::pmr::synchronized_pool_resource

C++ 中使用 Binet 公式查找第 n 个斐波那契数

C++ 中 tellg 和 tellp 的区别

C++ 指数搜索算法

C++ 中的矩阵指数化

C++ 中如何将 CSV 文件中的数据读入二维数组？

订阅 Tpoint Tech