Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 19:18

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Задача "нерешительный кенгуру"
СообщениеДобавлено: Сб апр 09, 2011 19:09 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Может быть зверская тишина лучше всего развеется от решения задачи

Кенгуру не умеет плавать, но должен перебраться на другую сторону пруда.
по поверхности пруда расположены камни - опоры, по которым он мог бы перебраться.
Прыгать он может на произвольное расстояние, но с несколькими условиями
1. кенгуру не механический, он устаёт, поэтому каждый следующий максимальный прыжок может быть не более 4/5 предыдущего
2. кенгуру в курсе своей слабости, потому не решится на прыжок более чем 4/5 предыдущего
3. даже если первый прыжок был очень длинным, а второй маленьким, т.е. не должен бы вызвать усталость, кенгуру всё равно не сможет решиться на прыжок длинее 4/5 предыдущего.

Задача
1. найти путь по камням в пруду для опасливого кенгуру. Понятно, что если камни расположены не слишком густо, нужно экономить длину прыжка, не совершать слишком коротких прыжков, т.к. может не найтись следующий камень на подходящем расстоянии
2. необходимо найти решение с как можно меньшей стартовой длиной прыжка. Понятно, что если ограничений на стартовую длину нет, то можно просто перепрыгнуть пруд, но это неинтересно.
3. при каких условиях возможно решение с использованием только целых чисел
4. какая эвристика возможна для этой задачи?

Камни (неподвижно) и соответственно кенгуру (динамически) расположены в ячейках сетки 25х25, растояние между узлами сетки одинаково и равно 1

соответственно расположение опоры может быть задано или одним числом - позицией в массиве, который описывает пруд

так расстояние по прямой между двумя числами 1 и 2 будет равно единице по горизонтали, между числами 0 25 - единице по вертикали

или двумя числами - X Y

скажем, вот

0,18
1,1
2,6
4,12
5,19
6,3
9,7
10,16
12,3
15,8
15,18
17,13
19,7
21,20
22,4
9,3
13,13
6,8
13,22
23,13
стартовое положение :D 2 варианта - в более простом - 0,0
в более сложном ненамного варианте считается, что вся нулевая полоса Y=0
заставлена камнями и нужно выбрать целое число - координату Х,
которая позволит наименьший прыжок, количество прыжков роли не играет


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Пн апр 11, 2011 13:49 
Не в сети

Зарегистрирован: Вт фев 08, 2011 07:15
Сообщения: 18
Откуда: Беларусь
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
сразу напрашивается такая эвристика: выбрать для 1-го прыжка камень ближайший к стартовой позиции, если удастся построить путь на другой берег, то задача решена, если нет -- выбираем следующий по удаленности и тд


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Пн апр 11, 2011 13:53 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
: AL/M ; писал(а):
сразу напрашивается такая эвристика: выбрать для 1-го прыжка камень ближайший к стартовой позиции, если удастся построить путь на другой берег, то задача решена, если нет -- выбираем следующий по удаленности и тд
Не будет ли такой путь решения - то же что полный перебор?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Пн апр 11, 2011 14:12 
Не в сети

Зарегистрирован: Вт фев 08, 2011 07:15
Сообщения: 18
Откуда: Беларусь
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
а это уже зависит от других эвристик ))

поэтому предлагаю еще для каждого пройденного камня запоминать макс. допустимую длину прыжка при котором берег из этого камня не достижим (если достижм то дальше нечего делать) -- тогда при повторном попадании на камень можно сравнивать текущую возможную длину прыжка с той что "записана на камне" и делать вывод стоит ли продолжать путь или вернуться назад


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 08:35 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
А "волной" с обратного берега пройти не проще? По обратному правилу соотношения прыжков.
Идем на все камни сразу (они становятся "вторым берегом"), с них смотрим, куда можно попасть еще и так несколько раз, пока не доберемся до другого берега, не доберемся - значит и прямого пути нет.

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 17:00 
Не в сети
Аватара пользователя

Зарегистрирован: Пт дек 26, 2008 21:16
Сообщения: 412
Откуда: Великий Новгород
Благодарил (а): 9 раз.
Поблагодарили: 4 раз.
WingLion писал(а):
А "волной" с обратного берега пройти не проще?
Да и первым пробуем самый ближайший камень.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 20:55 
Не в сети

Зарегистрирован: Вт фев 08, 2011 07:15
Сообщения: 18
Откуда: Беларусь
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
мне кажется метод «обратной волны» как раз-таки приведет к перебору всех возможных путей, т.к. обратный проход стремится максимизировать первоначалтный прыжок и следовательно чтобы найти минимальный нужно перебрать все пути


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 21:33 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Максимальная длина прыжков представляет собой геометрическую прогрессию. Сумма ее n членов
s = b * (1-4/5^n)/(1-4/5)
при n -> \inf формула превращается в s = b * (1-0)/(1-4/5), или s = b*5
Отсюда, если сумма должна быть не менее 25, то длина первого прыжка не может быть меньше 5. Это верхнее ограничение, причем оно не учитывает две особенности. Во-первых, при b=5 прыгать придется до бесконечности (так что это не вариант). Во-вторых, не учитывается переход от плавающей точки к целочисленному представлению, который, кстати, не оговорен и в условии. Если длина прыжка стала 0.99, то прыгать нельзя? Или надо дождаться 0.5? Или все расчеты надо вести с округлением, и следующий шаг рассчитывать от целочисленного представления, полученного округлением предыдущего прыжка?
Если отталкиваться от одного из вариантов, то можно попробовать проверять ближайший камень, находящийся на расстоянии, большим 5. Для каждого последующего прыжка пишем функцию "теоретически можно допрыгнуть", которая будет вычислять сумму бесконечного числа членов геометрической прогрессии с начальным членом, равным расстоянию прыжка до этого камня. И далее рекурсивно, пока не допрыгаем не теоретически, а практически.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 22:06 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Цитата:
Во-вторых, не учитывается переход от плавающей точки к целочисленному представлению, который, кстати, не оговорен и в условии. Если длина прыжка стала 0.99, то прыгать нельзя?

Цитата:
при каких условиях возможно решение с использованием только целых чисел
это вопрос а не задача, впрочем, это часть задачи


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 22:16 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
вопрос писал(а):
это вопрос а не задача, впрочем, это часть задачи

Так я уже несколько вариантов привел. Вот если допустимая длина прыжка 10, а до нового камня 10.1, то прыгать можно или нет?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 22:22 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Хищник писал(а):
вопрос писал(а):
это вопрос а не задача, впрочем, это часть задачи

Так я уже несколько вариантов привел. Вот если допустимая длина прыжка 10, а до нового камня 10.1, то прыгать можно или нет?

Если нам понятно, что длина больше - то нет. Т.е. если например по вертикали камень расположен на расстоянии 10 , то если он хоть на небольшой угол отклонен по диагонали - то расстояние очевидно больше.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 22:30 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Надеюсь подробное изложение Хищника :idea: не ввело кого-то в заблуждение - там показан теоретически лучший вариант
реально решенине будет хужe


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 22:37 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
вопрос писал(а):
Если нам понятно, что длина больше - то нет. Т.е. если например по вертикали камень расположен на расстоянии 10 , то если он хоть на небольшой угол отклонен по диагонали - то расстояние очевидно больше.

Но вот если мы прыгнули на корень квадратный из 17, то как рассчитывать максимальную длину следующего прыжка? На что умножать 4/5 - на точное значение, а потом округлить, или сначала округлить, а потом умножить?
Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 22:42 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Цитата:
Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.
:)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача "нерешительный кенгуру"
СообщениеДобавлено: Вт апр 12, 2011 23:38 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
вопрос писал(а):
Цитата:
Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.

Эээ... а что не так? Сумма квадратов расстояний - целое число. Если расстояния должны соотноситься не более чем 4/5, то квадраты - не более чем 16/25.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB