Задача с interview

Haskell · Post by **Haskell** » 29 Jul 2002 22:07

Даны n натуральных чисел x1,x2,...,xn и некоторое натуральное число N. Требуется за время порядка O(nN), используя O(N) памяти, определить можно ли выбрать несколько чисел xi из x1...xn так, чтобы их сумма равнялась N.

Bobo · Post by **Bobo** » 29 Jul 2002 22:29

[quote:bad5291852="Haskell"]Даны n натуральных чисел x1,x2,...,xn и некоторое натуральное число N. Требуется за время порядка O(nN), используя O(N) памяти, определить можно ли выбрать несколько чисел xi из x1...xn так, чтобы их сумма равнялась N.[/quote:bad5291852]

Забавно. Pешения быть не должно.
А если я докажу, что невозможно, ето будет решением?

Bobo · Post by **Bobo** » 30 Jul 2002 03:31

Пусть такой алгоритм существует.
Тогда, применив его n раз, выбрасывая по одному числа из набора, мы [b:c4ca42c38b]найдем[/b:c4ca42c38b] подмножество с суммой N (возможно пустое) за время О(n*n*N).
Быстрейший алгоритм, известный на Август 2001, решает эту задачу за О(n*2^(n/2)).
Ref: Menezes, Oorschot, Vanstone, "Handbook of Applied Cryptography", CRC Press, ISBN: 0-8493-8523-7

Придумать алгоритм я даже не пытаюсь. С удовольствием посмотрю на него, если я не прав.

Да, насчет "докажу" я погорячился :wink:

Azazello · Post by **Azazello** » 30 Jul 2002 03:53

Забавно... Это задачка, известная как knapsack problem - на её базе пытаются строить альтернативные (не базирующиеся на factoring problem, как RSA и GP) крипто-системы.

Andrey S · Post by **Andrey S** » 30 Jul 2002 04:18

[quote:e398b09eff="Azazello"]Забавно... Это задачка, известная как knapsack problem - на её базе пытаются строить альтернативные (не базирующиеся на factoring problem, как RSA и GP) крипто-системы.[/quote:e398b09eff]Хм. Всё-таки рюкзвк это поиск чисел, а здесь требуется лишь определить возможность решения. Но, вообще, неслабо такое на интервью схлопотать, а?

Azazello · Post by **Azazello** » 30 Jul 2002 04:50

[quote:9fa8ee9509="Andrey S"][quote:9fa8ee9509="Azazello"]Забавно... Это задачка, известная как knapsack problem - на её базе пытаются строить альтернативные (не базирующиеся на factoring problem, как RSA и GP) крипто-системы.[/quote:9fa8ee9509]Хм. Всё-таки рюкзвк это поиск чисел, а здесь требуется лишь определить возможность решения. Но, вообще, неслабо такое на интервью схлопотать, а?[/quote:9fa8ee9509]
Яйца бы отрывал за такие вопросы на интервью (если конечно интервьюируемый не хлещется знанием криптографии)...
Моя позиция при интервью проста - никто не обязан знать всего, но если уж пишешь в резюме, что что-то знаешь - будь готов к вопросам.

Haskell · Post by **Haskell** » 30 Jul 2002 06:47

[quote:6526644204="Bobo"]
Забавно. Pешения быть не должно.
А если я докажу, что невозможно, ето будет решением?[/quote:6526644204]

Действительно, похоже на задачу о рюкзаке. Но решение есть. Посмотрите более внимательно на то, _что_ надо найти (решение не набор чисел, а Да или Нет) и какие ресурсы можно использовать.

kot2002 · Post by **kot2002** » 30 Jul 2002 08:54

искать так чтобы сумма нескольких идущих ПОДРЯД членов равнялась бы N?
Тогда при N>n получим O(n*n),
а при N<n -O(Nn).

Bobo · Post by **Bobo** » 30 Jul 2002 16:42

[quote:fb5ed0718b="Haskell"][quote:fb5ed0718b="Bobo"]
Забавно. Pешения быть не должно.
А если я докажу, что невозможно, ето будет решением?[/quote:fb5ed0718b]

Действительно, похоже на задачу о рюкзаке. Но решение есть. Посмотрите более внимательно на то, _что_ надо найти (решение не набор чисел, а Да или Нет) и какие ресурсы можно использовать.[/quote:fb5ed0718b]

Дык я ж вроде показал, что эти две задачи эквивалентны, т.е. если "определительный" вариант решается за О(t), то "вычислительный" вариант решается за O(n*t).
Впридачу, если это верно, то очень похоже, что "определительная" задача - NP-полная.

Ресурсы, которые предложено использовать, выглядят странно. Вы уверены, что не пропустили условия типа "каждое следующее число больше суммы всех предыдущих"?
Ну если говорите, что решение есть - попробуем поискать...

olg2002 · Post by **olg2002** » 30 Jul 2002 17:56

Горе от ума...

Задача-то банальная. Но, видимо, решить ее на интервью по силам
либо толковому новичку, который не знает, что задача "решения
не имеет", либо тому, у кого мозги еще не засохли.
Ограничения на ресурсы включают N, что меняет картину самым
драматическим образом.

kot2002 · Post by **kot2002** » 30 Jul 2002 21:42

[quote:c754afe4ab="olg2002"]Горе от ума...

Задача-то банальная. Но, видимо, решить ее на интервью по силам
либо толковому новичку, который не знает, что задача "решения
не имеет", либо тому, у кого мозги еще не засохли.
Ограничения на ресурсы включают N, что меняет картину самым
драматическим образом.[/quote:c754afe4ab]
Что Вы имели в виду?

olg2002 · Post by **olg2002** » 30 Jul 2002 22:39

Я имел ввиду следующее

[code:1:339099ef7d]
bool A[N+1];

A[0] = true;
for ( int i=0; i<n; i++ ) {
for ( int j=N; j>=x[i]; j-- ) {
if ( A[j - x[i]] ) {
if ( j == N ) {
return true;
}
A[j] = true;
}
}
}
return false;
[/code:1:339099ef7d]

Bobo · Post by **Bobo** » 30 Jul 2002 23:34

Ага. Я тоже решил. Только памяти испосльзовал n*N.
Обясню словами.
bool S[n+1, N+1]
S[i, j] хранит true если среди первых i чисел есть подмножество с суммой j.
Заполняем так:
S[i, 0] = false для всех i,
S[1, j] = true если X[1] = j,
Дальше, S[i,,j] = S[i-1, j] OR S[i-1, j - x[i]]

Как только получаем true в последней колонке - return true

:oops:

kot2002 · Post by **kot2002** » 31 Jul 2002 00:25

если из одномерного массива выбирать так чтобы сколько то подряд равнялись бы N то тривиально.
Если перебирать всевозможные сочетания то невозможно.

chuchuva · Post by **chuchuva** » 31 Jul 2002 08:52

[quote:bddbba0b63="kot2002"]если из одномерного массива выбирать так чтобы сколько то подряд равнялись бы N то тривиально.
Если перебирать всевозможные сочетания то невозможно.[/quote:bddbba0b63]
kot2002, ты когда-нибудь слышал о динамическом программировании?..
Решение olg2002 рулит.

kot2002 · Post by **kot2002** » 31 Jul 2002 23:10

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

olg2002 · Post by **olg2002** » 01 Aug 2002 00:37

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

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

Bobo · Post by **Bobo** » 01 Aug 2002 17:30

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

Haskell · Post by **Haskell** » 01 Aug 2002 18:36

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

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

.

Bobo · Post by **Bobo** » 01 Aug 2002 20:56

[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 · Post by **Haskell** » 01 Aug 2002 21:37

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

Haskell · Post by **Haskell** » 01 Aug 2002 21:46

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

Bobo · Post by **Bobo** » 01 Aug 2002 22:49

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

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

Привет

Задача с interview

Задача с interview

Re: Задача с interview

Re: Задача с interview

А может имелось в виду

Re: Задача с interview

Может расшифруете?

Тупой я или условия задачи неправильны

Re: Тупой я или условия задачи неправильны

Re: Тупой я или условия задачи неправильны

Re: Тупой я или условия задачи неправильны