Алгоритмы. Реккурентные соотношения - Помощь студентам

Intermediate · 26.02.2011, 13:51

Здравствуйте! Я на 2-ом курсе, изучаю алгоритмы и структуры данных, и мне нужна помощь в решении задачи.
Вот здесь задача №16 (полигон).

Задача по теме "реккурентные соотношения". Если ее решать в лоб, то потребуется n! операций. n<=50. Не вычислять же 50! операций

С другой стороны, при удалении одного ребра полигону можно сопоставить арифметическое выражение. Например, в примере, который там рассматривается, при удалении ребра 3 мы получим выражение
4 + (-7) + 5 * 2
Теперь задача сводится к тому, чтобы в этом выражении правильно расставить скобки, порядок выполнения операций так, чтобы значение получилось наибольшим. Вот только я не знаю, как это сделать за полиномиальное время. Подскажите, если можете. И вообще, в правильном ли я направлении смыслю? Может, в задаче вообще не требуется подобных аналогий?

Intermediate · 26.02.2011, 20:53

Если бы числа были строго положительными, то все было бы очень просто. Сначала провести все операции сложения, затем - умножения. Но они могут быть отрицательными. Может, кто-нибудь знаком с таким или решал что-то подобное?

Intermediate · 27.02.2011, 00:31

http://fvn2009.narod.ru/Olympiads/Ru...ds/Rules22.htm

Задача 3 - расстановка скобок. Тему можете закрывать
Вообще-то думал, что на форуме найдутся умные люди-алгоритмики.

26.02.2011, 13:51	#1
Intermediate Регистрация: 26.02.2011 Сообщений: 7	Алгоритмы. Реккурентные соотношения Здравствуйте! Я на 2-ом курсе, изучаю алгоритмы и структуры данных, и мне нужна помощь в решении задачи. Вот здесь задача №16 (полигон). Задача по теме "реккурентные соотношения". Если ее решать в лоб, то потребуется n! операций. n<=50. Не вычислять же 50! операций С другой стороны, при удалении одного ребра полигону можно сопоставить арифметическое выражение. Например, в примере, который там рассматривается, при удалении ребра 3 мы получим выражение 4 + (-7) + 5 * 2 Теперь задача сводится к тому, чтобы в этом выражении правильно расставить скобки, порядок выполнения операций так, чтобы значение получилось наибольшим. Вот только я не знаю, как это сделать за полиномиальное время. Подскажите, если можете. И вообще, в правильном ли я направлении смыслю? Может, в задаче вообще не требуется подобных аналогий?

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Задача из раздела Комбинаторные алгоритмы и алгоритмы на гра-фах в Паскале	Klik_1602	Помощь студентам	1	04.01.2011 01:18
Алгоритмы	CodeNOT	Общие вопросы C/C++	3	11.12.2010 19:20
алгоритмы	boomeer	Общие вопросы C/C++	6	04.12.2010 20:05
рекурентные соотношения	машко	Помощь студентам	2	22.06.2009 11:08
Рекуррентные соотношения и динамическое программирование.	DOOM514	Фриланс	3	08.01.2009 16:20

26.02.2011, 20:53	#2
Intermediate Регистрация: 26.02.2011 Сообщений: 7	Если бы числа были строго положительными, то все было бы очень просто. Сначала провести все операции сложения, затем - умножения. Но они могут быть отрицательными. Может, кто-нибудь знаком с таким или решал что-то подобное?

27.02.2011, 00:31	#3
Intermediate Регистрация: 26.02.2011 Сообщений: 7	http://fvn2009.narod.ru/Olympiads/Ru...ds/Rules22.htm Задача 3 - расстановка скобок. Тему можете закрывать Вообще-то думал, что на форуме найдутся умные люди-алгоритмики.