Небольшой пикап находится в пустыне около склада горючего, содержащего N полных бочек бензина вместимостью по 50 галлонов каждая. (Для справки: один галлон в США примерно равен 3,78 литра, а в Великобритании несколько больше — 4,55 литра.) Бак пикапа, который сейчас пуст, вмещает 10 галлонов, при этом одного галлона бензина хватает на 10 миль пути. Пикап может перевозить только одну бочку горючего (пустую или полную).

Спрашивается, как далеко можно уехать от начальной точки?

---

Полное описание посмотрите здесь:

http://www.computerra.ru/offline/1998/242/1236/

Хотя многое написано, по-прежнему задача не решена в общем виде.

Может кто программу составит для решения?

Здравствуйте, mrhru, Вы писали:

M>Небольшой пикап находится в пустыне около склада горючего, содержащего N полных бочек бензина вместимостью по 50 галлонов каждая. (Для справки: один галлон в США примерно равен 3,78 литра, а в Великобритании несколько больше — 4,55 литра.) Бак пикапа, который сейчас пуст, вмещает 10 галлонов, при этом одного галлона бензина хватает на 10 миль пути. Пикап может перевозить только одну бочку горючего (пустую или полную).

M>Спрашивается, как далеко можно уехать от начальной точки?

Давай в нормальные единицы переведём это дело

Пикап увозит с собой бензина на (50+10)*10=600 миль.
Всего бензина N*50/60= 5N/6 полных заправок.

С одной заправки пикап может уехать на длину одной заправки (600 миль)

С двух заправок — на длину 1+1/3 заправки.
Для этого он отвозит на 1/3 пути 1/3 заправки, возвращается, а потом едет снова с полным баком, подзаправляясь по дороге.

С трёх заправок уезжает на 1+1/3+1/5 заправки.
Для этого два раза отвозит на точку 1/5 по 3/5 заправки и затем с двумя заправками от этой точки попадает в предыдущий случай.

Далее по индукции. Имея на краю пустыни K заправок можно уехать на
(1+1/3+1/5+...+1/K)*600 миль — растёт логарифмически с ростом запаса бензина

Единственная проблема — что у нас нецелое число заправок, это можно как-то решить, но малоинтересно.



M>

---

M>Полное описание посмотрите здесь:

M>http://www.computerra.ru/offline/1998/242/1236/

M>Хотя многое написано, по-прежнему задача не решена в общем виде.

M>Может кто программу составит для решения?

M>

Здравствуйте, Pushkin, Вы писали:

P>Далее по индукции. Имея на краю пустыни K заправок можно уехать на
P>(1+1/3+1/5+...+1/K)*600 миль — растёт логарифмически с ростом запаса бензина

Только знать бы по какому основанию логарифм. Здесь именно это важно. Поскольку не понятно является ли метод изложенный Вами оптимальным

Здравствуйте, mrhru, Вы писали:

M>Небольшой пикап находится в пустыне около склада горючего, содержащего N полных бочек бензина вместимостью по 50 галлонов каждая. (Для справки: один галлон в США примерно равен 3,78 литра, а в Великобритании несколько больше — 4,55 литра.) Бак пикапа, который сейчас пуст, вмещает 10 галлонов, при этом одного галлона бензина хватает на 10 миль пути. Пикап может перевозить только одну бочку горючего (пустую или полную).

M>Спрашивается, как далеко можно уехать от начальной точки?

M>

---

M>Полное описание посмотрите здесь:

M>http://www.computerra.ru/offline/1998/242/1236/

M>Хотя многое написано, по-прежнему задача не решена в общем виде.

M>Может кто программу составит для решения?

M>

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

Здравствуйте, DOOM, Вы писали:

DOO>Здравствуйте, Pushkin, Вы писали:

P>>Далее по индукции. Имея на краю пустыни K заправок можно уехать на
P>>(1+1/3+1/5+...+1/K)*600 миль — растёт логарифмически с ростом запаса бензина

DOO>Только знать бы по какому основанию логарифм. Здесь именно это важно. Поскольку не понятно является ли метод изложенный Вами оптимальным

Логарифм натуральный. Метод оптимальный. Он не мой — я просто помню.

Здравствуйте, Pushkin, Вы писали:

P>>>(1+1/3+1/5+...+1/K)*600 миль — растёт логарифмически с ростом запаса бензина

P>Логарифм натуральный. Метод оптимальный. Он не мой — я просто помню.

Да, блин, забыл уточнить. Так как там в ряду только нечётные члены, будет коечно только пол-логарифма.

Итого ответ для большого запаса бензина L=ln(5N/6)*300

В ответе нужно оставлять только необходимую часть исходного сообщения. Не пренебрегайте этим правилом.

Этот же совет относится и к товарищу Pushkin'у. :user:

(10+50)*10=600