Генерируйте 10-разрядное число с помощью клавиатуры телефона
Учитывая клавиатуру телефона как показано ниже:
1 2 3
4 5 6
7 8 9
0
Сколько различных 10-разрядных чисел может быть сформировано, начав от 1? Ограничение состоит в том, что перемещение от 1 цифры до следующего подобно перемещению Рыцаря в игре в шахматы.
Для, например, если мы в 1 затем, следующая цифра может быть или 6 или 8, если мы в 6 затем, следующая цифра может быть 1, 7 или 0.
Повторение цифр позволяется - 1616161616, верный номер.
Существует ли полиномиальный алгоритм времени, который решает эту проблему? Проблема требует, чтобы мы просто дали количество 10-разрядных чисел и не обязательно перечислили числа.
Править: Я пытался моделировать это как график с каждой цифрой, имеющей 2 или 3 цифры как ее соседи. Затем я использовал DFS, чтобы перейти до глубины 10 узлов и затем увеличить количество чисел каждый раз, когда я достиг глубины 10. Это, очевидно, не полиномиальное время. Принятие каждой цифры имело всего 2 соседей, это потребует, по крайней мере, 2^10 повторения.
Переменная здесь является количеством цифр. Я взял, например, 10 чисел цифры. Это могли также быть n-цифры.
3 ответа
Конечно, это можно сделать за полиномиальное время. Это отличное упражнение в динамическом программировании или мемоизации .
Предположим, что N (количество цифр) для примера равно 10.
Подумайте об этом рекурсивно так: Сколько чисел я могу построить, используя 10 цифр, начиная с 1 ?
Ответ:
[number of 9-digit numbers starting from 8] +
[number of 9-digit numbers starting from 6].
Итак, сколько "9-значных" числа, начинающиеся с 8 "есть? Ну,
[number of 8-digit numbers starting from 1] +
[number of 8-digit numbers starting from 3]
и тд. Базовый случай достигается, когда вы получаете вопрос «Сколько однозначных номеров начинается с X » (и ответ, очевидно, равен 1).
Когда дело доходит до сложности, главное наблюдение состоит в том, что вы повторно используете ранее вычисленные решения. То есть, например, ответ на «сколько имеется 5-значных номеров, начинающихся с 3 » , может использоваться как при ответе на «сколько 6-значных номеров есть ли, начиная с 8 " И ", сколько существует 6-значных номеров, начиная с 4 ". Это повторное использование приводит к уменьшению сложности с экспоненциальной до полиномиальной.
Давайте более подробно рассмотрим сложность решения динамического программирования:
Такая реализация будет заполнять матрицу следующим образом:
num[1][i] = 1, for all 0<=i<=9 -- there are one 1-digit number starting from X.
for digits = 2...N
for from = 0...9
num[digits][from] = num[digits-1][successor 1 of from] +
num[digits-1][successor 2 of from] +
...
num[digits-1][successor K of from]
return num[N][1] -- number of N-digit numbers starting from 1.
Алгоритм просто заполняет матрицу по одной ячейке за раз, а матрица имеет размерность 10 * N и, таким образом, выполняется за линейное время .
Записал с макушки, поправьте меня, если есть опечатки.
Это можно сделать за O(log N). Рассмотрим клавиатуру и возможные перемещения по ней как граф G(V, E), где вершины - это доступные цифры, а ребра говорят, какие цифры могут следовать за какими. Теперь для каждой позиции выхода i мы можем сформировать вектор Paths(i), содержащий количество различных путей, которыми может быть достигнута каждая вершина. Теперь довольно легко понять, что для данной позиции i и цифры v возможные пути, по которым она может быть достигнута, равны сумме различных путей, по которым могут быть достигнуты предыдущие цифры, или Paths(i)[v] = sum(Paths(i-1)[v2] * (1 if (v,v2) in E else 0) for v2 in V ). Теперь, это взятие суммы каждой позиции предыдущего вектора, умноженной на соответствующую позицию в столбце матрицы смежности. Поэтому мы можем упростить это как Paths(i) = Paths(i-1) - A, где A - матрица смежности графа. Если избавиться от рекурсии и воспользоваться ассоциативностью умножения матриц, то получится Paths(i) = Paths(1) - A^(i-1). Мы знаем Paths(1): у нас есть только один путь, к цифре 1.
Общее количество путей для n-значного числа равно сумме путей для каждой цифры, поэтому окончательный алгоритм становится таким: TotalPaths(n) = sum( [1,0,0,0,0,0,0,0,0,0,0] - A^(n-1) )
Экспоненция может быть вычислена через квадрат за O(log(n)) время, учитывая постоянные умножения времени, иначе O(M(n) * log(n)), где M(n) - сложность вашего любимого алгоритма умножения произвольной точности для n разрядных чисел.
Ответ попроще.
#include<stdio.h>
int a[10] = {2,2,2,2,3,0,3,2,2,2};
int b[10][3] = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{1,7,0},{2,6},{1,3},{2,4}};
int count(int curr,int n)
{
int sum = 0;
if(n==10)
return 1;
else
{
int i = 0;
int val = 0;
for(i = 0; i < a[curr]; i++)
{
val = count(b[curr][i],n+1);
sum += val;
}
return sum;
}
}
int main()
{
int n = 1;
int val = count(1,0);
printf("%d\n",val);
}
празднуют !!