Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Re: имеет ли смысл с ней биться 31.08.06 19:19 Число просмотров: 2275
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 31.08.06 19:25 Количество правок: 1
|
> Сдается мне, что есть какой-то подход, хотя если доказано,
> что задача не полименальная, то имеет ли смысл с ней
> биться...
Доказанная полиноминальность говорит о том, что можно посчитать за 2**N или быстрее. Но это не значить, что нельзя быстрее. Например, можно сделать перебор с "большим" перешагиванием через "плохие" варианты и показать, что время будет расти не по 2**N.
У этой задачи есть два "классических" решения. Одно для целых чисел, при этом требует построения таблицы [N, S], где S - заданная сумма.
Другое решение - это алгоритм на основе списков. Кроме времени 2**N еще требуется 2**N памяти, и если учесть время на обработку этой кучи, то в худшем случае время стремиться к 2**N*N. Но у этого алгоритма есть плюс, итерируются только не тупиковые ветви поиска решения, а не все варианты.
|
- Задачка - leo 31.08.06 11:31 [2227]
|
|
|
подробно о проекте
Анализ криптографических сетевых...
