IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Псевдо удавчик
сообщение
Сообщение #1


Знаток
****

Группа: Пользователи
Сообщений: 424
Пол: Мужской

Репутация: -  2  +


Люди помогите решить вот такую задачу.
Удавчик ползает по прямой и изначально он пробегает 1см в сек. Когда удавчик наползает на спидап его скорость удвавается. На вход подается координата начала, конца, и кол-во бонусов и их координаты. На до найти путь который займет наименьшее кол-во времени.
и вывести проходимые спидапы(их координыты) и общее время все происходит на прямой.
заранее спасибо


--------------------
Чего хочет женщина – того хочет Бог
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Задача интересная... Я уже запостил сюда решение, но сразу после этого обнаружил, что оно неверное sad.gif, и убрал. По сути ясно, что без полного перебора тут не обойтись... То есть нужно перепробовать все возможные способы прохождения спидапов, что соответствует перебору всех возможных расстановок, коих есть числом
Код
   n
<сумма> i!
  i=1

где n - число спидапов. Хотя меня не покидает сомнение, что это число можно уменьшить. Надо подумать..

Сообщение отредактировано: lapp -


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Знаток
****

Группа: Пользователи
Сообщений: 424
Пол: Мужской

Репутация: -  2  +


там спид апод до 1000 а время работы до 3сек


--------------------
Чего хочет женщина – того хочет Бог
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Автооответчик
*****

Группа: Пользователи
Сообщений: 1 188
Пол: Мужской
Реальное имя: Александр

Репутация: -  16  +


Цитата
Удавчик ползает по прямой и изначально он пробегает 1см в сек. Когда удавчик наползает на спидап его скорость удвавается.

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


--------------------
Неадекватная чушь может быть адекватным ответом на неадекватный вопрос. Понятно или разжевать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(GoodWind @ 12.04.2006 7:35) *

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

Полагаю, навсегда.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Знаток
****

Группа: Пользователи
Сообщений: 424
Пол: Мужской

Репутация: -  2  +


Цитата
Цитата
Цитата(GoodWind @ 12.04.2006 7:35)

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



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

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

пробывал, не помогло sad.gif мне завтра сдавать sad.gif


--------------------
Чего хочет женщина – того хочет Бог
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Знаток
****

Группа: Пользователи
Сообщений: 424
Пол: Мужской

Репутация: -  2  +


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


--------------------
Чего хочет женщина – того хочет Бог
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(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 мин. Никакой преп не станет ее давать на два дня.. Если я ошибаюсь - буду рад увидеть опровержения.. Сам тоже подумаю еще..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Немного подумав, я пришел к выводу, что проблема не так сложна, как сначала мне показалась..
В любой текущий момент времени удав может двигаться влево или вправо. Поворачивать на пустом месте (без спидапа) для удава никакого резону нет, так что будем рассматривать только моменты прохождения спидапов. В любой такой момент перед удавом стоит дилемма: двигаться влево или вправо - то есть двоичный выбор. Таким образом, все возможные пути представляют собой двоичные числа (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.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Знаток
****

Группа: Пользователи
Сообщений: 424
Пол: Мужской

Репутация: -  2  +


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

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

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

Мне просто было леня расладку переключать rolleyes.gif

Сообщение отредактировано: arhimag -


--------------------
Чего хочет женщина – того хочет Бог
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(arhimag @ 13.04.2006 6:35) *

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 22.08.2017 12:17
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"