Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Юмор > Решить небольшую задачку

Автор: Дрон 18.8.2010, 11:35

http://www.getacoder.com/projects/solve%20p%20vs%20np_132036.html

Цитата

Description
The project consists of writing a program in the language of your choice that answers the following question:

Given a set of integers, does some nonempty subset of them sum to 0?

For instance, the program should be able to find if a subset of the set {−2, −3, 15, 14, 7, −10} adds up to 0? The answer is "yes, because {−2, −3, −10, 15} add up to zero".

PS: The program should run in polynomial time.

Комментарии бесконечно радуют. Или огорчают. Смотря что вы ожидаете smile

Автор: Shaggie 18.8.2010, 11:56

Отлично!

Автор: azesmcar 18.8.2010, 13:21

Весело

повеселили комментарии типа

Цитата

I can do this for you in php or javascript. - 300$

начинаешь понимать откуда столько загубленных проектов smile

люди берутся за проект абсолютно не разбираясь в теме. smile

Цитата(Дрон @ 18.8.2010, 11:35

)

Смотря что вы ожидаете

да откровенно говоря ничего большего smile

Автор: Дрон 18.8.2010, 13:31

Цитата(azesmcar @ 18.8.2010, 13:21

)

люди берутся за проект абсолютно не разбираясь в теме. smile

Ага, очень показательно:

Цитата

We have worked on such project recently and we can do this one too

Кстати, для тех кто не следит за новостями computer science. Там кто-то пошутил, ответив:

Цитата

VinayDeolalikar
I think I have done this.
bid amount US$1,000,000

Так вот этот Vinay Deolalikar это сотрудник HP, который недавно опубликовал статью с доказательством P != NP. Правда, похоже там всё-таки нашлись ошибки, но это не важно.

Автор: Zloxa 8.9.2010, 22:36

Прошу прощения, не объясните ли в чем тут юмор?
Быть может в этой строке? Я не до конца понял ее смысл.

Цитата(Дрон @ 18.8.2010, 11:35

)

The program should run in polynomial time.

Ка кбы там ни было, задачка мне понравилась. /*Если я конечно ее правильно понял.*/
Размялся

Код


with recursive
      src as  (select -2 val
              union all select -3
              union all select 15
              union all select 14
              union all select 7
              union all select -10
              )
      ,src_prep as (select val, row_number () over () rn from src)
      ,rec (smc,sm,rn) as (
                       select to_char(val,'FM999999'),val,rn from src_prep
                       union all
                       select smc||'+'||src_prep.val,src_prep.val+sm, src_prep.rn
                         from rec,src_prep
                         where rec.rn < src_prep.rn
                      )
 select smc from rec
 where sm = 0
 limit 1;
     smc
--------------
 -2+-3+15+-10
(1 row)

Автор: Shaggie 9.9.2010, 06:23

Zloxa, именно в этой строчке шутка и зарыта. Пример классический, именно он приведён в http://en.wikipedia.org/wiki/P_versus_NP_problem.

P.S. У мну код проще получился ;)

Код


-- Haskell ghci

:m Data.List
let list = [-2, -3, 15, 14, 7, -10]
mapM_ print [seq | seq <- tail $ subsequences list, sum seq == 0]

Добавлено через 2 минуты и 11 секунд
Даже не конкретно в этой строчке, а в том, что топовые фрилансеры, даже не разобравшись в сути проблемы, налетели предлагать свои услуги по принципу "сначала получить бы аванс, а там видно будет"

Автор: Zloxa 9.9.2010, 09:34

Shaggie, спасибо за ссылку. Узнал много умных слов. В обозримом будущем не примену ими блестнуть перед коллегами ;)

Автор: sergejzr 20.9.2010, 20:33

Классная шутка smile

)))

Цитата(azesmcar @ 18.8.2010, 12:21

)

начинаешь понимать откуда столько загубленных проектов smile люди берутся за проект абсолютно не разбираясь в теме. smile