Алгоритм исключения чисел

Ответ 1

Вы не указали базу, но я буду считать десятичным без потери общности.

Во-первых, признайте, что это строковая проблема, а не числовая.

Построить конечный автомат A, чтобы распознать 50 целых чисел в качестве подстрок других строк. Например, два целых числа 44 и 3 распознаются как подстроки с помощью RE

^.*(44|3).*$

Построить конечный автомат B, чтобы распознать все числа, меньшие N. Например, распознать от 1 до 27 (включительно) в десятичной форме, что может быть достигнуто путем компиляции RE

^([1-9]|1[0-9]|2[0-7])$

Вычислим пересечение C автоматов A и B, которое, в свою очередь, является FA.

Используйте алгоритм динамического программирования для вычисления размера языка, распознанного C. Вычтите, что из размера языка, распознанного A, вычисляется по тому же алгоритму.

(Я не утверждаю, что это асимптотически оптимально, но он был достаточно быстрым, чтобы решить множество проблем Project Euler:)

Ответ 2

Это только объяснение того, что уже писали ларсманы. Если вам нравится этот ответ, пожалуйста, проголосуйте за него.

Конечный автомат FA - это просто набор состояний и правила, говорящие, что если вы находитесь в состоянии S, а следующий символ, который вы подаете, c, вы переходите к состоянию T. Два государства являются особыми. Один из них означает "начать здесь", а другой означает "я успешно совпадал". Один из символов является особым, и означает "только что закончившаяся строка". Таким образом, вы берете строку и конечный автомат, начинаете в исходном состоянии, продолжаете кормить персонажей в машине и меняете состояния. Вы не можете соответствовать, если вы дадите какой-либо непредвиденный ввод состояния. Вам удастся совпадение, если вы когда-либо достигли состояния "Я успешно сопоставлен".

Теперь существует хорошо известный алгоритм преобразования регулярного выражения в конечный автомат, который соответствует строке тогда и только тогда, когда это регулярное выражение совпадает. (Если вы читали о регулярных выражениях, так работают DFA-движки.) Чтобы проиллюстрировать, я буду использовать шаблон ^.*(44|3).*$, который означает "начало строки, любое количество символов, за которыми следуют либо 44, либо 3, после чего любым количеством символов, за которым следует конец строки."

Сначала обозначим все позиции, в которых мы можем находиться в регулярном выражении, когда мы ищем следующий символ: ^ A .*(4 B 4|3) C .*$

Состояние нашего механизма регулярных выражений будет подмножеством этих позиций, а особое состояние будет соответствовать. Результатом перехода состояния будет множество состояний, к которым мы могли бы добраться, если бы мы были в этом положении, и увидели конкретный характер. Наша начальная позиция находится в начале RE, которая является {A}. Вот состояния, которые могут быть достигнуты:

S1: {A}   # start
S2: {A, B}
S3: {A, C}
S4: {A, B, C}
S5: matched

Вот правила перехода:

S1:
  3: S3
  4: S2
  end of string: FAIL
  any other char: S1
S2:
  3: S3
  4: S3
  end of string: FAIL
  any other char: S1
S3:
  4: S4
  end of string: S5 (match)
  any other char: S3
S4:
  end of string: S5 (match)
  any other char: S4

Теперь, если вы берете любую строку, запустите ее в состоянии S1 и следуйте правилам, вы будете соответствовать этому шаблону. Процесс может быть долгим и утомительным, но, к счастью, он может быть автоматизирован. Я предполагаю, что larsmans автоматизировал его для собственного использования. (Техническое примечание: расширение от "позиций в RE" до "наборов позиций, в которых вы, возможно, находитесь", может выполняться либо спереди, либо здесь, либо во время выполнения. Для большинства REs лучше сделать это спереди, как здесь. Но крошечная часть патологических примеров завершится очень большим числом состояний, и лучше будет делать это во время выполнения.)

Мы можем сделать это с любым регулярным выражением. Например, ^([1-9]|1[0-9]|2[0-7])$ может быть помечен: ^ A ([1-9]|1 B [0-9]|2 C [0-7]) D $ и мы получим состояния:

T1: {A}
T2: {D}
T3: {B, D}
T4: {C, D}

и переходы:

T1:
  1: T3
  2: T4
  3-9: T2
  any other char: FAIL
T2:
  end of string: MATCH
  any other char: FAIL
T3:
  0-9: T2
  end of string: MATCH
  any other char: FAIL
T4:
  0-7: T2
  end of string: MATCH
  any other char: FAIL

ОК, поэтому мы знаем, что такое регулярное выражение, какой конечный автомат и как они соотносятся. Что такое пересечение двух конечных автоматов? Это просто конечный автомат, который совпадает, когда оба конечных автомата индивидуально совпадают, а в противном случае не совпадают. Легко построить, его множество состояний - это всего лишь множество пар состояния в одном, а состояние в другом. Его правило перехода заключается в том, чтобы просто применять правило перехода для каждого члена независимо, если либо не выполняется целое, если оба они совпадают.

В приведенной выше паре фактически выполняем пересечение на число 13. Мы начинаем в состоянии (S1, T1)

state: (S1, T1)  next char: 1
state: (S1, T3)  next char: 3
state: (S3, T2)  next char: end of string
state: (matched, matched) -> matched

И затем на номер 14.

state: (S1, T1)  next char: 1
state: (S1, T3)  next char: 4
state: (S2, T2)  next char: end of string
state: (FAIL, matched) -> FAIL

Теперь мы переходим к этому. Учитывая конечные конечные автоматы, мы можем использовать динамическое программирование, чтобы выяснить, сколько строк есть, которые соответствуют ему. Вот этот расчет:

0 chars:
  (S1, T1): 1
    -> (S1, T3): 1 # 1
    -> (S1, T4): 1 # 2
    -> (S3, T2): 1 # 3
    -> (S2, T2): 1 # 4
    -> (S1, T2): 5 # 5-9
1 chars:
  (S1: T2): 5      # dead end
  (S1, T3): 1
    -> (S1, T2): 8 # 0-2, 5-9
    -> (S2, T2): 1 # 3
    -> (S3, T2): 1 # 4
  (S1, T4): 1
    -> (S1, T2): 6 # 0-2, 5-7
    -> (S2, T2): 1 # 3
    -> (S3, T2): 1 # 4
  (S2, T2): 1      # dead end
  (S3, T2): 1
    -> match:    1 # end of string
2 chars:
  (S1, T2): 14     # dead end
  (S2, T2): 2      # dead end
  (S3, T2): 2
    -> match     2 # end of string
  match:    1
    -> match     1 # carry through the count
3 chars:
  match:    3

Хорошо, что много работы, но мы обнаружили, что есть три строки, которые соответствуют обоим этим правилам одновременно. И мы сделали это таким образом, чтобы это было автоматически и масштабируемо для гораздо большего числа.

Конечно, вопрос, который мы изначально задавали, заключался в том, сколько из них соответствует второму, но не первому. Хорошо, что мы знаем, что 27 соответствуют второму правилу, 3 соответствуют обоим, поэтому 24 должен соответствовать второму правилу, но не первым.

Как я уже говорил, это просто решение larsmans выяснено. Если вы что-то узнали, поддержите его, проголосуйте за его ответ. Если этот материал звучит интересно, купите книгу, такую ​​как Progamming Language Pragmatics, и узнайте больше о конечных автоматах, синтаксическом разборе, компиляции и т.п. Это очень хороший набор навыков, и слишком много программистов этого не делают.