|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Maxim Plaksin 2:468/57.113 15 Jul 2001 20:33:16
To : Alex Cvetkov
Subject : Скобки расставить. Оптимальное вычисление выражения с несколькими п
--------------------------------------------------------------------------------
Однажды 19 Aug 37 в 21:15, Alex Cvetkov писал к Maxim Plaksin:
AC>>> Это будет 70! вариантов.
MP>> это будет несколько тысяч вариантов (если не больше)
AC> 70! означает факториал числа 70.
сорри, - воспринял как восклицание :-)
предполагаю, что это неверный вывод (насчет 70!), т.к. не всегда будут
находиться общие множители в произведениях и колличество таких несовпадений
будет увеличиваться пропорционально числу появляющихся скобок, так что рекурсия
будет не очень глубокой (порядка 10-30 вызовов функции оптимизации в _лучших_
случаях)
не глубокая рекурсия, да плюс ограниченное количество вариантов => бытсро!
как говорится: "...не легкО, а лЕгко!" (с) ?
MP>> во-первых за скорость вычислений, насколько я помню, не говорилось,
MP>> т.е. нужно любым способом прооптимизить и не важно, какие это заберет
MP>> ресурсы.
AC> Что то мне подсказывает что он умрет от старости раньше чем
AC> прооптимизирует. Быстрее будет считать вообще без оптимизации.
рекурсивный алгоритм - не такой уж страшный зверь. когда-то я писал прогу для
игры в шахматы (компьютер-человек) с использованием рекурсивного перебора всех
возможных ходов и должен сказать, что это не вычислялось мучительно долго, даже
для уровня рекурсии порядка 10-15 ходов.
тем более, можно ввести в алгоритм условия, отсекающие заведомо ложные
варианты. я ведь не предлагал выносить за скобки "все что движется", а
только общие множители :-)
так же, думаю, что обсуждать далее это не стоит без практической реализации,
поскольку мы всего-лишь высказываем свои имхи...
bYe..
---
* Origin: Люблю экстрeмальный спорт - серфинг в net-mail'e... (2:468/57.113)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
