Ответ 1
Действительно, есть подход к этой схеме, которая, как оказалось, работает довольно часто. Он также может использоваться для перечисления всех X с данным свойством при условии, что их число достаточно мало. Вы можете даже использовать его для агрегирования некоторого ассоциативного оператора по всему X с заданным свойством, например, чтобы найти их сумму.
Чтобы понять общую идею, постараемся сформулировать условие X ≤ Y в терминах десятичных представлений X и Y.
Скажем, мы имеем X = x 1 x 2... x n - 1 x n и Y = y 1 y 2... y n - 1 y n, где x i и y i - это десятичные цифры X и Y. Если числа имеют разную длину, мы всегда можем добавить нулевые цифры в начало более короткого.
Определим leftmost_lo как наименьший я с x i < у <суб > явспом > . Определим leftmost_lo как n + 1, если такого я не существует.
Аналогично, мы определяем leftmost_hi как наименьший я с x i > y i, или n + 1 в противном случае.
Теперь X ≤ Y истинно, если и точно, если leftmost_lo <= leftmost_hi. С этим наблюдением становится возможным применить подход динамического программирования к проблеме, который "устанавливает" цифры X один за другим. Я продемонстрирую это с вашими примерами проблем:
Вычислить число f (Y) целых чисел X со свойством X ≤ Y и X имеет цифру sum 60
Пусть n - число Y-цифр, а y[i] - i-я десятичная цифра Y в соответствии с вышеприведенным определением. Следующий рекурсивный алгоритм решает проблему:
count(i, sum_so_far, leftmost_lo, leftmost_hi):
if i == n + 1:
# base case of the recursion, we have recursed beyond the last digit
# now we check whether the number X we built is a valid solution
if sum_so_far == 60 and leftmost_lo <= leftmost_hi:
return 1
else:
return 0
result = 0
# we need to decide which digit to use for x[i]
for d := 0 to 9
leftmost_lo' = leftmost_lo
leftmost_hi' = leftmost_hi
if d < y[i] and i < leftmost_lo': leftmost_lo' = i
if d > y[i] and i < leftmost_hi': leftmost_hi' = i
result += count(i + 1, sum_so_far + d, leftmost_lo', leftmost_hi')
return result
Теперь мы имеем f(Y) = count(1, 0, n + 1, n + 1), и мы решили проблему. Мы можем добавить memoization функцию, чтобы сделать ее быстрой. Время выполнения - O (n 4) для этой конкретной реализации. На самом деле мы можем искусно оптимизировать идею, чтобы сделать ее O (n). Это остается как упражнение для читателя (Подсказка: вы можете сжать информацию, хранящуюся в leftmost_lo и leftmost_hi, в один бит, и вы можете обрезать, если sum_so_far > 60). Решение можно найти в конце этого сообщения.
Если вы внимательно смотрите, sum_so_far здесь просто пример произвольной функции, вычисляющей значение из цифровой последовательности X.
Это может быть любая функция, которая может быть вычислена цифрой по цифре и выводит достаточно небольшой результат. Это может быть произведение цифр, битовая маска набора цифр, которые выполняют определенное свойство или многое другое.
Он также может быть просто функцией, которая возвращает 1 или 0, в зависимости от того, содержит ли число только цифры 4 и 7, что разрешает второй пример тривиально. Мы должны быть немного осторожны, потому что нам разрешено иметь начальные нули в начале, поэтому нам нужно нести дополнительный бит через рекурсивные вызовы функций, говорящие нам, разрешено ли нам использовать нуль в качестве цифры.
Вычислить число f (Y) целых чисел X со свойством X ≤ Y и X является палиндромным
Это немного жестче. Нам нужно быть осторожным с ведущими нулями: зеркальная точка палиндромного числа зависит от того, сколько у нас ведущих нулей, поэтому нам нужно будет отслеживать количество ведущих нулей.
Существует несколько способов упростить это: если мы можем подсчитать f (Y) с дополнительным ограничением, чтобы все числа X должны иметь одинаковые цифры, такие как Y, тогда мы также можем решить исходную проблему, путем повторения всех возможных цифр и добавления результатов.
Итак, мы можем просто предположить, что у нас нет ведущих нулей:
count(i, leftmost_lo, leftmost_hi):
if i == ceil(n/2) + 1: # we stop after we have placed one half of the number
if leftmost_lo <= leftmost_hi:
return 1
else:
return 0
result = 0
start = (i == 1) ? 1 : 0 # no leading zero, remember?
for d := start to 9
leftmost_lo' = leftmost_lo
leftmost_hi' = leftmost_hi
# digit n - i + 1 is the mirrored place of index i, so we place both at
# the same time here
if d < y[i] and i < leftmost_lo': leftmost_lo' = i
if d < y[n-i+1] and n-i+1 < leftmost_lo': leftmost_lo' = n-i+1
if d > y[i] and i < leftmost_hi': leftmost_hi' = i
if d > y[n-i+1] and n-i+1 < leftmost_hi': leftmost_hi' = n-i+1
result += count(i + 1, leftmost_lo', leftmost_hi')
return result
Результат снова будет f(Y) = count(1, n + 1, n + 1).
ОБНОВЛЕНИЕ:. Если мы хотим не только подсчитать числа, но и, возможно, перечислим их или вычислим из них какую-то совокупную функцию, которая не раскрывает структуру группы, нам необходимо обеспечить соблюдение нижней границы X также во время рекурсии. Это добавляет еще несколько параметров.
ОБНОВЛЕНИЕ 2: O (n) Решение для примера "цифра суммы 60":
В этом приложении мы поместим цифры слева направо. Поскольку нас интересует только то, имеет ли значение leftmost_lo < leftmost_hi, добавим новый параметр lo. lo истинно iif leftmost_lo < i и false в противном случае. Если lo истинно, мы можем использовать любую цифру для позиции i. Если это ложь, мы можем использовать цифры 0 только для Y [i], так как любая более крупная цифра вызывает leftmost_hi = i < leftmost_lo и поэтому не может привести к решению. Код:
def f(i, sum_so_far, lo):
if i == n + 1: return sum_so_far == 60
if sum_so_far > 60: return 0
res = 0
for d := 0 to (lo ? 9 : y[i]):
res += f(i + 1, sum + d, lo || d < y[i])
return res
Возможно, этот способ взгляда на это несколько проще, но также немного менее явный, чем подход leftmost_lo/leftmost_hi. Он также не работает сразу для нескольких более сложных сценариев, таких как проблема палиндрома (хотя его также можно использовать там).