Линейное уравнение с 3 переменными в C

Мне дали домашнее задание класса C, а именно:

Трасса Hyperloop строится из отдельных отрезков трубы определенной длины. Трасса начинается и заканчивается переборкой, и между каждыми двумя сегментами трубы есть переборка. Сегменты производятся двумя разными производителями (s1 и s2). Даны длины сегментов (s1, s2), переборок (b) и желаемого пути (l). Задача состоит в том, чтобы разработать функцию, которая будет на основе этих 4-х параметров решать, существуют ли допустимые комбинации отрезков и переборок, которые приведут к точной длине искомого пути, и, если они есть, выводить количество этих комбинаций .

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

Мое мнение, что я должен решить линейное уравнение с 3 переменными:

(m)*s1 + (n)*s2 + (m+n+1)*b = l

Но я понятия не имею, какой метод мне следует использовать для написания эффективного кода.


c algorithm math linear-equation equation-solving
person Aydin Misirzadeh    schedule 15.11.2018    source источник
comment
У линейных уравнений с тремя переменными нет конечного решения   -  person Thecave3    schedule 15.11.2018
comment
Ясно, что m и n должны быть целыми неотрицательными числами. Существуют ли какие-либо ограничения на заданные значения s1, s2, b и l, кроме того, что они неотрицательны? Будут ли они целыми, рациональными числами или просто действительными числами? Если целые числа, это хорошо изученная проблема диофантовых уравнений. Если рациональные числа, умножив уравнение на наименьший общий знаменатель, вы получите целое число. Ограничения будут определять ваш подход. Что вы знаете о диофантовых линейных уравнениях с двумя переменными?   -  person Rory Daulton    schedule 15.11.2018
comment
@ Thecave3: я вижу только две переменные, m и n. Какую третью переменную вы видите? И если данные константы являются рациональными числами, а m и n должны быть целыми неотрицательными числами, то будет только конечное число решений (возможно, ни одного).   -  person Rory Daulton    schedule 15.11.2018
comment
@RoryDaulton Спасибо за ваше замечание. Да, длины неотрицательные целые числа. Я не знаком с диофантовыми уравнениями, но сейчас вернусь к этой теме. Спасибо за совет.   -  person Aydin Misirzadeh    schedule 15.11.2018
comment
Вероятно, вам следует обратить внимание на Расширенный алгоритм Евклида как на важную часть вашего решения.   -  person Rory Daulton    schedule 15.11.2018
comment
Не беспокойтесь об эффективном коде. Заставьте его работать, заставьте его работать правильно, заставьте его работать быстро. Это правильный порядок.   -  person duffymo    schedule 15.11.2018
comment
Это Progtest домашнее задание от Programming and algorithmics 1 в CVUT (Чешский технический университет). Этот вопрос был задан, когда домашнее задание было еще открыто для сдачи.   -  person Elliott    schedule 25.07.2021

Ответы (2)


arrow_upward
0
arrow_downward

Уравнение предоставляет критерии для поиска комбинаций. При написании кода C для этого потребуется только итерация для m и n и проверка, соответствует ли длина l. Ниже приведен псевдокод, который может предоставлять комбинации

for m = 0 to l/s1
for n = 0 to l/s2
bnum = m + n - 1
if (m*s1 + n*s2 + bnum*b) == l)
print m, n, bnum
person anand    schedule 15.11.2018

arrow_upward
0
arrow_downward

Прежде всего, взгляните на свой строительный проект иначе:

  • Вы должны начать с переборки.
  • После этого каждая труба должна иметь переборку после нее.

Таким образом, вам нужно построить трассу длиной l-b из труб длиной m+b и n+b.

Перераспределите факторы, и вы обнаружите, что у вас есть уравнение с двумя переменными, а не с тремя:

(m+b)*s1 + (n+b)*s2 = l-b

Без ограничения общности предположим, что s2 > s1. Для вашего трека потребуется как минимум (нижняя граница) столько сегментов трубы, достаточно более длинного, чтобы достичь по крайней мере требуемой длины трека.

ceil( (l-b) / (n+b) )

и не более (верхняя граница), чем

floor( (l-b) / (m+b) )

Вы можете переборщить итеративное решение:

  • решить уравнение относительно s2
  • итерация s1 по указанному выше диапазону
  • для каждого значения s1 проверьте, является ли s2 целым числом. Если да, запишите решение.

Это просто, но не элегантно. На самом деле, вы захотите использовать соответствующую работу над линейными диофантовыми уравнениями, чтобы параметризовать все решения с помощью s1, s2 >= 0.

person Prune    schedule 15.11.2018
comment
@RoryDaulton Спасибо - я начал с одного решения, в котором они были взаимозаменяемы, и забыл удалить его, когда нашел лучшее решение, основанное на длине трубы. - person Prune; 19.11.2018