Представьте себе круговую трассу, на которой на произвольном расстоянии размещены заправки, каждая с определенным объемом бензина. Кол-во бензина на всех заправках равно длине дороги. Ваш автомобиль потребляет 100 литров на 100 км и имеет неограниченный бензобак. Вопрос: в какой точке автомобиль должен начать движение, что бы у него никогда не кончался бензин во время поездки? Дано: 2 массива, 1-ый с объемами бензина на заправках с направлении хода часов, 2-ой с расстояниями между заправками. Как заставить два массива сравниваться подобным образом?
volvo
15.12.2008 23:28
Цитата
Вопрос: в какой точке автомобиль должен начать движение, что бы у него никогда не кончался бензин во время поездки?
Ответ: в любой. Потому как
Цитата
автомобиль потребляет 100 литров на 100 км и имеет неограниченный бензобак
С чего бы в неограниченном бензобаке кончился бензин?
А если серьезно - ты бы условие перепроверил, что-то не очень связывается. Например,
Цитата
Кол-во бензина на всех заправках равно длине дороги
Я уж не говорю о том, что бензин мерить километрами - как то непривычно, вопрос вообще в другом: заправился автомобиль, слил весь бензин, это значит, что больше он на эту заправку приехать не может, или бензин как-то восстанавливается на заправке? Сколько кругов автомобиль должен намотать по трассе? Сколько у него в неограниченном бензобаке есть бензина в начале пути (а то ведь можно и до первой заправки не доехать, если бензина нет изначально)?
Kolyancz
16.12.2008 18:23
Да, условие сложно описать, проще, конечно нарисовать. Когда, я писал о том, что кол-во литров ровнокилометрам, я имел ввиду номинал. 23 литра-23километра. Неограниченый бак вовсе не значит полный бак, это второстепенное условие, типа на всякий случай. Вот напимер: На круговой дороге стоят 5 заправок: Первый массив показывает кол-во литров бензина на этих заправках: 4 7 5 3 4 Второй массив показывает кол-во километров между ними: 7 6 2 3 5 Видно, что всю дорогу можно проехать только лишь тогда, когда начнешь свой путь со второй заправки, т.е. начинаем на заправке номер два: налили 7 литров проехали 6 километров, остался 1 литр, налили еще 5, проехали 2 км, осталось 4 литра, налили еще 3, проехали 3 км, осталось 4 литра, налили еще 4 литра, проехали 5 км, осталось 3 литра, налили еще 4, проехали 7 км, вот и на той заправки, на которой начали. Круг один, нужно найти способ проехать круг так, что бы бензин не кончился по пути.
Lapp
17.12.2008 9:44
Цитата(Kolyancz @ 15.12.2008 19:18)
в какой точке автомобиль должен начать движение, что бы у него никогда не кончался бензин во время поездки?
Забавная задачка . Как я понимаю, исходная точка должна найтись обязательно. Возможно, она не одна, но мой код находит только первую.
Цитата(Kolyancz @ 15.12.2008 19:18)
Как заставить два массива сравниваться подобным образом?
Сначала я сделал вторым способом, но разброс во втором массиве получился низкий. Тогда я сделал первый способ. Он значительно улучшил ситуацию, но совсем честным будет только продолжение первого цикла первого способа до достижения t=0.
const m=20;
var Gas,Way: array[1..m]of integer; Start,Tank,t,i: integer;
begin { Заполнение массивов } Randomize; t:=0; { первый способ} for i:=1 to m do begin Gas[i]:=Random(m)+1; Way[i]:=Random(m)+1; t:=t+Gas[i]-Way[i]; end; for i:=1 to Abs(t) do Inc(Way[Random(m)+1],t div Abs(t));
{ второй способ } {for i:=1 to m do begin Gas[i]:=Random(m)+1; t:=t+Gas[i]; Way[i]:=0 end; for i:=1 to t do Inc(Way[Random(m)+1]);}
for i:=1 to m do WriteLn('Pump:',i:3,' Gas:',Gas[i]:3,' Way:',Way[i]:3);
{ Езда } Start:=0; repeat Inc(Start); Tank:=0; i:=Start; while Tank>=0 do begin Tank:=Tank+Gas[i]-Way[i]; i:=i mod m+1; if i=Start then break end; until Tank=0; WriteLn('start at pump ',Start); ReadLn end.
Kolyancz
17.12.2008 22:38
Lapp, ты действительно гений. Очень красиво решил. Спасибо.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.