Можно ли это решить, составить формулу/алгоритм?

Question

[Александр Керзаков]

Задача про монахов
Имеется 3 группы монахов: ведущие, простые, ученики. M монахов едят N пирогов по чину.
Ведущий по N1 пирогов, простой по N2 пирогов, ученики по N3 пирогов (N, N1, N2, N3 - могут быть целыми и дробными числами).
Сколько было монахов: ведущих (M1), простых (M2) и учеников (M3).
Исходные данные
M - количество монахов всего
N - количество пирогов всего
N1 - количество пирогов, съедаемым одним ведущим монахом
N2 - количество пирогов, съедаемым одним простым монахом
N2 - количество пирогов, съедаемым одним монахом-учеником
Результаты
M1 - количество ведущих монахов
M2 - количество простых монахов
M3 - количество монахов-учеников

Comments

[sim3x]

добавь свой алгоритм, чтоб не попасть "под задание, а не вопрос"

[Александр Керзаков]

sim3x: я не решил. Мне достаточно если ответят "можно".

Answer 1

[uvelichitel]

Для каждого M1 от 0 до N/N1
    M2 = (N - M1*N1 -M*N3 + M1*N3) / (N2 - N3)
    M3 = M - M1 - M2
        если M2 целое число и М3>0
            то вернуть ответ М1, М2, М3

Comments

[Александр Керзаков]

не могли бы Вы прокомментировать первую строчку, слегка непонятно.

[Александр]

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

[Александр Керзаков]

Александр: Извиняюсь =) Может вы её прокомментируете?

[Александр]

Попытаюсь:
Для каждого - это значит действие будет повторяться несколько раз ( N/N1 ) - тоесть вы получите несколько систем уравнений которые могут иметь решение. При этом он учел что M1 не может быть больше N/N1, что косвенно задано начальными условиями.

Answer 2

[SagePtr]

В данном виде - решить нельзя, так как в условии не сказано, как выходные данные зависят от входных. И не указано, что означают переменные М и П.

Comments

[Александр Керзаков]

Упс. Внесу поправочки.

[SagePtr]

А если так, как я понимаю, получается вот так:
М1 * П1 + М2 * П2 + М3 * П3 = П
М1 + М2 + М3 = М
Система уравнений с тремя неизвестными, но только двумя уравнениями. Слишком мало уравнений получается, вариантов решения может быть много.
Хотя с другой стороны, в целых числах может быть и одно решение.
При генерации входных данных тщательно проверяйте, чтобы целочисленное решение было одно.

[Александр Керзаков]

SagePtr: всё как вы понимаете, но решение должно быть однозначным :c При чём одним циклом :c

Answer 3

[Александр]

Можно двумя вложенными циклами - перебираем М1 и М2, а М3 находим из системы уравнений.
M1 + M2 + M3 = М
М1*П1 + М2*П2 + М3*П3 = П

Comments

[Александр Керзаков]

Но ведь мы не сможем перебрать эти числа, не зная значения М3.

[Александр]

3 неизвестных, 2 мы перебираем и получаем систему уравнений с 1 неизвестной - которую любой школьник сможет решить.

[Александр Керзаков]

Мы ведь не сможем проверить, верно или нет перебрали без значения M3... Я об этом.

[Александр]

вот:
M = 100, M1 = 5, M2 = 50 ; M3 = M - M1 - M2 = 45 правильно?
подставляем 45 во второе уравнение и если общее количесво полученное равно общему количесву заданному - то это одно из решений. и так подставляя вместо М1 и М2 числа от 1 до M

Тоесть для М1 = 1 меняем М2 от 1 до М, потом для M1 = 2 меняем М2 от 1 до М - каждый раз проверяем подходят ли эти значения, если подходят сохраняем их к вариантам решений

P.S. я себя чувствую дебилом уже...

[Александр Керзаков]

Александр: это в три цикла, получается?

Answer 4

[tzlom]

тут вопрос в условии, если читать буквально, то система уравнений такая:
N = N1*M1 + N2*M2 +N3*M3
M = M1 + M2 + M3
M1>=0
M2>=0
M3>=0
очевидно - её можно решить, но решений может быть больше 1го
тривиальный алгоритм - перебором всех возможных M1,M2,M3

Comments

[Александр Керзаков]

В итоге 4 цикла, из них 3 вложенных? Или можно короче?