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

Дрон

Дата 18.8.2010, 11:35 (ссылка)

(голосов:4)

Загрузка ...

Java-ненавистник :)

Профиль
Группа: Участник Клуба
Сообщений: 3179
Регистрация: 29.12.2002
Где: Санкт-Петербург

Репутация: 2
Всего: 92

Ссылка на задачу

Цитата

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 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 570
Регистрация: 21.12.2006
Где: outer space

Репутация: 3
Всего: 72

Отлично!

--------------------

Цитата(alina3000 @ 6.3.2014, 10:47

)

Сорри что не по теме

azesmcar

Дата 18.8.2010, 13:21 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: нет
Всего: 211

Весело

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

Цитата

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

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

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

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

)

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

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

Это сообщение отредактировал(а) azesmcar - 18.8.2010, 13:25

Дрон

Дата 18.8.2010, 13:31 (ссылка)

(голосов:2)

Загрузка ...

Java-ненавистник :)

Профиль
Группа: Участник Клуба
Сообщений: 3179
Регистрация: 29.12.2002
Где: Санкт-Петербург

Репутация: 2
Всего: 92

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Чо?

Профиль
Группа: Завсегдатай
Сообщений: 3473
Регистрация: 12.9.2008

Репутация: 3
Всего: 161

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

Цитата(Дрон @ 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)

Это сообщение отредактировал(а) Zloxa - 8.9.2010, 22:39

--------------------

Достоверно известно, что 89% людей доверяют статистике взятой с потолка smile

Shaggie

Дата 9.9.2010, 06:23 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 570
Регистрация: 21.12.2006
Где: outer space

Репутация: 3
Всего: 72

Zloxa, именно в этой строчке шутка и зарыта. Пример классический, именно он приведён в википедии.

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 секунд
Даже не конкретно в этой строчке, а в том, что топовые фрилансеры, даже не разобравшись в сути проблемы, налетели предлагать свои услуги по принципу "сначала получить бы аванс, а там видно будет"

--------------------

Цитата(alina3000 @ 6.3.2014, 10:47

)

Сорри что не по теме

Zloxa

Дата 9.9.2010, 09:34 (ссылка)

(нет голосов)

Загрузка ...

Чо?

Профиль
Группа: Завсегдатай
Сообщений: 3473
Регистрация: 12.9.2008

Репутация: 3
Всего: 161

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

--------------------

Достоверно известно, что 89% людей доверяют статистике взятой с потолка smile

sergejzr

Дата 20.9.2010, 20:33 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 17
Всего: 360

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

)))

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

)

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

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Юмор \| Следующая тема »