Помощь - Поиск - Пользователи - Календарь
Полная версия: Псевдо удавчик
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
arhimag
Люди помогите решить вот такую задачу.
Удавчик ползает по прямой и изначально он пробегает 1см в сек. Когда удавчик наползает на спидап его скорость удвавается. На вход подается координата начала, конца, и кол-во бонусов и их координаты. На до найти путь который займет наименьшее кол-во времени.
и вывести проходимые спидапы(их координыты) и общее время все происходит на прямой.
заранее спасибо
Lapp
Задача интересная... Я уже запостил сюда решение, но сразу после этого обнаружил, что оно неверное sad.gif, и убрал. По сути ясно, что без полного перебора тут не обойтись... То есть нужно перепробовать все возможные способы прохождения спидапов, что соответствует перебору всех возможных расстановок, коих есть числом
Код
   n
<сумма> i!
  i=1

где n - число спидапов. Хотя меня не покидает сомнение, что это число можно уменьшить. Надо подумать..
arhimag
там спид апод до 1000 а время работы до 3сек
klem4
Пользуйся поиском + смотри FAQ, я думаю тебе нужно искать "Поиск картчайшего пути в графе" ...
GoodWind
Цитата
Удавчик ползает по прямой и изначально он пробегает 1см в сек. Когда удавчик наползает на спидап его скорость удвавается.

на какой период удваивается ?
Lapp
Цитата(GoodWind @ 12.04.2006 7:35) *

на какой период удваивается ?

Полагаю, навсегда.
arhimag
Цитата
Цитата
Цитата(GoodWind @ 12.04.2006 7:35)

на какой период удваивается ?



Полагаю, навсегда.
yes2.gif yes2.gif
на всегда и координаты целочиссленные

Цитата
Пользуйся поиском + смотри FAQ, я думаю тебе нужно искать "Поиск картчайшего пути в графе" ...

пробывал, не помогло sad.gif мне завтра сдавать sad.gif
arhimag
Люди погибну, если завтра не сдам sad.gif помогите пожалуйста, хотябы идейками, но лучше кодом
Lapp
Цитата(klem4 @ 12.04.2006 7:32) *
Пользуйся поиском + смотри FAQ, я думаю тебе нужно искать "Поиск картчайшего пути в графе" ...
klem4, я думаю, это не граф. То есть граф, конечно, но граф из всевозможных соединений, и это не помогает, мне кажется. Впрочем, могу ошибаться. Развей свою идею.
Мне же кажется, что проще рассматривать последовательности прохождений спидапов, как n-значные числа в n-ричной системе. Иначе говоря, если есть 10 спидапов (занумерованных как 0, 1, 2 .. 9), то все варианты их прохождения выразятся числами типа 1025347698 - такими, где каждая цифра употреблена один раз. Можно проходить не все спидапы, тогда число будет короче. Некоторые комбинации неосуществимы в реальности, т.к. если спидап 2 находится за спидапом 1, то число, где 1 идет после 2 невозможно.
Цитата(arhimag @ 12.04.2006 6:41) *
там спид апод до 1000 а время работы до 3сек
arhimag, ты ничего не напутал?.. Если я правильно понял твой русский язык (весьма странный, согласись..) удав может ускориться 1000 раз - да? А ты представляешь себе значение скорости при этом? Ты понимаешь, что на хранение ее значения нужно 125 байт?? Тут нужно не просто длинная арифметика, а очень длинная.. и тогда о 3 секундах точно забудь..
Цитата(arhimag @ 12.04.2006 20:12) *
Люди погибну, если завтра не сдам sad.gif помогите пожалуйста, хотябы идейками, но лучше кодом
Дорогой друг, а о чем ты думал?.. Сейчас скажешь, что вчера задали, да? Имея некоторый опыт программирования, могу сказать, что эта задача не на 15 мин. Никакой преп не станет ее давать на два дня.. Если я ошибаюсь - буду рад увидеть опровержения.. Сам тоже подумаю еще..
Lapp
Немного подумав, я пришел к выводу, что проблема не так сложна, как сначала мне показалась..
В любой текущий момент времени удав может двигаться влево или вправо. Поворачивать на пустом месте (без спидапа) для удава никакого резону нет, так что будем рассматривать только моменты прохождения спидапов. В любой такой момент перед удавом стоит дилемма: двигаться влево или вправо - то есть двоичный выбор. Таким образом, все возможные пути представляют собой двоичные числа (0 означает движение влево, а 1 - вправо) длины не больше М разрядов (М - число спидапов, включая начальную точку).

Программных реализации этого дела на ум приходят две:
1. Перебор всех двоичных чисел с подсчетом времени путешествия удава по схеме каждого двоичного числа.
2. Рекурсивная процедура передвижения на шаг влево или вправо.

В каждой реализации пройденные точки помечаются как неактивные и на следующем шаге не учитываются.
Рекурсия более ресурсоемка (как по отношению к памяти, так и ко времени), но проще в реализации (по крайней мере, для меня), так что я выбрал ее.

Теперь слушай сюда, arhimag. Я сейчас выложу полностью работающую прогу (даже с некоторыми с комментариями).. Но если ты, arhimag, не напишешь тут в ближайшие дни полный разбор этой программы - то, arhimag, пеняй на себя, arhimag. Потому что какой бы ты там архи- ни был бы маг, а volvo меня тут уроет и еще потопчется потом на холмике!! И будет прав.. потому что надо заранее постить тему и участвовать в обсуждении активно, а не кричать, что помогите-гибнешь и все такое.. Короче, arhimag, если не появится подробного разбора этой проги в течение нескольких дней - я клянусь тебе, arhimag, я больше ни разу тебе тут не отвечу! Ни на самый маленький вопросик!! И, думаю, ко мне все остальные присоединятся..
Ты понл, да?? mad.gif
Вот, а теперь - дело..

Программа использует файл с названием 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.
arhimag
спасибо, Lapp но что ты имеешь ввиду под разбором? просто объяснить как она работает?

Цитата
Дорогой друг, а о чем ты думал?.. Сейчас скажешь, что вчера задали, да? Имея некоторый опыт программирования, могу сказать, что эта задача не на 15 мин. Никакой преп не станет ее давать на два дня.. Если я ошибаюсь - буду рад увидеть опровержения.. Сам тоже подумаю еще..

правильно ты думаешь она дана на три дня!
Цитата
Если я правильно понял твой русский язык (весьма странный, согласись..)

Мне просто было леня расладку переключать rolleyes.gif
Lapp
Цитата(arhimag @ 13.04.2006 6:35) *

спасибо, Lapp но что ты имеешь ввиду под разбором? просто объяснить как она работает?

Да. Только не в двух словах. Хорошо было бы и блок-схемку, но слова все же в первую очередь. И назначение всех переменных с объяснением, почему они глобальные или локальные.
Успехов! smile.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.