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

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

a1x1+a2x2+...+anxn=k,

(1)

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

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

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

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

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

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

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

Значение 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