| QUOTE (jalt @ 29.05.2006 - время: 22:42) |
| Гы... а они еще не готовы! Кстати, ищутся соавторы и тестеры! |
Я б в соавторы пошел, да только кто же меня возьмет, маньяка-извращенца :)
Зато есть предложение, подкупающее своей новизной. Предлагаю писать что-нибудь несложное, но полезное. Т.е. то, чем в дальшейшем возможно будут пользоваться Вы, я и остальной народ. Результат выставить на всеобщее обозрение, и победителя выбирать всеSEXнародным голосованием. Это будет честно.
Имхо, для начала нужно провести конкурс по регламенту олимпиад. А уж потом крупные полезные проекты представлять.
Это сообщение отредактировал jalt - 29-05-2006 - 23:16
| QUOTE (jalt @ 29.05.2006 - время: 23:08) |
| Ага. Только сначала придется устраивать конкурс на лучшее задание для конкурса, а потом уже конкурс по итогам того конкурса. Вот. Все меня поняли? :) Имхо, для начала нужно провести конкурс по регламенту олимпиад. А уж потом крупные полезные проекты представлять. |
Так уж и крупные? :)
Имхо конкурс на программирование должен быть как быстрые шахматы. Задание - ответ в течении десяти/тридцати минут (чур сигнатуры не подделывать! :)). А то если тут на сутки задание давать, то победит самый общительный.
| QUOTE (jalt @ 29.05.2006 - время: 23:54) |
| JeyLo, я ответил товарищу GregZ'у, который предложил писать сфот, полезный секснародовцам, а такой за полчаса не напишешь! |
Чем сложнее задание, тем дольше писать...
| QUOTE (GregZ @ 29.05.2006 - время: 21:28) | ||
Т.е. предлагаете посылать на конкурс исполняемые модули? А если я пишу под Maс OS? |
Исполняемые модули? Вы шутите!!! Я чужие исполняемые модули не запускаю! Там могут быть вирусы.
| QUOTE (JeyLo @ 30.05.2006 - время: 00:35) |
| Имхо конкурс на программирование должен быть как быстрые шахматы. Задание - ответ в течении десяти/тридцати минут (чур сигнатуры не подделывать! :)). А то если тут на сутки задание давать, то победит самый общительный. |
Ну и как общительность поможет решить, скажем, такую задачку:
"Разработать алгоритм удаления узла АВЛ-дерева с восстановлением балансировки. Реализовать данный алгоритм в составе быблиотеки работы с АВЛ-деревьями."
А тут работы не на сутки, а гораздо больше. Пока найдешь литературу по этим АВЛ-деревьям. Пока вникнешь в тонкости восстановления их балансировки ... Ну и прграммная реализация не сказал бы что очень простая ...
За 10-30 минут многие и войти сюда не успеют, чтобы задание прочесть.
Напротив, задания должны быть такие, чтобы на их решение требовалось длительное время - от нескольких дней до месяца. А за 10 минут можно только программку типа "Hello, world!" написать ...
Это сообщение отредактировал GrAnd - 30-05-2006 - 08:53
| QUOTE (jalt @ 29.05.2006 - время: 21:57) |
| Ладно, прекратили треп! Получаем задание, технические условия и пишем хоть в двоичном коде, на досмотр предоставляем exe-шник (или скрипт Linux), у кого Маки - в пролете. Exe-шник прогоняется через тесты, и в зависимости от того, сколько тестов он пройдет, начисляется определенное кол-во баллов. Так всех устраивает? |
Бугаа
я умер ... ты шутник???Вот есть 10 НАРОДНЫХ программеров, пишущих на пасхале... и среди них 1 товарисч пишет на c++ - и кто думаешь победит? нифига не этот один - победит КОМПИЛЯТОР осей...
а теперь прикольнись... там ещё окажется товарищ на прологе пищущий? тогда отдохнуть все...
Зы ты суръезна никогда не видел конкурсов програмистов? как минимум исходник нужен для оценки алгоритма в написании...
| QUOTE (jalt @ 30.05.2006 - время: 10:22) |
| GrAnd, и сколько участников у нас наберется? Два? Три? Ты думаещь, тут все суперпрограммеры собрались? Нам нужен НАРОДНЫЙ конкурс, в котором смог бы участвовать любой, кто более-менее на среднем уровне может что-то писать. |
Так это и есть самый что ни на есть средний уровень, даже ниже среднего. Посредственный, так сказать.
Я про алгоритмы обработки АВЛ-деревьев своим слушателям на курсах основ программирования читал, когда на этой ниве подвизался несколько лет назад.
Чтобы разобраться в этом много ума не надо. Было бы желание. Правда, алгоритм удаления узла, действительно непрост. Я его даже доказать не смог, хотя спинным мозгом чувствую, что он правилен.
Впрочем, это я привел шутки ради. На самом деле, нужно что-нить действительно попроще. Но не примитивное, где вся заслуга программера будет заключаться в умении пользоваться визуальными компонентами.
| QUOTE (GrAnd @ 30.05.2006 - время: 08:49) |
| "Разработать алгоритм удаления узла АВЛ-дерева с восстановлением балансировки. Реализовать данный алгоритм в составе быблиотеки работы с АВЛ-деревьями." |
Классная задачка - просто испугало АВЛ ... 3 минуты поиска - понял ... можно в принципе и такой вопрос... только вот зачем библиотека?
тут и с алгоритмом войны хватит - пока придумаешь как ... jalt Тему я прочитал давно... я просто выражаю свои соображения по поводу
| QUOTE (Kosyak @ 30.05.2006 - время: 11:50) |
| Классная задачка - просто испугало АВЛ ... 3 минуты поиска - понял ... можно в принципе и такой вопрос... только вот зачем библиотека? тут и с алгоритмом войны хватит - пока придумаешь как ... |
Ну по сравнению с алгоритмом - библиотека просто детский лепет.
Зато уже сурьезный продукт.
Впрочем, повторяю, я и не предлагал на самом деле это на конкурс. Разве что-то подобное на второй-третий тур. Это я так поерничал.
| QUOTE (jalt @ 30.05.2006 - время: 12:08) |
| Блин, ну ладно, давайте остановимся и прикинем количество участников. Хоть человек 10 должно набраться, иначе смысла конкурса нет. Э-эй! Программеры! Желающие участвовать отписываемся сюда! |
А зачем отписываться? Заводи тему, бросай туда пару-тройку задачек разной сложности, определяй сроки (только не меньше 2-х/3-х суток) и порядок.
Будь проще и люди к тебе потянутся.
Это же пробный конкурс. Потом уже можно и более четкие правила определять. А пока нужно, "чтобы было".
То что вы просили я могу сноровить задать в качестве задачи на интервью и дать на это 20 минут. (Уважающий себе программер, по памяти должен успеть)
Это сообщение отредактировал tetro - 30-05-2006 - 13:37
| QUOTE (tetro @ 30.05.2006 - время: 14:34) |
| 2GrAnd: AVL деревья у нас лично (в Alma-Mater) входят в базисный курс за 3й семестер - что в них сложного?!!! Ну самые известные и самые древние и почти самые эффективные утавновешенные деревья... То что вы просили я могу сноровить задать в качестве задачи на интервью и дать на это 20 минут. (Уважающий себе программер, по памяти должен успеть) |
Хм ... Оказывается их даже где-то изучают :) ... Приятно услышать.
И пусть даже так.
В любом случае интересно посмотреть, насколько эффективна реализация алгоритма. Да и насколько сам алгоритм эффективен ...
Но 20 минут тут не катит. Удаление узла с восстановлением балансировки достаточно заморочный процесс.
Впрочем, если память хорошая, то может быть и получится ...
Только вот дело как раз не в том, чтобы что-то по памяти, а чтобы алгоритм разработать самому ...
А что там сложного, если предположить что у нас нет совпадения ключей? Далее все из перво-принципов, то что по памяти, так это то что вращение осуществляем когда разница высот между правым и левом поддеревом 2.
АВЛ от простого дерева отличается тем что в нем хранится высота под-дерева.
Добавляем: бинарное дерево - как обычно добавлен лист. Далее "рекурсивно" (скорее в ковычках, чем без) у папы корректируем высоту и проверяем на уравновешенность:
если стало неуравновешенным, то вращаем в противоложную сторону: заменяем папу на след./пред. в поддереве узел, а папу всовываем туда с соотв. коррекцией... После вращения, высота в точке вращения осталась как прежде (до добавления), значит и выше ничего не надо менять.
Если высота изменилась (но здесь явно не было вращения), то корректим и его папу и продолжаем наверх.
Легко доказать, что к-во вращений максимум логарифмично, т.е. сложность О(log) как и для обычного дерева ...
| QUOTE (tetro @ 30.05.2006 - время: 16:39) |
| Да к слову как в том анекдоте: АВЛ - это 2 мужика, а не 3 ... причем в 1962 когда они это написали они жили в СССР. А что там сложного, если предположить что у нас нет совпадения ключей? |
Ну да ... А Слава Капээсэс - это вообще не мужик :) ...
Ну то, что ты описал, это действительно не сложно, ибо описывает включение нового узла в АВЛ-дерево. А я писал, об удалении ... Ведь после удаления узла остаются 2 хвоста, которые надо куда-то прицепить. Да еще так, чтобы баланс не нарушился.
Но мы что-то отвлеклись ...
Когда конкурсные задания-то будут?
2) Удаление, есть замена вершины - в данном случае практически листом (он не может быть выше 2го этажа) - для удобства и определенности мы берем его с более высокой стороны, т.е. в точке удаления нет нарушения критерия... А далее от него (где был вышедший на замену) наверх идем и вращаем, если надо (от папы вышедшего на замену) максимум на 1цу до его нового места...
Это сообщение отредактировал tetro - 31-05-2006 - 14:29
| QUOTE (tetro @ 31.05.2006 - время: 15:20) |
| 1) АВЛ - это фамилии 2х человек АВ (что-то типа Адисон-Вейский) и Л (Ландес) - я таки читал их оригинальную статью за 1962 год - они первыми подняли вопрос о сбалансированых деревьях. |
Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организации информации. :)
| QUOTE (jalt @ 31.05.2006 - время: 18:50) |
| Други мои! Ну так что с конкурсом? Участники наберутся? А то пока я смотрю, собралось вас трое продвинутых, и тишина! |
Боюсь, что об этом никто не знает, надо дать объявление.
И чтобы тему не засоряли сообщениями типа "Я поучаствую!" предлагаю заявки на участие на почту сбрасывать, я так один раз делал, в TheBat фильтр поставил и он все письма отсортировал в отдельную папку.
Всем кто видел и не видел конкурсы программистов, предлагаю для начала всего 2 тривиальнейшие задачи:
1. Составить алгоритм рисования n-конечной звезды, с учётом что перо не отрывается от бумаги.
Для тех, кому формулировка показалась расплывчатой - это значит что каждый следующий пиксель рисуется рядом с предыдущим, а n-конечная, значит что количество лучей неизвестно, то есть вводится пользователем. Глубина луча зависит от фантазии программиста, но это должна быть звезда, а не выпуклый многоугольник.
2. Есть стол неизвестной длины и ширины, есть неизвестное количество листов бумаги неизвестной ширины и высоты, которые хаотично разбросаны по столу, но однозначно вертикальной (горизонтальной) ориентации. Требуется составить алгоритм, который бы рассчитывал каким образом можно прибить гвоздями эти листки к столу таким образом, чтобы каждый лист был прибит не более чем одним гвоздём.
Для тех, кому формулировка показалась расплывчатой - это значит что на экране нужно случайно или посредством ввода пользователя разместить энное (неизвестное, то бишь вводимое пользователем) количество прямоугольников, которые ориентированы вертикально (горизонтально) и придумать как найти систему точек экрана, входящих в состав этих прямоугольников, но в каждый из них не более чем 1 раз.
Доп пункт для 2-й задачи - добавить в алгоритм анализ ситуаций что если два и более листов можно прибить одним гвоздём, то они обязательно должны быть прибиты одним гвоздём.
Платформа - неважно, при схожих вариантах решений претендентов, победителем считается тот, у кого минимальное количество полезных строчек кода. Полезной строчкой кода считается реализация оператора вне зависимости от его сложности или вызов функции или процедуры, входящих в состав стандартной поставки языка реализации.
А то, ребята, на тему жалко смотреть - громкое начало и ни одного дельного предложения.
Если что - участвовал в придумывании подобного рода задач, завсегда подкину пару-тройку интересностей.
| QUOTE (jalt @ 31.05.2006 - время: 19:50) |
| Други мои! Ну так что с конкурсом? Участники наберутся? А то пока я смотрю, собралось вас трое продвинутых, и тишина! |
Причем, один из них (т.е. я) в конкурсе участвовать не будет по причине нехватки времени. Работа, дом, дети, панимаш ....
| QUOTE (GrAnd @ 01.06.2006 - время: 07:50) | ||
Причем, один из них (т.е. я) в конкурсе участвовать не будет по причине нехватки времени. Работа, дом, дети, панимаш .... |
В соавторах\проверяющих будешь?
| QUOTE (Lem0nti @ 31.05.2006 - время: 22:17) |
| Всем кто видел и не видел конкурсы программистов, предлагаю для начала всего 2 тривиальнейшие задачи: |
Отставить палево... (с) :)
Думается мне участвовать в конкурсе будешь ты один. Конкурс должен быть в первую очередь народным.
К примеру у меня просто не будет времени для решения столь "тривиальных", как ты считаешь, задач.
Это сообщение отредактировал GregZ - 01-06-2006 - 12:47
| QUOTE (GregZ @ 01.06.2006 - время: 12:44) |
| К примеру у меня просто не будет времени для решения столь "тривиальных", как ты считаешь, задач. |
Тогда ты не народный программист! Это же тривиально! Буквально каких-то пару дней.. Отпросись у начальства. Как маленький, ей богу!
2) Есть 2/3 пути построить такой конкурс:
- что-то вкусное из темы красивой имплементации (скорее прогаммные трюки чем математика), тут я не слишком силен в задачах но, например,
Написать класс имплементирующий матрицы с операторами над ними, позволяющий писать марричные выражения в классической форме с минимальным overhead копирования при вычислении...
Или какие нибудь гадости из Design Patterns...
AVL, skip-list и пр, стуктуры данных были бы ничего если бы были гарантированно вне программы...
Здесь бонус скорее на стороне опыта...
- Какие-нибудь каки из Вычислительной геометрии или что-нибудь типа предложенного, т.е. олимпиада для студентов и школьников в ее лучшем смысле ... т.е. гибкость мозгов намного важнее опыта...