Планируем конкурс

(jalt @ 29.05.2006 - время: 23:08) Ага. Только сначала придется устраивать конкурс на лучшее задание для конкурса, а потом уже конкурс по итогам того конкурса. Вот. Все меня поняли? :)
Имхо, для начала нужно провести конкурс по регламенту олимпиад. А уж потом крупные полезные проекты представлять.
Так уж и крупные? :)

Имхо конкурс на программирование должен быть как быстрые шахматы. Задание - ответ в течении десяти/тридцати минут (чур сигнатуры не подделывать! :)). А то если тут на сутки задание давать, то победит самый общительный.

JeyLo, я ответил товарищу GregZ'у, который предложил писать сфот, полезный секснародовцам, а такой за полчаса не напишешь!

(jalt @ 29.05.2006 - время: 23:54) JeyLo, я ответил товарищу GregZ'у, который предложил писать сфот, полезный секснародовцам, а такой за полчаса не напишешь!
Чем сложнее задание, тем дольше писать...

(GregZ @ 29.05.2006 - время: 21:28) (JeyLo @ 29.05.2006 - время: 21:16)А че там разбираться? Оценивать качество кода, да? Так и представляю: у участника номер один вот это вот отрывок на C++ лучше, чем вот у третьего на C#, а шестой на QBasic'е вообще сделал все конгениально! Программа или работает, или нет... Вот и весь подход. :)
Т.е. предлагаете посылать на конкурс исполняемые модули? А если я пишу под Maс OS?
Исполняемые модули? Вы шутите!!! Я чужие исполняемые модули не запускаю! Там могут быть вирусы.

(JeyLo @ 30.05.2006 - время: 00:35)Имхо конкурс на программирование должен быть как быстрые шахматы. Задание - ответ в течении десяти/тридцати минут (чур сигнатуры не подделывать! :)). А то если тут на сутки задание давать, то победит самый общительный.
Ну и как общительность поможет решить, скажем, такую задачку:

"Разработать алгоритм удаления узла АВЛ-дерева с восстановлением балансировки. Реализовать данный алгоритм в составе быблиотеки работы с АВЛ-деревьями."

А тут работы не на сутки, а гораздо больше. Пока найдешь литературу по этим АВЛ-деревьям. Пока вникнешь в тонкости восстановления их балансировки ... Ну и прграммная реализация не сказал бы что очень простая ...

За 10-30 минут многие и войти сюда не успеют, чтобы задание прочесть.
Напротив, задания должны быть такие, чтобы на их решение требовалось длительное время - от нескольких дней до месяца. А за 10 минут можно только программку типа "Hello, world!" написать ...

GrAnd, и сколько участников у нас наберется? Два? Три? Ты думаещь, тут все суперпрограммеры собрались? Нам нужен НАРОДНЫЙ конкурс, в котором смог бы участвовать любой, кто более-менее на среднем уровне может что-то писать.

(jalt @ 29.05.2006 - время: 21:57) Ладно, прекратили треп! Получаем задание, технические условия и пишем хоть в двоичном коде, на досмотр предоставляем exe-шник (или скрипт Linux), у кого Маки - в пролете. Exe-шник прогоняется через тесты, и в зависимости от того, сколько тестов он пройдет, начисляется определенное кол-во баллов. Так всех устраивает?
Бугаа я умер ... ты шутник???

Вот есть 10 НАРОДНЫХ программеров, пишущих на пасхале... и среди них 1 товарисч пишет на c++ - и кто думаешь победит? нифига не этот один - победит КОМПИЛЯТОР осей...

а теперь прикольнись... там ещё окажется товарищ на прологе пищущий? тогда отдохнуть все...


Зы ты суръезна никогда не видел конкурсов програмистов? как минимум исходник нужен для оценки алгоритма в написании...

Kosyak, если ты внибательно прочел весь топик, в самом начале я предлагал предоставлять на оценку именно исходники. На что JeyLo ответил: "А че там разбираться? Оценивать качество кода, да? Так и представляю: у участника номер один вот это вот отрывок на C++ лучше, чем вот у третьего на C#, а шестой на QBasic'е вообще сделал все конгениально! Программа или работает, или нет... Вот и весь подход. :)". Так что если честно, я уже не знаю, кого слушать. Давайте чтоли голосование открывать...

(jalt @ 30.05.2006 - время: 10:22) GrAnd, и сколько участников у нас наберется? Два? Три? Ты думаещь, тут все суперпрограммеры собрались? Нам нужен НАРОДНЫЙ конкурс, в котором смог бы участвовать любой, кто более-менее на среднем уровне может что-то писать.
Так это и есть самый что ни на есть средний уровень, даже ниже среднего. Посредственный, так сказать.
Я про алгоритмы обработки АВЛ-деревьев своим слушателям на курсах основ программирования читал, когда на этой ниве подвизался несколько лет назад.
Чтобы разобраться в этом много ума не надо. Было бы желание. Правда, алгоритм удаления узла, действительно непрост. Я его даже доказать не смог, хотя спинным мозгом чувствую, что он правилен.

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

(GrAnd @ 30.05.2006 - время: 08:49) "Разработать алгоритм удаления узла АВЛ-дерева с восстановлением балансировки. Реализовать данный алгоритм в составе быблиотеки работы с АВЛ-деревьями."
Классная задачка - просто испугало АВЛ ... 3 минуты поиска - понял ... можно в принципе и такой вопрос... только вот зачем библиотека? тут и с алгоритмом войны хватит - пока придумаешь как ...



jalt Тему я прочитал давно... я просто выражаю свои соображения по поводу

Блин, ну ладно, давайте остановимся и прикинем количество участников. Хоть человек 10 должно набраться, иначе смысла конкурса нет. Э-эй! Программеры! Желающие участвовать отписываемся сюда!

(Kosyak @ 30.05.2006 - время: 11:50) Классная задачка - просто испугало АВЛ ... 3 минуты поиска - понял ... можно в принципе и такой вопрос... только вот зачем библиотека? тут и с алгоритмом войны хватит - пока придумаешь как ...
Ну по сравнению с алгоритмом - библиотека просто детский лепет.
Зато уже сурьезный продукт.
Впрочем, повторяю, я и не предлагал на самом деле это на конкурс. Разве что-то подобное на второй-третий тур. Это я так поерничал.

(jalt @ 30.05.2006 - время: 12:08) Блин, ну ладно, давайте остановимся и прикинем количество участников. Хоть человек 10 должно набраться, иначе смысла конкурса нет. Э-эй! Программеры! Желающие участвовать отписываемся сюда!
А зачем отписываться? Заводи тему, бросай туда пару-тройку задачек разной сложности, определяй сроки (только не меньше 2-х/3-х суток) и порядок.
Будь проще и люди к тебе потянутся.
Это же пробный конкурс. Потом уже можно и более четкие правила определять. А пока нужно, "чтобы было".

2GrAnd: AVL деревья у нас лично (в Alma-Mater) входят в базисный курс за 3й семестер - что в них сложного?!!! Ну самые известные и самые древние и почти самые эффективные утавновешенные деревья...

То что вы просили я могу сноровить задать в качестве задачи на интервью и дать на это 20 минут. (Уважающий себе программер, по памяти должен успеть)

(tetro @ 30.05.2006 - время: 14:34) 2GrAnd: AVL деревья у нас лично (в Alma-Mater) входят в базисный курс за 3й семестер - что в них сложного?!!! Ну самые известные и самые древние и почти самые эффективные утавновешенные деревья...

То что вы просили я могу сноровить задать в качестве задачи на интервью и дать на это 20 минут. (Уважающий себе программер, по памяти должен успеть)
Хм ... Оказывается их даже где-то изучают :) ... Приятно услышать.

И пусть даже так.
В любом случае интересно посмотреть, насколько эффективна реализация алгоритма. Да и насколько сам алгоритм эффективен ...

Но 20 минут тут не катит. Удаление узла с восстановлением балансировки достаточно заморочный процесс.
Впрочем, если память хорошая, то может быть и получится ...

Только вот дело как раз не в том, чтобы что-то по памяти, а чтобы алгоритм разработать самому ...

Да к слову как в том анекдоте: АВЛ - это 2 мужика, а не 3 ... причем в 1962 когда они это написали они жили в СССР.

А что там сложного, если предположить что у нас нет совпадения ключей? Далее все из перво-принципов, то что по памяти, так это то что вращение осуществляем когда разница высот между правым и левом поддеревом 2.
АВЛ от простого дерева отличается тем что в нем хранится высота под-дерева.

Добавляем: бинарное дерево - как обычно добавлен лист. Далее "рекурсивно" (скорее в ковычках, чем без) у папы корректируем высоту и проверяем на уравновешенность:
если стало неуравновешенным, то вращаем в противоложную сторону: заменяем папу на след./пред. в поддереве узел, а папу всовываем туда с соотв. коррекцией... После вращения, высота в точке вращения осталась как прежде (до добавления), значит и выше ничего не надо менять.
Если высота изменилась (но здесь явно не было вращения), то корректим и его папу и продолжаем наверх.

Легко доказать, что к-во вращений максимум логарифмично, т.е. сложность О(log) как и для обычного дерева ...

(tetro @ 30.05.2006 - время: 16:39) Да к слову как в том анекдоте: АВЛ - это 2 мужика, а не 3 ... причем в 1962 когда они это написали они жили в СССР.

А что там сложного, если предположить что у нас нет совпадения ключей?
Ну да ... А Слава Капээсэс - это вообще не мужик :) ...

Ну то, что ты описал, это действительно не сложно, ибо описывает включение нового узла в АВЛ-дерево. А я писал, об удалении ... Ведь после удаления узла остаются 2 хвоста, которые надо куда-то прицепить. Да еще так, чтобы баланс не нарушился.

Но мы что-то отвлеклись ...
Когда конкурсные задания-то будут?

1) АВЛ - это фамилии 2х человек АВ (что-то типа Адисон-Вейский) и Л (Ландес) - я таки читал их оригинальную статью за 1962 год - они первыми подняли вопрос о сбалансированых деревьях.
2) Удаление, есть замена вершины - в данном случае практически листом (он не может быть выше 2го этажа) - для удобства и определенности мы берем его с более высокой стороны, т.е. в точке удаления нет нарушения критерия... А далее от него (где был вышедший на замену) наверх идем и вращаем, если надо (от папы вышедшего на замену) максимум на 1цу до его нового места...

(tetro @ 31.05.2006 - время: 15:20) 1) АВЛ - это фамилии 2х человек АВ (что-то типа Адисон-Вейский) и Л (Ландес) - я таки читал их оригинальную статью за 1962 год - они первыми подняли вопрос о сбалансированых деревьях.
Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организации информации. :)

Други мои! Ну так что с конкурсом? Участники наберутся? А то пока я смотрю, собралось вас трое продвинутых, и тишина!