в--..Ш миль

Для k=l ответ равен 500 милям, как и показано на рис. 3.1.2. Можно заправить машину в точке В и пересечь оставшиеся 500 миль пустыни. Ясно, что это наиболее отдаленная точка, стартуя из которой можно преодолеть пустыню, имея в точности 500 тал- соотм лонов горючего.

Мы поставили перед собой частную цель, потому что не смогли бы решить сразу исходную задачу. Мы не задаем- вопрос: сколько топлива нужно машине, чтобы преодолеть заданную дистанцию? Вместо этого задаем более простой, но родственный вопрос: какое расстояние можно проехать на заданном количестве топлива? Ответить на первый вопрос становится возможным, когда ответом на второй является: не меньше 1000 миль.

Предположим, что k=2, т. е. имеется два полных бака (1000 галлонов). Будем рассматривать этот случай, опираясь на результат для1. Данная ситуация иллюстрируется на рис. 3.1.2. Каково максимальное значение Xi, такое, что, отправляясь с 1000 галлонами горючего из точки 500-Xi, можно перевезти достаточно горючего в -точку В, чтобы завершить поездку, как в случае /г=1.

Один из способов определения приемлемого значения Xi состоит в следующем. Заправляемся в точке 500-Xi, едем Xj миль до В и переливаем в хранилище все горючее, кроме Xi галлонов, которые потребуются для возвращения в -точку 500-Xj. В этой -точке бак становится пустым. Теперь наполняем второй полный бак, проезжаем Xi миль до В, забираем в В горючее, оставленное там, и из В едем в С с полным баком. Общее пройденное расстояние сос-гоит из трех отрезков по Xi миль и одного отрезка ВС длиной 500 миль. Мы должны израсходовать каждую каплю топлива, чтобы сделать значение Xi как можно большим. Поэтому Xi находим из уравнения

3x1+500=1000 (галлонов);

его решение: Xi=500/3. Таким образом, два бака (1000 галлонов) позволяют нам проехать

D2 = 500 + Xi = 500(l + -j миль.

Заметим, ч-го исходная предпосылка является недальновидной и грубой. Когда имеются в распоряжении k баков горючего, мы просто стараемся продвинуться назад как можно дальше от -точки, найденной для k~l баков.

Рассмотрим k=3. Из какой точки мы можем выехать с 1500 галлонами топлива так, что машина сможет доставить 1000 галлонов в точку 500-Xi? Возвращаясь к рис. 3.1.2, мы ищем наибольшее зна-

ifl-L о мш

Рис. 3.1.2. Задача о джипе: пересечение пустыни из Л в С.

чение Хг, такое, что, выезжая с 1500 галлонами топлива из точки 500-Хх-Хг, мы можем доставить 1000 галлонов в точку 500-х Мы выезжаем из точки 500-Xi-лга, доезжаем до 500-Xi, переливаем все горючее, кроме Хг галлонов, и возвращаемся в точку 500-Xi-Хг с пустым баком. Повторив эту процедуру, мы затратим Xг галлонов на проезд и оставим 1000-42 галлонов в точке 500-х,. Теперь в точке ЩУ-Хг-Хг осталось ровно 500 галлонов. Заправляемся последними 500 галлонами и едем в точку 500-Xi, израсходовав на это Хг галлонов.

Теперь мы находимся в точке 500-Xi, затратив на проезд Ъхг галлонов топлива. Здесь оставлено в общей сложности 1500-52 галлонов. Это количество должно быть равно 1000 галлонам, т. е. л:а=500/5. Из этого заключаем, что 1500 галлонов позволяют нам проехать

Сз = 500 + л:1 + л:2 = 500 1 + - + -) миль.

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

С„ = 500(1ч4ч4+...+2;)-

Нужно найти наименьшее значение п, при котором D„1000-Простые вычисления показывают, что для п=1 имеем В=9П,Ъ мили, т. е. семь баков, или 3500 галлонов, топлива дадут нам возможность проехать 977,5 мили. Полный восьмой бак - это было бы уже больше, чем нам надо, чтобы перевезти 3500 галлонов из точки А в точку, отстоящую на 22,5 мили (1000-977,5) от А. Читателю представляется самостоятельно убедиться в том, что для доставки 3500 галлонов топлива к отметке 22,5 мили достаточно 337,5 галлона. Таким образом, для того чтобы пересечь на машине пустыню из Л в С, нужно 3837,5 галлона горючего.

Теперь алгоритм транспортировки горючего может быть представлен следующим образом. Стартуем из А, имея 3837,5 галлона. Здесь как раз достаточно топлива, чтобы постепенно перевезти 3500 галлонов к отметке 22,5 мили, где мы в конце концов окажемся с пустым баком и запасом горючего на семь полных заправок. Этого топлива достаточно, чтобы перевезти 3000 галлонов к точке, отстоящей на 22,5+500/13 миль от А, где бак машины будет опять пуст. Последующие перевозки приведут нас к точке, отстоящей на 22,5+ 500/13+ -f500/11 миль от Л, с пустым баком машины и 2500 галлонами.

Продолжая таким образом, мы продвигаемся вперед благодаря анализу, проведенному методом отрабатывания назад. Вскоре мы окажемся у отметки 500(1-1/3)=1000/3 миль с 1000 галлонами топлива. Затем мы перевезем 500 галлонов в В, зальем их в бак машины и доедем без остановки до С. Рис. 3.1.3 иллюстрирует весь этот процесс.

Для тех, кто знаком с бесконечными рядами, заметим, что D„

есть п-я частная сумма нечетного гармонического ряда. Поскольку этот ряд расходится, алгоритм. дает возможность пересечь любую пустыню. Как можно модифицировать этот алгоритм для того, чтобы оставить достаточно горючего в различных точках пустыни для возвращения в Л?

Adbm SfiTfiff Idttiici Itfafc гол 2000 гй? 1500 гс/г 1000 гйГ £00 гаг

А 7 Б S в

3. "--

Рис. 3.1.3. Схема решения задачи оджипе.

Возникает вопрос, можно ли проехать 1000 миль, затратив меньше чем 3837,5 галлона горючего. Оказывается, что нельзя. Доказательство этого факта довольно сложно. Однако можно высказать следующий, довольно правдоподобный довод. Очевидно, мы действуем наилучшим образом для й=1. При /г=2 мы используем наш план для k=\ и затем вводим в действие второй бак горючего для того, чтобы оказаться как можно дальше от В. Исходная предпосылка для k баков заключается в том, что мы знаем, как действовать наилучшим образом в случае с k-1 баками, и отодвигаемся как можно дальше назад с помощью й-го бака.

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

Упражнения 3.1

3.1.1. Взвешивание монет (подъем). Имеется 25 золотых монет. Все они одного веса, за исключением одной монеты с дефектом, которая весит меньше остальных. Разработайте алгоритм, определяющий дефект за три взвешивания. Каково максимальное число монет, для которых можно определить монету с дефектом не больше чем за три взвешивания на весах с чашками?

3.1.2. НеотградуироваНные сосуды (отрабатывание назад). Имеются неотградуиро-ванные 5-галлонный и 3-галлонный сосуды. Нужно отмерить ровно 4 галлона жидкости. Разработайте алгоритм для этой процедуры. Предполагается, что есть очень большой резервуар с жидкостью.

*3.1.3. Задача разрезания бумаги (частные цели). На рис. 3.1.4 показан греческий крест, составленный из пяти одинаковых квадратов. Делая только два прямых разреза, разрежьте крест так, чтобы можно было сложить его части в прямоугольник, одна сторона которого в два раза длиннее другой.

3.1.4. Разбиение круга (подъем). На какое максимальное число частей может быть разделен круг четырьмя прямыми линиями?