Автор |
Сообщение |
12.07.2007 18:12:06
Тема: Ищу теорию
|
Тарас Зубык
Темы: 19
Сообщений: 28
Мой профиль
|
1.
*****
Пожалуйста, обьясните мне, что такое рекурсия с меморизацией.
Какие задачи на эту тему?
Если есть, то дайте теорию.
*****
2.
*****
Так же не знаю что такое Meet-in-the-Middle.
Какие задачи на эту тему, теория?
Буду очень благодарен.
*****
Большое СПАСИБО.
______________________
Thinking is positive
|
13.07.2007 09:28:39
Тема: Re:Ищу теорию
|
Михаил Долинский
Темы: 1982
Сообщений: 47183
Мой профиль
|
Сначала о задачах.
В курсе "Методы алгоритмизации" задачи группируются по разделам (IOI, USACO, ACM, Олимпиады по информатике), а потом темам.
Темы "Рекурсия с меморизацией" и "Meet-in-the-Middle" встречаются в разделах ACM и Олимпиады по информатике.
Теория по этим вопросам в курсе "Методы алгоритмизации" отсутствует, но пару слов могу сообщить.
1. "Рекурсия с меморизацией"
- часто при рекурсивных вычислениях выполняется одна и та же работа (при входе в рекурсию с одними и теми же значениями ее параметров). В случае, если для решения критично время выполнения, можно достичь существенного ускорения ЗАПОМИНАЯ (memory - память) в массивах результат работы рекурсивной процедуры/функции для заданных параметров. Если один параметр - в одномерном массиве, два параметра - в двумерном массиве, три параметра - в трехмерном массиве и т.д. Понятно, что такой программе может потребоваться значительно больше памяти, поэтому в конкретных задачах могут быть компромиссы - когда что-то помнится, а что-то перевычисляется при каждом входе в рекурсию.
2. "Meet-in-the-Middle"
Дословный перевод "Встретимся в средине"
Существуют переборные задачи, число вариантов в которых растет экспоненциально на каждом шагу. Тогда при некотором определенном числе таких шагов, число вариантов становится "неподъемным".
"Meet-in-the-Middle" предлагает вести два перебора:
Один - от начального состояния, другой - от конечного состояния.
И пытаться "сопоставить" результаты этих переборов "в средине".
Если сопоставить удалось - значит есть варинт перехода из начального состояния в конечное, иначе - нет.
|
23.08.2007 22:59:01
Тема: Re:Ищу теорию
|
Dima Megov
Темы: 1
Сообщений: 5
Мой профиль
|
Неплохое объяснение решения задачи при помощи Meet-in-the-middle можно прочитать на topcoder.com.
А именно на разборе задачи KnapsackProblem из TCHS07 Semifinal Round от Saturday, May 19, 2007.
|
24.08.2007 10:50:44
Тема: Re:Ищу теорию
|
Михаил Долинский
Темы: 1982
Сообщений: 47183
Мой профиль
|
Спасибо, Дима - а можно прямую ссылку?
Заранее благодарен.
|
07.11.2007 17:24:35
Тема: Re:Ищу теорию
|
Dima Megov
Темы: 1
Сообщений: 5
Мой профиль
|
Пожалуйста :
http://www.topcoder.com/tc?module=Static&d1=hs&d2=match_editorials&d3=tchs07Semi
|
22.10.2017 23:31:02
Тема: Re:Ищу теорию
|
Ольга Захарченко
Темы: 7
Сообщений: 46
Мой профиль
|
Подскажите, пожалуйста, правильно ли я понял из статьи на википедии, что манхеттенское расстояние есть неизменное расстояние между двумя точками, не зависящее от конкретного маршрута движения от точки до точки, но со специфическими ограничениями траектории:
1) двигаться только параллельно осям 0x и 0y;
2) двигаться только по направлению сокращения расстояния между точками, а точнее, не увеличивая расстояния между их проекциями на оси 0x и 0y.
P.S. А сфера применения, что-то вроде замены маршрута (составленного при вышеуказанных ограничениях к траектории) на равноценные по расстоянию (при аналогичных ограничениях), или шахматные задачи?
|
23.10.2017 12:41:29
Тема: Re:Ищу теорию
|
Михаил Долинский
Темы: 1982
Сообщений: 47183
Мой профиль
|
В наших задачах всё КОНКРЕТНО
M:=abs(x1-x2)+abs(y1-y2);
для точек (x1,y1) и (x2,y2)
|
23.01.2023 00:44:11
Тема: Re:Ищу теорию
|
Артём Мороз
Темы: 1
Сообщений: 2
Мой профиль
|
Где можно почитать теорию на задачи по битмаскам и побитовые операции?
|
23.01.2023 21:33:27
Тема: Re:Ищу теорию
|
Иван Ложечник
Темы: 2
Сообщений: 8
Мой профиль
|
Артём Мороз:
Где можно почитать теорию на задачи по битмаскам и побитовые операции?
https://brestprog.by/topics/bitmasks/
|
|