Автор |
Сообщение |
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
я поразмышлял на тему прямого и обратного поиска и пришел к выводу что оба подхода симметричны: - при движении вперед длина прыжка умножается на 4/5, назад -- на 5/4 - при движении вперед мы останавливаемся когда в окрестности равной длине прыжка нет камней (слишком короткий прыжок), при движении назад -- когда длина прыжка превышает макс. допустимую (слишком длинный прыжок) - в обоих направлениях можно реализовать поиск и в глубину и в ширину и тд...
но есть важное различие: при прямом обходе первый найденный путь удовлетворяет условию минимальности 1-го прыжка, при обратном надо перебрать все пути
остается вопрос: что лучше -- в глубину или ширину? Идя в глубину можно довольно эффективно отсекать повторное прохождение камней расставляя на них метки (динамическое программирование); если в ширину то такое отсечение невозможно, но может и не нужно?
у кого какие мысли по этому поводу?
я поразмышлял на тему прямого и обратного поиска и пришел к выводу что оба подхода симметричны: - при движении вперед длина прыжка умножается на 4/5, назад -- на 5/4 - при движении вперед мы останавливаемся когда в окрестности равной длине прыжка нет камней (слишком короткий прыжок), при движении назад -- когда длина прыжка превышает макс. допустимую (слишком длинный прыжок) - в обоих направлениях можно реализовать поиск и в глубину и в ширину и тд...
но есть важное различие: при прямом обходе первый найденный путь удовлетворяет условию минимальности 1-го прыжка, при обратном надо перебрать все пути
остается вопрос: что лучше -- в глубину или ширину? Идя в глубину можно довольно эффективно отсекать повторное прохождение камней расставляя на них метки (динамическое программирование); если в ширину то такое отсечение невозможно, но может и не нужно?
у кого какие мысли по этому поводу?
|
|
|
|
Добавлено: Чт апр 14, 2011 03:04 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
viewtopic.php?f=12&t=2704&start=15разместил решение на прологе для проверки решения на форте Всё-таки ещё раз предложу (не настаивая) открыть в конкурсе задач подотдел "решения на других языках" (тех же задач) не каждый тематический программистский форум может похвастать тем, что задачи решают на нескольких языках одновременно, манипулируя алгоритмами Задача про поиск пробела была решена на Прологе (два решения), Эйфории, и на Форте, причём Форт был нескольких реализаций и Пролог - также не один
http://fforum.winglion.ru/viewtopic.php?f=12&t=2704&start=15 разместил решение на прологе для проверки решения на форте
[size=85]Всё-таки ещё раз предложу (не настаивая) открыть в конкурсе задач подотдел "решения на других языках" (тех же задач) не каждый тематический программистский форум может похвастать тем, что задачи решают на нескольких языках одновременно, манипулируя алгоритмами Задача про поиск пробела была решена на Прологе (два решения), Эйфории, и на Форте, причём Форт был нескольких реализаций и Пролог - также не один[/size]
|
|
|
|
Добавлено: Ср апр 13, 2011 20:50 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
Хищник писал(а): вопрос писал(а): Цитата: Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми. Эээ... а что не так? Сумма квадратов расстояний - целое число. Если расстояния должны соотноситься не более чем 4/5, то квадраты - не более чем 16/25. Всё так , теперь может быть кто-то код предложит если нужно, могу запостить решение на Прологе для проверки оно, правда, в действительных числах и полный исчерпывающий перебор
[quote="Хищник"][quote="вопрос"]Цитата: Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.[/quote] Эээ... а что не так? Сумма квадратов расстояний - целое число. Если расстояния должны соотноситься не более чем 4/5, то квадраты - не более чем 16/25.[/quote] Всё так :) , теперь может быть кто-то код предложит если нужно, могу запостить решение на Прологе для проверки оно, правда, в действительных числах и [s]полный[/s] исчерпывающий перебор
|
|
|
|
Добавлено: Вт апр 12, 2011 23:54 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
вопрос писал(а): Цитата: Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми. Эээ... а что не так? Сумма квадратов расстояний - целое число. Если расстояния должны соотноситься не более чем 4/5, то квадраты - не более чем 16/25.
[quote="вопрос"]Цитата: Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.[/quote] Эээ... а что не так? Сумма квадратов расстояний - целое число. Если расстояния должны соотноситься не более чем 4/5, то квадраты - не более чем 16/25.
|
|
|
|
Добавлено: Вт апр 12, 2011 23:38 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
Цитата: Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.
[quote]Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.[/quote] :)
|
|
|
|
Добавлено: Вт апр 12, 2011 22:42 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
вопрос писал(а): Если нам понятно, что длина больше - то нет. Т.е. если например по вертикали камень расположен на расстоянии 10 , то если он хоть на небольшой угол отклонен по диагонали - то расстояние очевидно больше. Но вот если мы прыгнули на корень квадратный из 17, то как рассчитывать максимальную длину следующего прыжка? На что умножать 4/5 - на точное значение, а потом округлить, или сначала округлить, а потом умножить? Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.
[quote="вопрос"]Если нам понятно, что длина больше - то нет. Т.е. если например по вертикали камень расположен на расстоянии 10 , то если он хоть на небольшой угол отклонен по диагонали - то расстояние очевидно больше.[/quote] Но вот если мы прыгнули на корень квадратный из 17, то как рассчитывать максимальную длину следующего прыжка? На что умножать 4/5 - на точное значение, а потом округлить, или сначала округлить, а потом умножить? Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.
|
|
|
|
Добавлено: Вт апр 12, 2011 22:37 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
Надеюсь подробное изложение Хищника не ввело кого-то в заблуждение - там показан теоретически лучший вариант реально решенине будет хужe
Надеюсь подробное изложение Хищника :idea: не ввело кого-то в заблуждение - там показан [i]теоретически[/i] лучший вариант реально решенине будет хужe
|
|
|
|
Добавлено: Вт апр 12, 2011 22:30 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
Хищник писал(а): вопрос писал(а): это вопрос а не задача, впрочем, это часть задачи Так я уже несколько вариантов привел. Вот если допустимая длина прыжка 10, а до нового камня 10.1, то прыгать можно или нет? Если нам понятно, что длина больше - то нет. Т.е. если например по вертикали камень расположен на расстоянии 10 , то если он хоть на небольшой угол отклонен по диагонали - то расстояние очевидно больше.
[quote="Хищник"][quote="вопрос"]это вопрос а не задача, впрочем, это часть задачи[/quote] Так я уже несколько вариантов привел. Вот если допустимая длина прыжка 10, а до нового камня 10.1, то прыгать можно или нет?[/quote] Если нам понятно, что длина больше - то нет. Т.е. если например по вертикали камень расположен на расстоянии 10 , то если он хоть на небольшой угол отклонен по диагонали - то расстояние очевидно больше.
|
|
|
|
Добавлено: Вт апр 12, 2011 22:22 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
вопрос писал(а): это вопрос а не задача, впрочем, это часть задачи Так я уже несколько вариантов привел. Вот если допустимая длина прыжка 10, а до нового камня 10.1, то прыгать можно или нет?
[quote="вопрос"]это вопрос а не задача, впрочем, это часть задачи[/quote] Так я уже несколько вариантов привел. Вот если допустимая длина прыжка 10, а до нового камня 10.1, то прыгать можно или нет?
|
|
|
|
Добавлено: Вт апр 12, 2011 22:16 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
Цитата: Во-вторых, не учитывается переход от плавающей точки к целочисленному представлению, который, кстати, не оговорен и в условии. Если длина прыжка стала 0.99, то прыгать нельзя? Цитата: при каких условиях возможно решение с использованием только целых чисел это вопрос а не задача, впрочем, это часть задачи
[quote]Во-вторых, не учитывается переход от плавающей точки к целочисленному представлению, который, кстати, не оговорен и в условии. Если длина прыжка стала 0.99, то прыгать нельзя? [/quote] [quote][b]при каких условиях возможно[/b] решение с использованием только целых чисел[/quote]это [i]вопрос[/i] а не задача, впрочем, это часть задачи
|
|
|
|
Добавлено: Вт апр 12, 2011 22:06 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
Максимальная длина прыжков представляет собой геометрическую прогрессию. Сумма ее 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. Для каждого последующего прыжка пишем функцию "теоретически можно допрыгнуть", которая будет вычислять сумму бесконечного числа членов геометрической прогрессии с начальным членом, равным расстоянию прыжка до этого камня. И далее рекурсивно, пока не допрыгаем не теоретически, а практически.
Максимальная длина прыжков представляет собой геометрическую прогрессию. Сумма ее 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. Для каждого последующего прыжка пишем функцию "теоретически можно допрыгнуть", которая будет вычислять сумму бесконечного числа членов геометрической прогрессии с начальным членом, равным расстоянию прыжка до этого камня. И далее рекурсивно, пока не допрыгаем не теоретически, а практически.
|
|
|
|
Добавлено: Вт апр 12, 2011 21:33 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
мне кажется метод «обратной волны» как раз-таки приведет к перебору всех возможных путей, т.к. обратный проход стремится максимизировать первоначалтный прыжок и следовательно чтобы найти минимальный нужно перебрать все пути
мне кажется метод «обратной волны» как раз-таки приведет к перебору всех возможных путей, т.к. обратный проход стремится максимизировать первоначалтный прыжок и следовательно чтобы найти минимальный нужно перебрать все пути
|
|
|
|
Добавлено: Вт апр 12, 2011 20:55 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
WingLion писал(а): А "волной" с обратного берега пройти не проще? Да и первым пробуем самый ближайший камень.
[quote="WingLion"]А "волной" с обратного берега пройти не проще?[/quote]Да и первым пробуем самый ближайший камень.
|
|
|
|
Добавлено: Вт апр 12, 2011 17:00 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
А "волной" с обратного берега пройти не проще? По обратному правилу соотношения прыжков. Идем на все камни сразу (они становятся "вторым берегом"), с них смотрим, куда можно попасть еще и так несколько раз, пока не доберемся до другого берега, не доберемся - значит и прямого пути нет.
А "волной" с обратного берега пройти не проще? По обратному правилу соотношения прыжков. Идем на все камни сразу (они становятся "вторым берегом"), с них смотрим, куда можно попасть еще и так несколько раз, пока не доберемся до другого берега, не доберемся - значит и прямого пути нет.
|
|
|
|
Добавлено: Вт апр 12, 2011 08:35 |
|
|
|
|
|
Заголовок сообщения: |
Re: Задача "нерешительный кенгуру" |
|
|
а это уже зависит от других эвристик ))
поэтому предлагаю еще для каждого пройденного камня запоминать макс. допустимую длину прыжка при котором берег из этого камня не достижим (если достижм то дальше нечего делать) -- тогда при повторном попадании на камень можно сравнивать текущую возможную длину прыжка с той что "записана на камне" и делать вывод стоит ли продолжать путь или вернуться назад
а это уже зависит от других эвристик ))
поэтому предлагаю еще для каждого пройденного камня запоминать макс. допустимую длину прыжка при котором берег из этого камня не достижим (если достижм то дальше нечего делать) -- тогда при повторном попадании на камень можно сравнивать текущую возможную длину прыжка с той что "записана на камне" и делать вывод стоит ли продолжать путь или вернуться назад
|
|
|
|
Добавлено: Пн апр 11, 2011 14:12 |
|
|
|
|