Люди помогите решить вот такую задачу.
Удавчик ползает по прямой и изначально он пробегает 1см в сек. Когда удавчик наползает на спидап его скорость удвавается. На вход подается координата начала, конца, и кол-во бонусов и их координаты. На до найти путь который займет наименьшее кол-во времени.
и вывести проходимые спидапы(их координыты) и общее время все происходит на прямой.
заранее спасибо
Задача интересная... Я уже запостил сюда решение, но сразу после этого обнаружил, что оно неверное , и убрал. По сути ясно, что без полного перебора тут не обойтись... То есть нужно перепробовать все возможные способы прохождения спидапов, что соответствует перебору всех возможных расстановок, коих есть числом
там спид апод до 1000 а время работы до 3сек
Пользуйся поиском + смотри FAQ, я думаю тебе нужно искать "Поиск картчайшего пути в графе" ...
Люди погибну, если завтра не сдам помогите пожалуйста, хотябы идейками, но лучше кодом
Немного подумав, я пришел к выводу, что проблема не так сложна, как сначала мне показалась..
В любой текущий момент времени удав может двигаться влево или вправо. Поворачивать на пустом месте (без спидапа) для удава никакого резону нет, так что будем рассматривать только моменты прохождения спидапов. В любой такой момент перед удавом стоит дилемма: двигаться влево или вправо - то есть двоичный выбор. Таким образом, все возможные пути представляют собой двоичные числа (0 означает движение влево, а 1 - вправо) длины не больше М разрядов (М - число спидапов, включая начальную точку).
Программных реализации этого дела на ум приходят две:
1. Перебор всех двоичных чисел с подсчетом времени путешествия удава по схеме каждого двоичного числа.
2. Рекурсивная процедура передвижения на шаг влево или вправо.
В каждой реализации пройденные точки помечаются как неактивные и на следующем шаге не учитываются.
Рекурсия более ресурсоемка (как по отношению к памяти, так и ко времени), но проще в реализации (по крайней мере, для меня), так что я выбрал ее.
Теперь слушай сюда, arhimag. Я сейчас выложу полностью работающую прогу (даже с некоторыми с комментариями).. Но если ты, arhimag, не напишешь тут в ближайшие дни полный разбор этой программы - то, arhimag, пеняй на себя, arhimag. Потому что какой бы ты там архи- ни был бы маг, а volvo меня тут уроет и еще потопчется потом на холмике!! И будет прав.. потому что надо заранее постить тему и участвовать в обсуждении активно, а не кричать, что помогите-гибнешь и все такое.. Короче, arhimag, если не появится подробного разбора этой проги в течение нескольких дней - я клянусь тебе, arhimag, я больше ни разу тебе тут не отвечу! Ни на самый маленький вопросик!! И, думаю, ко мне все остальные присоединятся..
Ты понл, да??
Вот, а теперь - дело..
Программа использует файл с названием speedups.txt. В нем заводятся координаты спидапов, а также координаты начального положения удава и финиша. Все координаты должны быть обязательно упорядочены по возрастанию! Координаты старта вводятся среди спидапов (как бы он начинает движение со спидапа). Координата финиша всегда максимальная! Случай, когда финиш находится слева моя прога не умеет решать. Формат файла такой:
В первой строчке два целых числа:
- сначала кол-во спидапов плюс 2 (то есть полное число спидапов плюс старт и финиш),
- потом номер спидапа начальной позиции (старта).
В последующих строках идут координаты спидапов, старта и финиша по возрастающей, по одному числу на строку. Вот пример файла (комментарии в скобках в файле не должны присутствовать!):
7 3 (семь строк ниже, третье число - старт)
-10
-3
1 (это старт)
2
15
20
30 (это финиш)
А теперь сама прога..
const
N=100;
type
tInt=integer;
tReal=real;
tSpeedUp=record
x:integer;
active:boolean
end;
var
time:tReal=1E99;
l:integer=0;
var
x,p,px:array[1..N]of integer;
a:array[1..N]of boolean;
f:text;
s,m,i,lx:integer;
function Go(s:integer;v,t:tReal):boolean;
var
sl,sr:integer;
begin
Inc(l);p[l]:=s;
if s=m then begin { finish }
if time>t then begin
time:=t;
lx:=l;
px:=p
end
end
else if a[s] then begin { active speedup }
a[s]:=false;
sl:=s;
repeat Dec(sl) until (sl=0)or Go(sl,v*2,t+(x[s]-x[sl])/v); { Move left }
sr:=s;
repeat Inc(sr) until (sr>m)or Go(sr,v*2,t+(x[sr]-x[s])/v); { Move right }
a[s]:=true;
Go:=true
end
else Go:=false; { passive speedup }
Dec(l)
end;
begin
Assign(f,'speedups.txt');ReSet(f);
ReadLn(f,m,s);
for i:=1 to m do begin
ReadLn(f,x[i]);
a[i]:=true
end;
Close(f);
Go(s,1,0);
WriteLn('Min Time:',time:10:6);
Write('Path:');
for i:=1 to lx do Write(px[i]:4);
ReadLn
end.
спасибо, Lapp но что ты имеешь ввиду под разбором? просто объяснить как она работает?