Алгоритм определения существования решения с неотрицательными значениями для линейного диофантового уравнения

Question

Я ищу метод, чтобы определить, есть ли решение для уравнений, таких как:3n1 + 4n2 + 5n3 = 456, где n1,n2,n3 являются положительными целыми числами.

Или более общий: существуют ли нулевые или положительные целые числа n1,n2,n3..., которые решают уравнение k1n1+k2n2+k3n3...=m, где k1, k2, k3... и m являются известными положительными целыми числами.

Мне не нужно искать решение - просто чтобы определить, существует ли решение.

Редактировать:

Что касается практического использования этого алгоритма:

В коммуникационной библиотеке я хочу решить, является ли данное сообщение действительным в соответствии с его размером, прежде чем обрабатывать сообщение. Например: я знаю, что сообщение содержит ноль или более 3-байтовых элементов, ноль или более 4-байтовых элементов и ноль или более 5-байтовых элементов. Я получил сообщение размером 456 байт, и я хочу определить его достоверность, прежде чем проводить дальнейшую проверку его содержимого. Конечно, заголовок сообщения содержит количество элементов каждого типа, но я хочу сделать первую проверку на уровне коммуникационной библиотеки, передавая что-то вроде pair<MsgType,vector<3,4,5>>,

Answer 1

Вы спрашиваете, если регулярное выражение

(Ххх | хххх | ххххх)*

соответствует xx... x, где x встречается 456 раз.

Вот решение в O(n+a^2), где a - наименьшее из чисел на левой стороне (в данном случае 3).

Предположим, что ваши цифры 6,7,15. Я назову номер, который можно выразить в виде 6x+7y+15z "доступно". Вы должны проверить, доступен ли данный номер.

Если вы можете получить какое-то число n, то, конечно, вы сможете получить n+6, n+12, n+18 - в общем случае, n+6k для всех k >= 0. С другой стороны, если вы не можете получить некоторое число n, тогда n-6, безусловно, тоже недоступен (если вы могли бы получить (n-6), тогда (n-6)+6=n было бы доступно), это означает, что n-12, N-18, N-6K не доступны ни.

Предположим, вы определили, что 15 доступно, а 9 нет. В нашем случае 15=6*0+7*0+15*1, но никак не получит 9. Итак, согласно нашим предыдущим рассуждениям, 15+6k доступно для всех k> = 0, а 9-6k для всех k> = 0 - нет. Если у вас есть какое-то число, которое разделено на 6, вы получите 3 как остаток (3, 9, 15, 21, ...), вы можете быстро ответить: числа <= 9 недоступны, числа>= 15 есть.

Для всех возможных остатков деления достаточно определить на 6 (то есть 0,1,2,3,4,5), какое наименьшее число доступно. (Я только что показал, что это число для остатка 3 - 15).

Как это сделать: создать граф с вершинами 0,1,2,3,4,5. Для всех заданных вам чисел k (7,15 - мы игнорируем 6) добавьте ребро из x в (x + k) mod 6. Присвойте ему вес (x + k) div 6. Используйте алгоритм Дейкстры, используя 0 в качестве начального узел. Найденные алгоритмом расстояния будут именно теми числами, которые мы ищем.

В нашем случае (6,7,15) число 7 дает 0 -> 1 (вес 1), 1 -> 2 (вес 1), 2 -> 3 (вес 1), ..., 5 -> 0 (вес 1) и число 15 дает 0 -> 3 (вес 2), 1 -> 4 (вес 2), ..., 5 -> 1 (вес 2). Кратчайший путь от 0 до 3 имеет одно ребро - его вес равен 2. Так что 6*2 + 3 = 15 - это наименьшее число, которое дает 3 в качестве остатка. 6*1 + 3 = 9 недоступно (ну, мы проверяли это ранее вручную).

А какая связь с регулярными выражениями? Ну, каждое регулярное выражение имеет эквивалентный конечный автомат, и я построил один из них.

Эта проблема с разрешением нескольких запросов появилась на польской олимпиаде, и я перевел решение. Теперь, если вы слышите, как человек говорит, что информатика бесполезна для настоящих программистов, бейте его по лицу.

Answer 2

В соответствии с этим, если наибольший общий множитель {n1, n2, n3, ...} не является делителем m, то у вас нет решения. На этой странице показан пример просто {n1, n2}, но он распространяется на более крупные системы. Новая проблема - написание алгоритма для нахождения наибольшего общего фактора, но это тривиально в свете исходной проблемы.

Таким образом, часть вашего алгоритма найдет gcf({n1,n2,...}), а затем посмотрит, является ли он фактором m. Если это не так, то никакого решения не существует. Это не полностью показывает, что решение существует, но оно может быстро показать вам, что не существует, что все еще полезно.

Answer 3

Это связано с проблемой монет Фробениуса, которая не была решена при n>3.

Answer 4

Похоже, вы говорите о системе неравенств с целочисленными ограничениями. Реальность такова, что вы решаете эту систему:

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

И дополнительное ограничение, что n1, n2, n3 являются целыми числами. Это проблема линейного программирования. К сожалению для вас, общий случай решения такой системы с целочисленными ограничениями является NP-полным. Однако есть много алгоритмов, которые решат это за вас.

Answer 5

Вот кое-что на случай 2 номера. Я еще не понял, как его масштабировать:

Учитывая 2 относительно простых целых числа x и y, существуют такие положительные целые числа a и b, что ax+by=c для всех c>=(x-1)(y-1)

В основном это работает, потому что, если вы предполагаете, x<yВы можете выразить все целые числа mod x с помощью (0, y, 2y, 3y, ..., (x-1)y). Теперь, добавив некоторое положительное кратное x, вы можете получить все целые числа между [(x-1)(y-1),(x-1)y], как и все целые числа между (x-1) (y- 1) и (x-1) y-1 были выражены ранее.

1. НОД (х, у). Если c не кратно, вернуть false.
2. если GCD(x,y)> 1, разделить x, y, c на GCD
3. Если c> (x-1) (y-1), вернуть true
4. Остальное грубая сила

И для грубой силы:

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false

Answer 6

Подход методом перебора (псевдокод):

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

Смотрите также http://mail.python.org/pipermail/python-list/2000-April/031714.html

РЕДАКТИРОВАТЬ: В коммуникационной библиотеке это не имеет смысла, поскольку она должна работать немедленно. В приложении ОП я бы, вероятно, использовал какой-то хэш, но его подход звучит интересно.

Answer 7

Возможно, следующая информация не имеет значения, потому что она не обрабатывает общую ситуацию, но...

Если проблема состоит в том, чтобы определить, может ли данное положительное целое число K быть сформировано как сумма 3*n1 + 4*n2 + 5*n3для неотрицательных целых чисел n1, n2, n3 ответ "да" для K >= 3.

Известный учебник Розена Дискретная математика и ее приложения, с. 287 из шестого издания, доказывает, что "каждая сумма почтовых сборов в 12 центов или более может быть сформирована с использованием только марок 4 цента и 5 центов", используя индукцию.

Основным шагом является то, что почтовая оплата 12 центов может быть сформирована с 3 печатями по четыре цента.

Шаг индукции считает, что если P(k) является истинным с использованием марок с четырьмя центами, то просто замените печать с четырьмя центами на печать с пятью центами, чтобы показать, что P(k+1) является истинным. Если P(k) истинно, не используя штампов с четырьмя центами, то, поскольку k>=12, нам нужно по крайней мере 3 штемпеля по пять центов, чтобы сформировать нашу сумму, и 3 штемпеля по пять центов можно заменить на 4 штрафа по четыре цента. штампы для достижения k+1.

Чтобы расширить вышеупомянутое решение для этой проблемы, нужно просто рассмотреть еще несколько случаев.