Жадный калкулятор -> Форум на Исходниках.Ру

	Наши проекты: Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту

Здравствуйте, Гость ! [18.97.9.174]

правила раздела Алгоритмы

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray

Новое голосование

Жадный калкулятор

albom

Сообщ. #1 , 23.11.03, 16:44

Senior Member

Профиль · PM

Поощрения: 2 Dgm

Рейтинг (т): 20

Есть такая задачка: дано выражение, состоящие из чисел и знаков операция (+, -, /), необходимо в этом выражении расставить скобки, что бы результат получился максимальным.

Например, если входные данные такие:

Цитата

3+4-2*4+2

то результат должен быть примерно такой:

Цитата

30
((3+(4-2))*4)+2

В общем, построил я две матрицы: max и min. В ячейке max[i,j] хранится максимальное значение, которое может получить выражение, которое начинается с i-ого числа и заканчивается j-им. Понятно, что в матрице min хранится минимальное значение.

Ясно, что ответом на задачу является число max[1,n] (где n - количество чисел в исходном выражении).

Вот только чего у меня не получается, так это по этим матрицам восстановить расположение скобок. Посоветуйте, как можно это сделать? Или какую дополнительную информацию нужно хранить вместе с этими матрицами?

Заранее спасибо за ответ.

Visitor

Сообщ. #2 , 23.11.03, 17:03

Profi

Профиль · PM

Поощрения: 1 Dgm

Рейтинг (т): 22

вместе с каждым числом в етих матрицах надо хранить и позицию знака, который объединяет два выражения... (max[5,12] = 10000, pos[5,12] = 7, т.е., чтобы получить max необходимо подвыражение с 5 по 7 (=max[5,7]) умножить на подвыражение с 8 по 12 (=max[8,12])...).

Или просто при восстановлении проходить по всем возможным знакам, сравнивая результат max[5,i] =-*/ max[i+1,12] с найденным максимумом max[5,12].

Сообщение отредактировано: Visitor - 23.11.03, 17:03

albom	Сообщ. #3 , 23.11.03, 19:34
Senior Member Профиль · PM Поощрения: 2 Dgm Рейтинг (т): 20	Спасибо за подсказку, думаю мне этого хватит...

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей:

[ Script execution time: 0.1219 ] [ 15 queries used ] [ Generated: 6.10.26, 00:52 GMT ]