Логические задачи.

[burning_LEGION]

Есть бензиновоз с цистерной ёмкостью 1000л и 4000л бензина на складе. Бензин надо перевезти в удалённую деревню до которой 1000км. Бензиновоз расходует этот же бензин 1 литр на километр. Он может ездить и вперёд и назад, оставлять бензин в произвольной точке пути, потом забирать его. Сколько бензина он может довезти до деревни?

1к, которая ему нужна чтобы вернуться)

 

[avbua]

1к, которая ему нужна чтобы вернуться)

возвращаться он не собирается, его там распилят на металлолом, так как мало в него влазит и много ест.

 

[burning_LEGION]

возвращаться он не собирается, его там распилят на металлолом, так как мало в него влазит и много ест.

зато он сосет бенз прямо с груза

 

[sobutilnik]

Есть бензовоз с цистерной ёмкостью 1000л и 4000л бензина на складе. Бензин надо перевезти в удалённую деревню до которой 1000км. Бензовоз расходует этот же бензин 1 литр на километр. Он может ездить и вперёд и назад, оставлять бензин в произвольной точке пути, потом забирать его. Сколько бензина он может довезти до деревни?

375 литров

 

[crghome]

375 литров

541.5 литра

логика рассуждений:
-нам необходимо сделать минимальное количество ходок, в одну и другую сторону;
-за основу берем 1000 л., который влазят в машину;
-значит для перевозки всего груза, в новую точку, на расстояние Х, ему необходимо сделать 4000 / 1000 = 4 ходки, и правильнее считать в двойном размере, т.е. 8 поездок (бензин же на обратном пути тоже кушается);
-таким образом получим зависимость (сори Delphi):
if V > 1000 then X = 1000 / 4
if V > 2000 then X = 1000 / 6
if V > 3000 then X = 1000 / 8
-таким не хитрым расчетом мы получим следующие расстояния:
3000 л. перевозим на 125 км. с затратами 1000 л., далее
1998 л. - на 167 км. с затратами 1002 л., далее
1000 л. - на 249,5 с затратами 998 л., далее
у нас останется 1000 л, и расстояние в 1000 - 125 - 167 - 249,5 = 458,5 км, его проезжаем за один проезд и привозим 1000 - 458,5 = 541,5 л

 

[Kakashkin]

Есть бензовоз с цистерной ёмкостью 1000л и 4000л бензина на складе. Бензин надо перевезти в удалённую деревню до которой 1000км. Бензовоз расходует этот же бензин 1 литр на километр. Он может ездить и вперёд и назад, оставлять бензин в произвольной точке пути, потом забирать его. Сколько бензина он может довезти до деревни?

Бензина-то сколько на складе изначально?

 

[crghome]

Kakashkin
Есть бензовоз с цистерной ёмкостью 1000л (вот здесь должна быть запятая) и 4000л бензина на складе.

 

[Kakashkin]

примерно 676л

Чтобы переместить весь бензин на 1км, начиная от склада, надо 7 ходок по 1 км. Через 1000/7 км понадобится уже 5 ходок по 1 км. Ещё через 1000/5 км понадобится 3 ходки по 1 км. В конце концов, через 1000/3 км понадобится всего 1 ходка, т.е. грубо говоря, мы довезем 1000 л на растояние 1000(1/7 + 1/5 + 1/3) = 676 км, а значит в деревню прибудет 676 л.

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

Kakashkin
Есть бензовоз с цистерной ёмкостью 1000л (вот здесь должна быть запятая) и 4000л бензина на складе.

Это да, ещё было бы неплохо в вопросе написать "какое _максимальное_ количество бензина" а не просто "Сколько бензина он может довезти до деревни?"

и правильнее считать в двойном размере, т.е. 8 поездок

Ещё правильнее считать, как 7 поездок Ведь последний раз обратно ехать не надо

 

[avbua]

примерно 676л

Чтобы переместить весь бензин на 1км, начиная от склада...

Примерно правильно, только нет смысла перевозить бензин по 1 км, проще превозить до той точки, до которой потратится 1000л.

1. Таким образом, если у нас 4000л, то до первой точки нам надо довести 3000л, значит сделать 4 ходки туда и 3 обратно. 1000/7= почти 143км
2. До следующей точки нам надо довести 2000л, 3 ходки туда и 2 обратно, 1000/5=200км
3. До предпоследней точки нам надо довести 1000л, это две ходки туда и 1 обратно, 1000/3= 333км

Итого мы уже проехали 143+200+333= 676км

4. Стартуем с этой точки с полной цистерной и довозим 676литров

 

[Kakashkin]

Примерно правильно, только нет смысла перевозить бензин по 1 км, проще превозить до той точки, до которой потратится 1000л.

1. Таким образом, если у нас 4000л, то до первой точки нам надо довести 3000л, значит сделать 4 ходки туда и 3 обратно. 1000/7= почти 143км
2. До следующей точки нам надо довести 2000л, 3 ходки туда и 2 обратно, 1000/5=200км
3. До предпоследней точки нам надо довести 1000л, это две ходки туда и 1 обратно, 1000/3= 333км

Итого мы уже проехали 143+200+333= 676км

4. Стартуем с этой точки с полной цистерной и довозим 676литров

Да, но как вы докажете, что нет варианта перевезти больше, используя ваш подход? В случае с условным 1км можно по аддитивности разложить любое решение через него. Я 1 км взял лишь для иллюстрации...

 

[crghome]

kakashkin - avbua прав (превозить до той точки, до которой потратится 1000л), ты применил тот же метод, и все это из моих предположений (правда я действительно ошибся с ненужной обратной ходкой)

 

[Kakashkin]

kakashkin - avbua прав (превозить до той точки, до которой потратится 1000л), ты применил тот же метод, и все это из моих предположений (правда я действительно ошибся с ненужной обратной ходкой)

Все правы, потому что вариантов там миллион. Только где доказательство того, что это максимальный вариант?
С вашими "(превозить до той точки, до которой потратится 1000л)" этим доказательством и не пахнет

 

[crghome]

С вашими "(превозить до той точки, до которой потратится 1000л)" этим доказательством и не пахнет

Это влияет на количество ходок для максимилизации перевозки, так как вмещается только тонна, то и считать необходимо до того момента пока не станет на тонну меньше. Иначе будет возрастать кол-во затрат, модель представляет собой обратную параболу.

 

[Kakashkin]

Это влияет на количество ходок для максимилизации перевозки, так как вмещается только тонна, то и считать необходимо до того момента пока не станет на тонну меньше. Иначе будет возрастать кол-во затрат, модель представляет собой обратную параболу.

Как вы считаете я прекрасно понимаю, я сам точно также посчитал в итоге. Но вопрос в другом, предположим есть вариант довезти X л, где X>676 л, как используя лишь перевоз на 1000/7, 1000/5 и 1000/3 км прийти к противоречию?

 

[sobutilnik]

Да, но как вы докажете, что нет варианта перевезти больше, используя ваш подход? В случае с условным 1км можно по аддитивности разложить любое решение через него. Я 1 км взял лишь для иллюстрации...

тут все логично. Нужно перевозить на 1метр или еще лучше на 1мм. Если будет считать на 1 метр, то явно получим число большее 676.

 

[avbua]

Да, но как вы докажете, что нет варианта перевезти больше, используя ваш подход?

Попробуем:

1. Сначала докажем, что оставлять какой-то остаток на складе невыгодно. Если при решении задачи на складе осталось x литров из всего объёма V, то всегда можно использовать x литров для перевоза V-x литров на какое-то растояние и дальше применив старое решение и учитывая, что расстояние стало меньше, получить лучший результат.

2. Чтобы довезти большее число литров до конечной точки, надо минимизировать проезд бензовоза, т. е. участок дороги по которому нужно проехать n раз должен быть минимальным. Для определения начала следующего участка исходим из того, что следующий участок надо проехать за меньшее число раз, значит количество бензина там должно быть кратное 1000 и меньше чем на текущем участке.

 

[Kakashkin]

тут все логично. Нужно перевозить на 1метр или еще лучше на 1мм. Если будет считать на 1 метр, то явно получим число большее 676.

1 м или 1мм - не играет роли, получите тоже самое: 7 ходок * 1 м = 7 * 1мм * 1000 отрезков

2. Чтобы довезти большее число литров до конечной точки, надо минимизировать проезд бензовоза, т. е. участок дороги по которому нужно проехать n раз должен быть минимальным. Для определения начала следующего участка исходим из того, что следующий участок надо проехать за меньшее число раз, значит количество бензина там должно быть кратное 1000 и меньше чем на текущем участке.

Так я же вам показал, что след участок можно проехать не обязательно за меньшее кол-во раз - если ехать кусками по 1км, то след участок можно проехать за равное пред кол-во раз, а привезти ровно столько же.

 

[sobutilnik]

1 м или 1мм - не играет роли, получите тоже самое: 7 ходок * 1 м = 7 * 1мм * 1000 отрезков

Доедет больше. Возьмите расстояние для итерации 1000км. Вообще не доедем. Теперь 500 км. доедем до середині, но пустые. 250 км. Уже часть сможем довести до места. И т.д. уменьшая расстояние получаем больше результат

 

[Kakashkin]

Доедет больше. Возьмите расстояние для итерации 1000км. Вообще не доедем. Теперь 500 км. доедем до середині, но пустые. 250 км. Уже часть сможем довести до места. И т.д. уменьшая расстояние получаем больше результат

 

[avbua]

Доедет больше. Возьмите расстояние для итерации 1000км. Вообще не доедем. Теперь 500 км. доедем до середині, но пустые. 250 км. Уже часть сможем довести до места. И т.д. уменьшая расстояние получаем больше результат

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