数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律研究移动数字键盘问题\n
本例中，给出一个数字手机键盘。我们只能按当前按钮的顶部、底部、右侧和左侧按钮，不允许按对角键。我们也不能按键盘上的 * 和 # 按钮。
给定一个数字，我们必须找到可以使用键盘和给定的规则组成的指定位数的数字的数量。
输入和输出
Input: Digit count. Say 3 digit numbers. Output: Number of possible 3 digit numbers, that can be formed with the given conditions. Here the answer is 138.
算法
getCount(n)
输入：数字 n。
输出：在手机键盘中键入 n 位数字的可能方法。
Begin if n <= 0, then return 0 if n = 1, then return 10 define two array row and col to move each direction from current key define count table of size (10 x n+1) for i in range 0 to 9, do count[i, 0] := 0 count[i, 1] := 1 done for k in range 2 to n, do for i in range 0 to 3, do for j in range 0 to 2, do if key[i, j] ≠ * or #, then num := key[i, j] count[num, k] := 0 for all possible moves, do rowMove := i + row[move] colMove := j + col[move] if rowMove in (0..3) colMove in (0..2), and key ≠ * or #, then nextNum := key[rowMove, colMove] count[num, k] := count[num, k] + count[nextNum, k+1] done done done done totalCount := 0 for i in range 1 to 9, do totalCount := totalCount + count[i, n] done return totalCount End
示例
#include <iostream>
using namespace std;
char keypad[4][3] = {
{'1','2','3'},
{'4','5','6'},
{'7','8','9'},
{'*','0','#'}
};
int getCount(int n) {
if(keypad == NULL || n <= 0)
return 0;
if(n == 1)
return 10; //1 digit number 0-9
int row[] = {0, 0, -1, 0, 1}; //for up and down the row will change
int col[] = {0, -1, 0, 1, 0}; //for left and right column will change
int count[10][n+1]; //store count for starting with i and length j
int move=0, rowMove=0, colMove=0, num = 0;
int nextNum=0, totalCount = 0;
for (int i=0; i<=9; i++) { //for length 0 and 1
count[i][0] = 0;
count[i][1] = 1
}
for (int k=2; k<=n; k++) { //for digits 2 to n
for (int i=0; i<4; i++ ) { //for Row wise
for (int j=0; j<3; j++) { // for column wise
if (keypad[i][j] != '*' && keypad[i][j] != '#') { //keys are not * and #
num = keypad[i][j] - '0'; //find the number from the character
count[num][k] = 0;
for (move=0; move<5; move++) {
rowMove = i + row[move]; //move using row moving matrix
colMove = j + col[move]; //move using column moving matrix
if (rowMove >= 0 && rowMove <= 3 && colMove >=0 && colMove <= 2 &&
keypad[rowMove][colMove] != '*' && keypad[rowMove][colMove] != '#') {
nextNum = keypad[rowMove][colMove] - '0'; //find next number
count[num][k] += count[nextNum][k-1];
}
}
}
}
}
}
totalCount = 0;
for (int i=0; i<=9; i++) //for the number starting with i
totalCount += count[i][n];
return totalCount;
}
int main() {
int n;
cout << "Number of digits: "; cin >> n;
cout << "Possible Combinations: " << getCount(n);
}输出
Number of digits: 3 Possible Combinations: 138
更新于： 2020 年 6 月 17 日
1K+ 阅读量
广告