ПРИМЕР ПОЛНОГО АНАЛИЗА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ О СУММЕ



Формулировка задачи и асимптотическая оценка

Словесно задача о сумме формулируется как задача нахождения таких чисел из данной совокупности, которые в сумме дают заданное число, классически задача формулируется в терминах целых чисел [6].

В терминах структур данных языка высокого уровня задача формулируется, как задача определения таких элементов исходного массива S из N чисел, которые в сумме дают число V (отметим, что задача относится к классу NPC).

Детальная формулировка:
Дано: Массив S[i], i={1, N} и число V.
Требуется: определить такие Sj, что Sj=V

Тривиальное решение определяется равенством V=Sum, где Sum= Si , условия существования решения имеют вид:

Min {S[i], i=1,N} =< V =< Sum.

Получим асимптотическую оценку сложности решения данной задачи для алгоритма, использующего прямой перебор всех возможных вариантов. Поскольку исходный массив содержит N чисел, то проверке на равенство V подлежат следующие варианты решений:

o V содержит 1 слагаемое вариантов;

o V содержит 2 слагаемых вариантов;

o V содержит 3 слагаемых вариантов;

o и т.д. до проверки одного варианта с N слагаемыми.

Поскольку сумма биномиальных коэффициентов для степени N равна - и для каждого варианта необходимо выполнить суммирование (с оценкой O(N)) для проверки на V, то оценка сложности алгоритма в худшем случае имеет вид:

(7.1)

Алгоритм точного решения задачи о сумме (метод перебора)

Определим вспомогательный массив, хранящий текущее сочетание исходных чисел в массиве S, подлежащих проверке на V – массив Cnt[j], элемент массива равен «0», если число S[j] не входит в V и равен «1», если число S[j] входит в V

Решение получено, если V = S[j]*Cnt[j].

Могут быть предложены следующие две реализации механизма полного перебора вариантов:

o перебор по всевозможным сочетаниям из k элементов по N, т.е. сначала алгоритм пытается представить V как один из элементов массива S, затем перебираются все возможные пары, затем все возможные тройки и т.д.;

o перебор по двоичному счётчику, реализованному в массиве Cnt: Вторая идея алгоритмически более проста и сводится к решению задаче об увеличении двоичного счётчика в массиве Cnt на «1»:

o при 00...0111 увеличение на «1» приводит к сбросу всех правых «1» и установке в «1» следующего самого правого «0»;

o при 00...1000, когда последний элемент счетчика равен «0» увеличение на «1» приводит к переустановке последнего элемента в массиве Cnt с «0» в «1».

Рассматривая массив Cnt как указатель на элементы массива S, подлежащие суммированию в данный момент, мы производим суммирование и проверку на V, до тех пор, пока решение не будет найдено или же безрезультатно будут просмотрены все возможные варианты.

Таким образом, алгоритм точного решения задаче о сумме методом прямого перебора имеет в формальной системе языка высокого уровня следующий вид:


Дата добавления: 2018-02-28; просмотров: 730; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!