Задача о мобильной клавиатуре
Работая с обычной клавиатурой мобильного телефона,
unsigned char keypad[4][3] = { {'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'} };
будем нажимать только кнопки, расположенные вверх, влево, вправо или вниз от текущей кнопки. Нельзя нажимать угловые кнопки нижнего ряда ('*' и '#').
Задача - по заданному натуральному числу N найти количество возможных чисел длины N.
Для N = 1 ответ = 10 (0, 1, ..., 9)
Для N = 2 ответ = 36, вот его первые слагаемые:
Начиная с "0", имеем 00, 08 (всего 2)
Начиная с "1", имеем 11, 12, 14 (всего 3)
Начиная с "2", имеем 22, 21, 23, 25 (всего 4)
Начиная с "3", имеем 33, 32, 36 (всего 3)
Начиная с "4", имеем 44,41,45,47 (всего 4)
Начиная с "5", имеем 55,54,52,56,58 (всего 5)
и т.д.
Программа (консоль актуальной сборки Visual Studio 2019) иллюстрирует подход к решению с помощью методов динамического программирования за время O(n).
#include <iostream> int getCount(unsigned char keypad[][3], int n) { //Количество чисел длины n на клавиатуре keypad if (keypad == NULL || n <= 0) return 0; if (n == 1) return 10; //Смещения для шага влево, вверх, вправо, вниз int row[] = { 0, 0, -1, 0, 1 }; int col[] = { 0, -1, 0, 1, 0 }; //count[i][j] - количество чисел, начиная с цифры i длины j int *count[10]; for (int i = 0; i < 10; i++) { count[i] = new int [n+1]; count[i][0] = 0; count[i][1] = 1; } int i = 0, j = 0, k = 0, move = 0, ro = 0, co = 0, num = 0; int nextNum = 0, totalCount = 0; //Снизу вверх - получить количество чисел длины 2, 3, 4, ..., n for (k = 2; k <= n; k++) { for (i = 0; i < 4; i++) { //Цикл по строке клавиатуры for (j = 0; j < 3; j++) { //Цикл по столбцу клавиатуры if (keypad[i][j] != '*' && keypad[i][j] != '#') { //Только 0..9 //Числа, начинающиеся с цифры keypad[i][j] длиной k; //keypad[i][j] станет 1-й цифрой и далее ищем (k-1) цифр num = keypad[i][j] - '0'; count[num][k] = 0; //Идти влево, вверх, вправо, вниз от текущего местоположения, //если новое местоположение допустимо, получить числовое значение длиной (k-1) для новой цифры //и добавить ранее найденно количество чисел for (move = 0; move < 5; move++) { ro = i + row[move]; co = j + col[move]; if (ro >= 0 && ro <= 3 && co >= 0 && co <= 2 && keypad[ro][co] != '*' && keypad[ro][co] != '#') { nextNum = keypad[ro][co] - '0'; count[num][k] += count[nextNum][k - 1]; } } } } } } //Получить количество возможных чисел длины n, начиная с цифры 0, 1, ..., 9 totalCount = 0; for (i = 0; i <= 9; i++) { //std::cout << "Start with " << i << ": " << count[i][n] << std::endl; //отладка totalCount += count[i][n]; } for (int i = 9; i > -1; i--) delete count[i]; return totalCount; } int main() { unsigned char keypad[4][3] = { {'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'} }; for (int k = 1; k < 10; k++) { std::cout << "Length = " << k << ", count = " << getCount(keypad, k) << std::endl; } return 0; }
На самом деле, как это обычно бывает с ДП, если взглянуть на вопрос "чуть поуже", можно обойтись только двумя массивами размерности 10. Вот изменённая функция getCount
:
int getCount(unsigned char keypad[][3], int n) { if (keypad == NULL || n <= 0) return 0; if (n == 1) return 10; int odd[10], even[10]; //odd[i], even[i] - количество чисел, начинающихся с цифры i, для любой длины j int i = 0, j = 0, useOdd = 0, totalCount = 0; for (i = 0; i <= 9; i++) odd[i] = 1; // для j = 1 for (j = 2; j <= n; j++) { //Для j от 2 до n useOdd = 1 - useOdd; //Явно пишем строки для чисел от 0 до 9. Это можно записать как DFS на сетке 4X3, //используя допустимые сочутания строк и столбцов. //https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83 if (useOdd == 1) { even[0] = odd[0] + odd[8]; even[1] = odd[1] + odd[2] + odd[4]; even[2] = odd[2] + odd[1] + odd[3] + odd[5]; even[3] = odd[3] + odd[2] + odd[6]; even[4] = odd[4] + odd[1] + odd[5] + odd[7]; even[5] = odd[5] + odd[2] + odd[4] + odd[8] + odd[6]; even[6] = odd[6] + odd[3] + odd[5] + odd[9]; even[7] = odd[7] + odd[4] + odd[8]; even[8] = odd[8] + odd[0] + odd[5] + odd[7] + odd[9]; even[9] = odd[9] + odd[6] + odd[8]; } else { odd[0] = even[0] + even[8]; odd[1] = even[1] + even[2] + even[4]; odd[2] = even[2] + even[1] + even[3] + even[5]; odd[3] = even[3] + even[2] + even[6]; odd[4] = even[4] + even[1] + even[5] + even[7]; odd[5] = even[5] + even[2] + even[4] + even[8] + even[6]; odd[6] = even[6] + even[3] + even[5] + even[9]; odd[7] = even[7] + even[4] + even[8]; odd[8] = even[8] + even[0] + even[5] + even[7] + even[9]; odd[9] = even[9] + even[6] + even[8]; } } totalCount = 0; if (useOdd == 1) { for (i = 0; i <= 9; i++) totalCount += even[i]; } else { for (i = 0; i <= 9; i++) totalCount += odd[i]; } return totalCount; }
Length = 1, count = 10 Length = 2, count = 36 Length = 3, count = 138 Length = 4, count = 532 Length = 5, count = 2062 Length = 6, count = 7990 Length = 7, count = 30984 Length = 8, count = 120130 Length = 9, count = 465832
Есть и другие интересные задачи, связанные с мобильной или "калькуляторной" клавиатурой, особенно касающиеся признаков делимости на 11 и 9.
15.03.2022, 12:26 [514 просмотров]