IPB

Здравствуйте, гость ( Вход | Регистрация )

Активные темы за последние сутки
Новые сообщения с Вашего последнего посещения
Главная страница форума
Один из грузовиков должен проехать как можно дальше
Николай Петрович
сообщение 24.4.2019, 19:37
Сообщение #1


Я такой же, как все: я не похож ни на кого другого.


Группа: Пользователь
Сообщений: 4439
Регистрация: 7.10.2014
Из: Королёв
Пользователь №: 2324



У вас есть парк из 50 грузовиков. Каждый из них полностью заправлен и может проехать 100 км. Как далеко с их помощью вы можете доставить определенный груз? Что будет, если в вашем распоряжении N грузовиков?
Не все понимают сразу о чем речь: территориально это место, где нет никаких заправочных станций. Единственное место, где можно здесь найти горючее – это топливные баки грузовиков. Пересесть из грузовика в гибридный легковой автомобиль Prius нельзя. Бросить грузовик без топлива, где бы это ни случилось, и без водителя – в порядке вещей. И единственное, что здесь важно, – доставить как можно дальше ценный груз.

Источник, в нём дана ссылка на другое решение


Сначала решим вспомогательную задачу: в путь отправились два грузовика. Назовём ресурсом расстояние, которое может проехать грузовик с полным бензобаком.
Одному из грузовиков суждено остаться стоять на дороге. Само собой разумеется, что наибольшая дальность перевозки будет в том случае, если грузовик-донор отдаст второму грузовику весь оставшийся бензин. Когда грузовики не проехали половины ресурса, переливать бензин невыгодно, потому что освободилось меньше половины бака, а у донора бак заполнен более, чем наполовину. Если же грузовики проедут больше половины ресурса, то в бензобаке у каждого останется меньше половины объёма, и второй грузовик не сможет заправиться полностью. Значит, оптимальное место заправки там, где грузовики проехали ровно половину ресурса.

Теперь рассмотрим поездку трёх грузовиков.
Место для переливания бензина в этом случае не может быть ближе к месту старта, чем одна треть ресурса, потому что грузовики должны выработать одну треть бензина, чтобы появилась возможность забрать у грузовика-донора весь оставшийся у него бензин, а это две трети бензобака.
На растоянии одной трети ресурса бензин грузовика-донора (две трети бака) можно поделить только поровну, причём у каждого из двух грузовиков окажется полный бензобак. Дальнейшее путешествие двух грузовиков рассмотрено выше. Если же по какой-то причине все грузовики поедут дальше, не перелив бензин, то это будет не просто отсрочкой переливания бензина, а непроизводительным расходом бензина грузовиком-донором. Зачем ему ехать дальше, ведь всё равно он останется на дороге с пустым бензобаком.
Чтобы эта мысль была яснее, представим себе, что два грузовика отправились в путь с полными бензобаками, а третий тоже поехал с ними, но у него бензобак наполнен на одну треть, а в кузове лежат две канистры с таким же количеством безнзина. Вот они проезжают одну треть ресурса, третий грузовик дальше ехать не может, каждый из двух других грузовиков получает канистру и оказывается полностью заправленным. Третий грузовик мог бы проехать дальше, если бы часть бензина из канистр залил в свой бензобак, но для двух других грузовиков это означало бы не только отсрочку пополнения запаса бензина, но и получение меньшего количества бензина. То есть, оставшиеся два грузовика не смогли бы доставить груз так же далеко, как это сделали грузовики из вспомогательной задачи, разобранной в начале.

Если в путь отправятся четыре грузовика, то дозаправка должна состояться, когда у каждого из грузовиков освободится одна четверть бензобака, при этом у грузовика-донора, как у всех остальных, в бензобаке останется три четверти объёма. Этого хватит ровно для того, чтобы трём оставшимся грузовикам долить бензина до полной заправки.
Видна закономерность: каждый очередной грузовик-донор должен проехать от предыдущей заправки до своей последней остановки такую часть ресурса, которая равна обратной величине от количества грузовиков, едущих до этой остановки. Когда доноров не останется, единственный грузовик проедет расстояние, равное ресурсу, и доставит груз.

Ответ (в общем виде): максимальное расстояние, на которое 50 грузовиков могут доставить груз, равно 1/50+1/49+1/48+...+1/2+1 расстояния, которое один грузовик может проехать с полным бензобаком.


--------------------
Почти перестал публиковать сообщения в этом форуме, потому что без обратной связи делать это неинтересно.
Стал редко просматривать сообщения в форуме и другую доступную без авторизации обновляемую информацию в нём.
По-прежнему активен в интернете, почти всюду — с теми же, что здесь, никнеймом и аватаром.

Дата помещения этой подписи "О себе" — 19.02.2024
Перейти в начало страницы
 
+Цитировать сообщение
 
Начать новую тему
Ответов (1 - 1)
Татиана
сообщение 24.4.2019, 21:24
Сообщение #2


Активный участник


Группа: Пользователь
Сообщений: 1027
Регистрация: 28.8.2015
Из: Москва
Пользователь №: 2757



Хорошая задача. 02.gif
Перейти в начало страницы
 
+Цитировать сообщение

Ответить в данную темуНачать новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



RSS Текстовая версия Сейчас: 29.3.2024, 2:25