[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->Обсуждение теории
Автор Сообщение
Тарас Зубык

Темы: 19
Сообщений: 28

Мой профиль
1.
*****
Пожалуйста, обьясните мне, что такое рекурсия с меморизацией.
Какие задачи на эту тему?
Если есть, то дайте теорию.
*****

2.
*****
Так же не знаю что такое Meet-in-the-Middle.
Какие задачи на эту тему, теория?
Буду очень благодарен.
*****

Большое СПАСИБО.
______________________
Thinking is positive
Михаил Долинский

Темы: 1374
Сообщений: 32449

Мой профиль
Сначала о задачах.
В курсе "Методы алгоритмизации" задачи группируются по разделам (IOI, USACO, ACM, Олимпиады по информатике), а потом темам.
Темы "Рекурсия с меморизацией" и "Meet-in-the-Middle" встречаются в разделах ACM и Олимпиады по информатике.
Теория по этим вопросам в курсе "Методы алгоритмизации" отсутствует, но пару слов могу сообщить.

1. "Рекурсия с меморизацией"
- часто при рекурсивных вычислениях выполняется одна и та же работа (при входе в рекурсию с одними и теми же значениями ее параметров). В случае, если для решения критично время выполнения, можно достичь существенного ускорения ЗАПОМИНАЯ (memory - память) в массивах результат работы рекурсивной процедуры/функции для заданных параметров. Если один параметр - в одномерном массиве, два параметра - в двумерном массиве, три параметра - в трехмерном массиве и т.д. Понятно, что такой программе может потребоваться значительно больше памяти, поэтому в конкретных задачах могут быть компромиссы - когда что-то помнится, а что-то перевычисляется при каждом входе в рекурсию.

2. "Meet-in-the-Middle"
Дословный перевод "Встретимся в средине"
Существуют переборные задачи, число вариантов в которых растет экспоненциально на каждом шагу. Тогда при некотором определенном числе таких шагов, число вариантов становится "неподъемным".
"Meet-in-the-Middle" предлагает вести два перебора:
Один - от начального состояния, другой - от конечного состояния.
И пытаться "сопоставить" результаты этих переборов "в средине".
Если сопоставить удалось - значит есть варинт перехода из начального состояния в конечное, иначе - нет.
Dima Megov

Темы: 1
Сообщений: 5

Мой профиль
Неплохое объяснение решения задачи при помощи Meet-in-the-middle можно прочитать на topcoder.com.
А именно на разборе задачи KnapsackProblem из TCHS07 Semifinal Round от Saturday, May 19, 2007.
Михаил Долинский

Темы: 1374
Сообщений: 32449

Мой профиль
Спасибо, Дима - а можно прямую ссылку?
Заранее благодарен.
Dima Megov

Темы: 1
Сообщений: 5

Мой профиль
Пожалуйста :
http://www.topcoder.com/tc?module=Static&d1=hs&d2=match_editorials&d3=tchs07Semi
Ольга Захарченко

Темы: 0
Сообщений: 22

Мой профиль
Подскажите, пожалуйста, правильно ли я понял из статьи на википедии, что манхеттенское расстояние есть неизменное расстояние между двумя точками, не зависящее от конкретного маршрута движения от точки до точки, но со специфическими ограничениями траектории:
1) двигаться только параллельно осям 0x и 0y;
2) двигаться только по направлению сокращения расстояния между точками, а точнее, не увеличивая расстояния между их проекциями на оси 0x и 0y.

P.S. А сфера применения, что-то вроде замены маршрута (составленного при вышеуказанных ограничениях к траектории) на равноценные по расстоянию (при аналогичных ограничениях), или шахматные задачи?

______________________
С уважением, Захарченко Сергей
(отец Захарченко Ольги)
Михаил Долинский

Темы: 1374
Сообщений: 32449

Мой профиль
В наших задачах всё КОНКРЕТНО

M:=abs(x1-x2)+abs(y1-y2);

для точек (x1,y1) и (x2,y2)
 
Индекс форума ->Олимпиадное программирование ->Обсуждение теории
Time:0,125