|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Maxim Plaksin 2:468/57.113 12 Jul 2001 02:38:37
To : Oleg Ponomarev
Subject : Скобки расставить. Оптимальное вычисление выражения с несколькими п
--------------------------------------------------------------------------------
Однажды 16 Aug 37 в 18:24, Oleg Ponomarev писал к All:
OP> Hапример:
OP> 1 + x1*x2*x3 + x1*x2*x4 (6 умножений)
OP> легко преобразуется в
OP> 1 + x1*x2 * (x3 + x4) (3 умножения)
судя по этому примеру, алгоритм можно представить как рекурсию:
описываю образно, думаю сам додумаешь как это формализовать, т.к. особо
напрягаться летом неохота.
в начале, представляем выражение в виде структуры, в которой, каждой группе
множителей Xq,Xw,Xe...Xr ставим в соответствие запись, в которой содержатся
индексы всех иксов, т.е. получится нечто такое: <q,w,e,...r> теперь наша задача
сводится к тому, что бы брать попарно две таких записи, находить в них
одинаковые индексы и "выносить их за скобки", а что бы это получилось как можно
оптимальнее, нам на помощь приходит рекурсия:
суть рекурсии в данном случае будет заключаться в переборе всех возможных
комбинаций "вынесения" общих множетелей и нахождение самого короткого выражения
(в данном случае, как я понял, главным критерием является колличество умножений
в выражении)
насчет структуры я пошутил :) там нужно нечто более мудреное, т.к. кроме
индексов, надо запоминать еще что у нас после вынесения множителей получилось в
скобках и кроме этого, сами скобки так же могут быть общими множителями, но не
пугайся - внимательно представь себе эти преобразования и ты обязательно
найдешь закономерности, которые и будут нужным алгоритмом.
прямо перед отправкой мне в голову пришла мысль:
когда после вынесения общего множителя получаем скобки, их можно обозначить
введением новой переменной, а ее соответствие этим скобкам запомнить где-то в
памяти (и каждый раз, после вынесения общего множителя, проверять - а нет-ли
у нас уже соответствующей подстановки?), тогда алгоритм упрощается. после того,
как получится выражение, не подлежащее дальнейшей оптимизации, к нему применить
обратное действие - подставить вместо введенных переменных соответствующие им
скобки, после чего пересчитать к-во умножений и зделать вывод об оптимальности
результата.
OP> В моем случае количество переменных может достигать 70-ти,
OP> а количество комбинаций их различных произведений нескольких тясяч.
вариантов перебора будет _очень_ много, но в итоге ты получишь наиболее
оптимальное произведение
OP> Hаверняка, в компиляторах применяется некие приемы оптимизации
OP> вычисления выражений. Какие? Что лучше применить мне в моем случае?
если в _итоге_ ничего не получится - напиши мне мылом, я попробую тогда сам
написать программу...
bYe..
---
* Origin: Люблю экстрeмальный спорт - серфинг в net-mail'e... (2:468/57.113)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
