БлогNot. Задача о мобильной клавиатуре

Задача о мобильной клавиатуре

Работая с обычной клавиатурой мобильного телефона,

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 просмотров]


теги: c++ программирование числа алгоритм мобильник

К этой статье пока нет комментариев, Ваш будет первым