|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 11 Jul 2001 19:35:33
To : All
Subject : Re: Скобки расставить. Оптимальное вычисление выражения с несколькими п
--------------------------------------------------------------------------------
"Oleg Ponomarev" <O.Ponomarev@VAZ.RU> wrote in message
news:3B43FACE.2DB3@vaz.ru...
> > U> Итак. Есть выражение представленное ввиде суммы произведений
> > U> нескольких переменных. Каким образом можно преобразовать его
> > U> так, что бы минимизировать количество умножений (очень
> > U> "дорогой" операции в моем случае). Причем, коэффициэнты у всех
> > U> произведений равны единице (уж не знаю, облегчит ли это задачу :)
>
> Меня интересует, имеено алгоритм упрощения подобных выражений,
> сам принцип. Просто мне кажется, что он уже существует и я не хочу
> изобретать велосипед.
>
Возьмем полином, например
1+x*y+y+y*y*y+x*y*z+z+z*z
посчитаем сколько умножений используется для каждой переменной
во всех слагаемых. Причем внутри одного слагаемого считается
только одно умножение для каждой переменной, соответственно
?слагаемого x y z
1-е 0 0 0
2-е 1 1 0
3-е 0 1 0
4-е 0 1 0
5-е 1 1 1
6-е 0 0 1
7-е 0 0 1
сумма: 2 4 3
То есть "у" встречается чаще, так вынесем ее за скобки
(заменим 4 умножения на одно).
1+y*(x+1+y*y+z*x)+z+z*z
тот же самый подход применяем опять на всех уровнях -
на внешнем и внутри каждых скобкок.
Получим
1+y*(x*(1+z)+1+y*y)+z*(1+z)
Возможно прийдем не к оптимальному результату,
но с этого хотя бы можно начать. По крайней мере
для полинома от одного параметра этот подход
приведет к схеме Горнера.
Второй шаг - трактовка отдельных блоков как
самостоятельных элементов. В данном случае,
например (1+z) вполне можно считать отдельной
переменной и считать ее один раз.
Hу а дальше ... можно наверное еще чего нибудь
придумать :).
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
