Nickolay.info. PHP. LDE (Linear Diofant Equation) - сервис для решения линейных диофантовых уравнений

Nickolay.info. PHP. Статьи. LDE (Linear Diofant Equation) - сервис для решения линейных диофантовых уравнений

Сколько есть способов набрать определённую денежную сумму монетами нескольких заданных номиналов? Можно ли придумать другие месяцы для года из 365 дней? Как распределить 20 человек по 3 участкам работ и сколько есть способов это сделать?

На эти и множество других подобных вопросов можно ответить, решив линейное диофантово уравнение вида

a₁x₁+a₂x₂+...+a_nx_n=k,

(1)

где a_i - заданные коэффициенты, k - правая часть уравнения, та самая денежная сумма или продолжительность года, а x_i - неизвестные величины.

О диофантовых уравнениях на сайте уже упоминалось вот здесь, там же вы можете прочитать об их неразрешимости в общем виде.

Для решения уравнения (1) с ненулевыми положительными целыми коэффициентами a_i и целым k>1 я сейчас написал небольшой сервис, так как нужно было посмотреть "в работе" подобную задачу.

Целочисленные положительные коэффициенты a_i вводятся в форму через пробел или запятую. Нули или значения a_i>k исключаются из данных, коэффициенты a_i автоматически сортируются по возрастанию. Очевидно, что решать с a_i=0 или a_i>k было бы бессмысленно, это означало бы лишь то, что в решение всегда входит 0 объектов какого-то вида.

Решение менее, чем с двумя различными коэффициентами a_i также не выполняется, ведь с одним коэффициентом решение всегда тривиально.

С коэффициентами a_i<0 решение теоретически возможно, но здесь отключено, так как алгоритм основан на предположении, что все числа положительны. Да и задач таких большинство.

Скрипт автоматически сортирует коэффициенты a_i по возрастанию (от перестановки мест слагаемых сумма не меняется, а так удобнее).

Значение k также должно быть целым и k>1, иначе решать нечего. При необходимости k корректируется в заданных скриптом пределах от 2 до 99999. Ограничение сверху связано с желанием, чтобы время на перебор не оказалось слишком большим. Да, метод решения - перебор, вот весь алгоритм для корректных данных (PHP):

//Число коэффицентов равно n, такова же размерность массивов $a, $b, $c
//Массив $b заполнен по правилу:
for ($i=0; $i<$n; $i++) $b[$i]=(int)($k/$a[$i]);
//Массив $c заполнен нулями

do { //Начало цикла перебора
 $s=0;
 for ($i=0; $i<$n; $i++) $s+=$a[$i]*$c[$i];
 if ($s==$k) { //Вывод очередного решения c[i]
 }
 $found = false;
 for ($i=$n-1; $i>-1; $i--) {
  if ($c[$i]==$b[$i]) for ($j=$i; $j<$n; $j++) $c[$j]=0;
  else { $c[$i]++; break; }
 }
 if ($i<0) $found = true;
} while (!$found); //Конец цикла перебора

Сервис в работе

Исходник сервиса, всё в одном файле (2 Кб)

Вот примеры использования сервиса для "глубоко практических" задач :)

Возможные комбинации месяцев из 28-31 дней для года из 365 дней (полные результаты)

Способы набрать рубль монетами в 1, 5, 10 и 50 копеек (результаты без нулей)

Способы разбить 20 человек на двойки и тройки людей (только ответы x[i])

Способы 3 человекам разойтись по 3 пивбарам :)

Как видно из URL-адресов этих примеров, обращаться к сервису можно и через командную строку (методом GET), в этом случае параметры таковы:

a - список коэффициентов через запятую;
k - значение из правой части уравнения;
r=1 - чтобы сразу решилось при вызове, иначе параметра r не надо
v=1 или v=2 или v=3 - способ вывода, то есть, решения целиком, решения без нулей или только ответы x[i]

гостевая; E-mail