Задачи по программированию
Я решил запостить свой дебютный пост о той части свой жизни которой я увлекся года 3-4 назад. А именно об соревновательном программировании.
Существуют несколько сайтов содержащих 1000+ задач на различные темы программирования, попадаются очень экзотичные проблеммы, которые способны решить только десятки человек.
Вот самые популярные ссылки в данной теме:
http://uva.onlinejudge.org/index.php
http://www.topcoder.com/
http://acm.timus.ru/
Создание подобного ресурса тоже не менее интересная задача.
На данный момент я решил более 500 задач, различной сложности. Сейчас попробуем разобраться, что это мне дало.
Но для начала немного статистики:
Горизонтальные линии показывают, что у меня есть жена и ребенок и другие интерессы.
Резкий подъем активности после 2010 не говорит, что я вдруг познал дзен в программировании. Просто я нашел очень полезный сайт, где задачи отсортированны по сложности. (Кому интересно вот он). Но все таки прогресс есть.
Любого кто захочет начать занятся соревновательным программированием подстерегают демоны.
Первый из них это глупые ошибки, которых можно было бы избежать. Мой опыт подсказывает, что это самое большая трата времени. Причин их возникновения очень много.
Самые больные темы:
1. Индексы массивов
Часто приходится делать магию с индексами. Самы простые примеры это ходы шахматных фигур.
Возьмем самый простой пример ладью, необходимо перебрать все позиции в кот. она может находится.
Эволюция началась с самого просто:
Ладья ходит в 4 стороны, значит это 4 цикла. т.е. так:
for(int k=1; ; k++)
{
newx = x + k
.. если вышли за предели останавливаемся
}
for(int k=1; ; k++)
{
newx = x - k
.. если вышли за предели останавливаемся
}
// тоже самое для y
У меня процесс эволюции закончился след.
const int DIR_COUNT = 4;
int Dirs[DIR_COUNT][2] =
{
{1,0},
{-1,0},
{0, 1},
{0, -1},
}
for(int k=0; k < DIR_COUNT; k++)
{
for(int t=1; ; t++)
{
newX = x + t*Dirs[k][0];
newY = y + t*Dirs[k][1];
// делаем необходимое
}
}
Такой подход легко запомнить и эффективно использовать под любые виды фигур. Вот из последних задач (игра камень-ножницы-бумага, 0й индекс кол-во побед, 1й поражений)
int Relations [3][3][2] =
{
//rock paper scissor
{{0,0}, {0,1}, {1,0}}, // rock
{{1,0}, {0,0}, {0,1}}, // paper
{{0,1}, {1,0}, {0,0}}, // scissor
};
2.Считывание данных
Тут мое самое большое откровение это избегать ручного разбора строк. scanf ( мне именно его легче использовать в данном случае) позволяет решать многие задачи на лету. MSDN
Часто используемые конструкции это:
while( scanf("%d", &n) != EOF ) - для считывания до конца файла.
scanf("%1s", str); str[0] - Для считывания одно значещего символа
3.Мнимые NP задачи
Я всегда оцениваю вычислительную сложность задачи, перед тем как браться за программирование. Иногда O(2^N) может быть единственным способом, но тогда необходимо N <= 8. Если это не так, то скорее всего возможно отсекать бесперспективные ветки. Если N ~ 100, то о грубой силе не может быть речи. Если N ~ 100000, то и O(N^2) не сможет справится.
Я стараюсь доверять своей интуиции и подождать, может быть появится более хорошая мысль.
4.Много кода
Иногда я ловлю себя на мысли, что кода слишком много и наверное идея была не очень правильной. Тогда я останавлваюсь и начинаю искать другие решения. Только через некоторое время, когда нет других вариантов возвращаюсь к коду.
Ну и бонус, чего можно ожидать от такого увлечения:
1. Начинаешь меньше делать глупых ошибок ( иначе не выжить)
2. Мелкие задачи решаются быстрее.
3. Возможность реализовать классические алгоритмы, которые читал в книге, но не реализовывал
Чего не стоит ожидать:
1. Задачи укладываются в 1000 строк, по-этому это лишь косвенно помогает в больших проектах
2. Задачи в основном имеют теоретический интересс, на практике в 95% есть готовые решения.(контейнеры, графы и БД) Не стоит ждать, что придется эту задачу решать в комерческом продукте.
Ну и самый большой плюс -решать задачи доставляет удовольствие. Это скорее медитативный процесс. Каждый новый ACCEPTED радость. Каждый WRONG ANSWER, TIME LIMIT EXCEEDED - новое испытание!
Существуют несколько сайтов содержащих 1000+ задач на различные темы программирования, попадаются очень экзотичные проблеммы, которые способны решить только десятки человек.
Вот самые популярные ссылки в данной теме:
http://uva.onlinejudge.org/index.php
http://www.topcoder.com/
http://acm.timus.ru/
Создание подобного ресурса тоже не менее интересная задача.
На данный момент я решил более 500 задач, различной сложности. Сейчас попробуем разобраться, что это мне дало.
Но для начала немного статистики:
Горизонтальные линии показывают, что у меня есть жена и ребенок и другие интерессы.
Резкий подъем активности после 2010 не говорит, что я вдруг познал дзен в программировании. Просто я нашел очень полезный сайт, где задачи отсортированны по сложности. (Кому интересно вот он). Но все таки прогресс есть.
Любого кто захочет начать занятся соревновательным программированием подстерегают демоны.
Первый из них это глупые ошибки, которых можно было бы избежать. Мой опыт подсказывает, что это самое большая трата времени. Причин их возникновения очень много.
Самые больные темы:
1. Индексы массивов
Часто приходится делать магию с индексами. Самы простые примеры это ходы шахматных фигур.
Возьмем самый простой пример ладью, необходимо перебрать все позиции в кот. она может находится.
Эволюция началась с самого просто:
Ладья ходит в 4 стороны, значит это 4 цикла. т.е. так:
for(int k=1; ; k++)
{
newx = x + k
.. если вышли за предели останавливаемся
}
for(int k=1; ; k++)
{
newx = x - k
.. если вышли за предели останавливаемся
}
// тоже самое для y
У меня процесс эволюции закончился след.
const int DIR_COUNT = 4;
int Dirs[DIR_COUNT][2] =
{
{1,0},
{-1,0},
{0, 1},
{0, -1},
}
for(int k=0; k < DIR_COUNT; k++)
{
for(int t=1; ; t++)
{
newX = x + t*Dirs[k][0];
newY = y + t*Dirs[k][1];
// делаем необходимое
}
}
Такой подход легко запомнить и эффективно использовать под любые виды фигур. Вот из последних задач (игра камень-ножницы-бумага, 0й индекс кол-во побед, 1й поражений)
int Relations [3][3][2] =
{
//rock paper scissor
{{0,0}, {0,1}, {1,0}}, // rock
{{1,0}, {0,0}, {0,1}}, // paper
{{0,1}, {1,0}, {0,0}}, // scissor
};
2.Считывание данных
Тут мое самое большое откровение это избегать ручного разбора строк. scanf ( мне именно его легче использовать в данном случае) позволяет решать многие задачи на лету. MSDN
Часто используемые конструкции это:
while( scanf("%d", &n) != EOF ) - для считывания до конца файла.
scanf("%1s", str); str[0] - Для считывания одно значещего символа
3.Мнимые NP задачи
Я всегда оцениваю вычислительную сложность задачи, перед тем как браться за программирование. Иногда O(2^N) может быть единственным способом, но тогда необходимо N <= 8. Если это не так, то скорее всего возможно отсекать бесперспективные ветки. Если N ~ 100, то о грубой силе не может быть речи. Если N ~ 100000, то и O(N^2) не сможет справится.
Я стараюсь доверять своей интуиции и подождать, может быть появится более хорошая мысль.
4.Много кода
Иногда я ловлю себя на мысли, что кода слишком много и наверное идея была не очень правильной. Тогда я останавлваюсь и начинаю искать другие решения. Только через некоторое время, когда нет других вариантов возвращаюсь к коду.
Ну и бонус, чего можно ожидать от такого увлечения:
1. Начинаешь меньше делать глупых ошибок ( иначе не выжить)
2. Мелкие задачи решаются быстрее.
3. Возможность реализовать классические алгоритмы, которые читал в книге, но не реализовывал
Чего не стоит ожидать:
1. Задачи укладываются в 1000 строк, по-этому это лишь косвенно помогает в больших проектах
2. Задачи в основном имеют теоретический интересс, на практике в 95% есть готовые решения.(контейнеры, графы и БД) Не стоит ждать, что придется эту задачу решать в комерческом продукте.
Ну и самый большой плюс -решать задачи доставляет удовольствие. Это скорее медитативный процесс. Каждый новый ACCEPTED радость. Каждый WRONG ANSWER, TIME LIMIT EXCEEDED - новое испытание!