Задача с interview

[kot2002]

[quote:76c21f8f74="chuchuva"][quote:76c21f8f74="kot2002"]если из одномерного массива выбирать так чтобы сколько то подряд равнялись бы N то тривиально.
Если перебирать всевозможные сочетания то невозможно.[/quote:76c21f8f74]
kot2002, ты когда-нибудь слышал о динамическом программировании?..
Решение olg2002 рулит.[/quote:76c21f8f74]
Не знаю ни про динамическое ни про кинематическое.
Но из простых соображений нужно перебирать всевозможные сочетания.
Да и С я почти не знаком, а жаль. Но алгоритм, вроде, не зависит от языка.
С удовольствием бы узнал (и может быть не только я) как решается задача.
На простом человеческом языке.

[olg2002]

[quote:5bb0b02b0b="kot2002"]
С удовольствием бы узнал (и может быть не только я) как решается задача.
На простом человеческом языке.[/quote:5bb0b02b0b]

Идея алгоритма заключается в том, чтобы помечать числа от 0 до N,
которые могут быть представлены в виде суммы Хi. Начинаем с того,
что помечаем 0. Далее берем Х1, добавляем ко всем уже помеченным
(т.е. 0) и помечаем все новые получаемые числа (т.е. Х1).
Берем по-очереди Х2, Х3, ..., добавляем ко всем уже помеченным
и помечаем все новые получаемые числа. Если однажды мы помечаем
N, заканчиваем работу с результатом "успех". Если перебрали все Хi,
заканчиваем работы с результатом "неудача".
Памяти для пометок нужно O(N), время работы O(n*N).

[Bobo]

Ну и в моем алгоритме та же идея, только не оптимально реализованная. Я словами ее уже обяснил.
Обший принтсип динамического программирования такой:
1. Пишется рекурсивный алгоритм, который перебирает дерево всех вариантов.
В данном случае - все подмножества.
2. Ишутся правила, которые позволяют отрезать потенциально ненужные ветки у етого дерева.
В данном случае - подмножества с суммой, больше N можно выкинуть, и из двых подмножеств одинаковой длины с одинаковой суммой одно можно выкинуть.
3. Щитаем, сколько листьев остается в дереве. Если достаточно мало - писехм итеративный алгоритм, который их генерит.
В нашем случае - осталось не больше N+1 на каждом из n уровней дерева.
Строим табличку и заполняем.
Получаем в точности алгоритм, который я привел.
Olg2002 использовал то, что нас не интересует, какое именно множество имеет сумму К, и уложился в ограничение по памяти.

[Haskell]

[quote:4d200e9615="Bobo"]
Olg2002 использовал то, что нас не интересует, какое именно множество имеет сумму К, и уложился в ограничение по памяти.[/quote:4d200e9615]

Не совсем верно. Немного модифицировав алгоритм (будем хранить в ячейке i индекс xk, благодаря которому мы туда попали), мы в результате за то же время и с той же памятью сможем найти конкретные номера x, которые в сумме дают N. Такие невероятные скорости получаются благодаря большой памяти .

[Bobo]

[quote:6355bd6a63="Haskell"][quote:6355bd6a63="Bobo"]
Olg2002 использовал то, что нас не интересует, какое именно множество имеет сумму К, и уложился в ограничение по памяти.[/quote:6355bd6a63]

Не совсем верно. Немного модифицировав алгоритм (будем хранить в ячейке i индекс xk, благодаря которому мы туда попали), мы в результате за то же время и с той же памятью сможем найти конкретные номера x, которые в сумме дают N. Такие невероятные скорости получаются благодаря большой памяти .[/quote:6355bd6a63]

Ага. Только если хранить в табличке индексы вместо да/нет, получится ровно столько памяти, сколько у меня. Если искать конкретный набор, то нужно либо n*N памяти, либо n*n*N времени (если применить метод Olg2002 n раз, как я предлагал, когда показывал "еквивалентность" задач).
Что касается пригодности такого метода для криптоанализа, то достаточно выбрать N > 2^(n-1), чтоб задача перстала быть "полиномиальной", даже без ограничений на память.
Кстати, динамическое программирование я использовал реально один раз в жизни для оптимизационной задачи. Мне его показал один умный инженер, и я тогда мало чего в нем понял. Сейчас понял гораздо больше. Всем спасибо

[Haskell]

Никак не могу понять откуда берется N*n. Такая оценка получается, если мы хотим найти все возможные суммы, а не только какую-нибудь одну. Если же нам достаточно одной, то хватит O(N*log n) (c O(N) я погорячился).

[Haskell]

Никак не могу понять откуда берется N*n. Такая оценка получается, если мы хотим найти все возможные суммы, а не только какую-нибудь одну. Если же нам достаточно одной, то хватит O(N*log n) (c O(N) я погорячился).

[Bobo]

[quote:491deb591e="Haskell"]Никак не могу понять откуда берется N*n. Такая оценка получается, если мы хотим найти все возможные суммы, а не только какую-нибудь одну. Если же нам достаточно одной, то хватит O(N*log n) (c O(N) я погорячился).[/quote:491deb591e]

Согласен. N*log(n). Sorry.