Форум на Исходниках.RU

Перебор всех вариантов (сочетание ног насекомых)

Akina — Fri, 21 Feb 2020 20:16:18 +0000

Akina: Да я вообще не понимаю твоей заморочки по оптимизации учебной задачи с жёстко фиксированным (применение которого в данном конкретном случае есть явный [censored]) алгоритмом.

Перебор всех вариантов (сочетание ног насекомых)

FasterHarder — Fri, 21 Feb 2020 13:58:23 +0000

FasterHarder: тут с К все ок
из условия следует, что x, y, K - натуральные числа

вот, что делать с 11.5 милл.переборов (в худшем случае), хотя может это и не критично. Прогнал проггу на десятках миллионах N, результат появился сразу (там что-то получилось насекомых 235 000).

Перебор всех вариантов (сочетание ног насекомых)

Akina — Fri, 21 Feb 2020 12:11:56 +0000

Akina:

Цитата FasterHarder @ 21.02.20, 10:43

// наличие хотя бы одного жука и 1 паука гарантировано

Для этого достаточно ненулевого K. Если жуков ноль - К не существует (деление на ноль), если пауков ноль, то К=0.

При условии, что решение существует, конечно...

Перебор всех вариантов (сочетание ног насекомых)

FasterHarder — Fri, 21 Feb 2020 10:43:01 +0000

FasterHarder:

Цитата amk @ 21.02.20, 09:46

к примеру, можешь перебрать все возможные количества жуков, от нуля и до того, как число ног у жуков будет больше N.

я, кажись, понял, да, действительно, достаточно запустить лишь цикл по одним насекомым, а вторых искать в зависимости от первых...
только НЕ от НУЛЯ, а от 1, т к кол-во ног насекомых - натуральные...ноги1 * K = ноги2

Цитата amk @ 21.02.20, 09:46

Если задача решается, значит все частные ОБЯЗАНЫ быть целыми.

да, согласен, дробные "ноги" не рассматриваем, хотя еще подумаю потщательнее этот момент...

Цитата amk @ 21.02.20, 09:46

Ну и N должно нацело делиться на 6*(K + 1)

это я закладывал и понимаю, просто не стал писать, т к это не влияет на кол-во переборов, просто, если не делится, то сразу ответ 0.

в общем, вроде понятно, спс amk!

P.S. еще были мысли, что нужно что-то мутить с разложением на простые делители N, K и пр., но ведать не придется, ну и хорошо!

Добавлено 21.02.20, 11:10
вот прожка на с++, вроде все ОКейно!

#include <iostream>

using namespace std;

int main(void)

{

long long K, N;

long long result = 0;

cin >> N >> K;

if(N % (6*K + 6) == 0)

{

// наличие хотя бы одного жука и 1 паука гарантировано

for(long long x = 1; 6*x + 8 <= N; x++)

if((6*x + 6*x*K) == N)

{

result = x + 6*x*K/8;

break;

}

cout << endl << result << endl;

fflush(stdin);

cin.get();

return 0;

}

т е предельное число переборов составляет (N - 8)/6. Кстати, N может на входе достигать 100 миллионов...(100 млн - 8)/6 примерно 11.5 млн переборов. Много это или мало, а черт его знает...но кажется, что многовато и нужна еще какая-то оптимизация.

Перебор всех вариантов (сочетание ног насекомых)

amk — Fri, 21 Feb 2020 09:46:38 +0000

amk: Ну, к примеру, можешь перебрать все возможные количества жуков, от нуля и до того, как число ног у жуков будет больше N.
Далее подсчитываешь число ног жуков и пауков (6x и 6x*K) и сравниваешь их сумму с N. В принципе, если на этот момент суммарное число ног превысит N, то задача не сходится.

И кстати, в твоём решении незачем брать натуральные снизу. Если задача решается, значит все частные ОБЯЗАНЫ быть целыми.
Ну и N должно нацело делиться на 6*(K + 1)

Перебор всех вариантов (сочетание ног насекомых)

FasterHarder — Fri, 21 Feb 2020 08:44:38 +0000

FasterHarder: Всем хай! Сходу к делу!
Условие задачи следующее: на берегу океана сидят и курят жуки и пауки, у которых вместе N ног. У каждого жука по 6 ног, а паука - 8 ног. Известно, что ног у всех жуков в К раз меньше, чем у всех пауков.
Сколько всего жуков и пауков находится на берегу океана? N и К - натуральные числа. Если решений нет - выдать ответ ноль.

строим мат.модель!
х - кол-во жуков, y - кол-во пауков
6х - всего ног у всех жуков
8y - всего ног у всех пауков

6x + 8y = N (1 необходимое условие)
6x * K = 8y (2 необходимое условие)

6x + 6x*K = N
6x(1 + K) = N
x = N / (6 + 6K)
все, ГОТОВО. Данное уравнение имеет однозначное решение (если будет натуральное Х) иначе - нет решения.
Проверим, пусть N = 360, K = 2.
x = 360 / (6*3) = 360 / 18 = 20
y = 6*20*2/8 = 30
Итого: 20 + 30 = 50

но есть одно НО(!), нужно решить задачу МЕТОДОМ ПОЛНОГО ПЕРЕБОРА.
Что перебирать? ну, наверное {x, y}.
Какие допустимые значения перебора х и y? Очевидно, что X(min) = Y(min) = 1.
Нужно делать оценку допустимости X(max), Y(max).
X(max) будет макс. при минимальном Y = 1.
6*X(max) + 8 = N
X(max) <= (N - 8)/6 - берем ближайшее натуральное снизу.

Y(max) будем макс. при минимальном X = 1.
6 + 8*Y(max) = N
Y(max) <= (N - 6)/8 - берем ближайшее натуральное снизу.

В итоге получаются такие переборы, да?
for(x = 1 to X(max))
for(y = 1 to Y(max))
здесь подставляем текущие {x; y} в ОБА условия. Если выполнилось - ответ найден. Дальше можно не проверять, т к решение единственное (если оно есть)

но есть еще одно НО(!), при возможности, нужно сократить варианты переборов (не до единственного).
и вот у меня вопрос, здесь за счет чего варианты перебора можно сократить??

добавить в эти циклы проверку
for(x = 1 to X(max))
for(y = 1 to Y(max))
if(6x * K != 8Y) // дальше не считаем
но вроде это НЕ сокращает варианты перебора...значения x, y также бегают от 1 до (max).

Очень простая задача с очень странными требованиями решения через полный перебор, да, понимаю)
подскажите как быть-то