Медали для всех, даром, и пусть никто не уйдет обыгранным!

Добрый день, уважаемые друзья!

Глядя на нижеследующие ссылки (2011, 2012, 2013, 2014 — следует нажать ссылочку Standings), многие современники не спрашивают у меня, как прийти к подобным результатам. А зря.

К сожалению, сам по себе ритуал еженедельного посещения кружка умелых информационных ручек с опцией прорешивания особо приглянувшихся задач способен перевести Вас лет за 5 из состояния «сдаю на OCPC-18 три задачи» в состояние «сдаю на OCPC-23 семь задач». Цели и задачи факультатива не могут выходить за пределы предоставления Вам базовых олимпиадных знаний и навыков, а также развития способности самостоятельно ориентироваться в джунглях алгоритмов и языков программирования. Поэтому, воспользовавшись лицензией GNU (то есть, бесплатно), хочу распространить методику превращения обычной команды в призера полуфинала чемпионата Мира.

Данный подход зиждится на трех китах и одной черепахе:
1) Практика
2) Дорешивание
3) Теория
4) Собственно, черепаха

1) Практика. Состоит из личной и командной подготовки.
а) Личная тренировка заключается в ежедневном прорешивании по 1-5 задач в течение нескольких лет. Для этого на начальном этапе неплохо подойдет сайт acm.timus.ru, поскольку там, в отличие от е-олимпа, нет тысяч задач уровня а+б и задач с битыми тестами и поломанными чекерами. Через какое-то время после начала Ваших тренировок на тимусе Вы неизбежно столкнетесь с необходимостью овладения новыми алгоритмами, что и требуется. Также крайне рекомендуется решать личные контесты на codeforces.com и topcoder.com каждый раз, когда они начинаются не в 4 утра.
б) Командная тренировка заключается в еженедельном совместном с командой решении 5-часового контеста, соответствующего Вашему текущему уровню. Для этого отлично подойдет субботний кружок. Здесь Вы отрабатываете командную тактику, опыт взаимодействия, одновременное придумывание одной задачи, написание второй и дебага третьей за одним и тем же компьютером. Для этой цели может подойти, например, codeforces.com — там много соревнований самого разного уровня с очень хорошими тестами и возможностью соревноваться с другими участниками этого контеста.
Если закончился контест, а у Вас еще 2 недодебаженные задачи и 3 — с придуманными решениями, но Вы не успеваете их сдать, это верный признак того, что нужно поднажать на личные тренировки с целью довести до блеска известные Вам методы решения.

2) Дорешивание. Задачи, не решенные во время личной или командной тренировки, необходимо дорешать после разбора. На контесте Вы учитесь сдавать задачи, которые Вы умеете решать. На дорешивании — учитесь сдавать задачи, которые решать до сих пор не умели. Это основа любого роста, который состоит из двух частей — вширь и вглубь. Недорешенная задача может преследовать Вас годами из Полуфинала в Полуфинал, пока Вы не избавитесь от нее, как нерешенной, либо она — от Вас, как участника. Второе наступает всегда в силу возрастных ограничений для ACM ICPC.

3) Теория. Однажды наступает такой момент, когда прошла половина контеста, у Вас 5 задач, сданных с плюса, и еще 5, с которыми Вы понятия не имеете, что делать. Скорее всего, это означает, что настало время изучать новые алгоритмы. Для этих целей служит книга Кормена и др. «Алгоритмы. Построение и анализ», а также сайт e-maxx.ru/algo. В первую очередь стоит изучать те алгоритмы, которые чаще других упоминаются на разборе нерешенных Вами задач.

В команде для каждого «разлоченного» алгоритма должен быть один человек, который пишет его за известное время и со строго ограниченным сверху количеством ошибок и еще 2 человека должны иметь представление, что этот алгоритм делает, чтобы узнавать на него задачи. Для более простых/распространенных алгоритмов важно, чтобы их хорошо писали все трое. Чтобы изучить новый алгоритм, нужно прочитать и понять соответствующую статью, написать соответствующий рабочий код, а затем прорешать все доступные по теме задачи (их можно найти на тимусе и кодфорсе). Очень важно не заниматься копипастом, а писать решение каждый раз заново. Более того, желательно одну и ту же задачу сдавать по несколько раз, засекая время. В идеале, Вы должны тратить на реализацию от 5 до 15 минут (и знать заранее, сколько именно).
Где-то раз в пару месяцев нужно делать пересдачу хотя бы одной задачи по каждому изученному алгоритму, дабы навыки находились в тонусе. В целом, это касается более редких алгоритмов, поскольку часто встречающиеся и так будут попадаться Вам каждую неделю.
Кстати, важная составляющая теории — знание того языка программирования, на котором Вы пишете. Для C++ могу порекомендовать книгу Аммерааля по STL — в ней довольно неплохо описаны структуры данных и алгоритмы, реализованные в стандартной библиотеке.

4) Черепаха, на которой все и стоит, — осознание того, что никто не научит Вас решать задачи. Ни ув. преподаватели ОНУ, ни я, ни ув. Андрей Лопатин с ув. Андреем Станкевичем не проделают за Вас когнитивную работу по утрамбовыванию алгоритмов и методов решения задач в Ваш персональный мозг. Только Ваши усилия и Ваша инициатива способны перевести Вашу команду из аутсайдеров в лидеры. И всякое творчество приветствуется: читайте участникам кружка лекции по изученным Вами алгоритмам, придумывайте свои задачи и проводите по ним контесты (благо, сервер у нас есть), ездите на школы и сборы, общайтесь с единомышленниками. Искренняя заинтересованность и упорный труд свернут горы!

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

Завершить хочу мотивирующей ссылкой (ищем слово Odessa). С целью не повторения, но преодоления, разумеется.

FAQ или диалоги с умным человеком.

  1. Q: Ну выиграю я этот ваш Финал и что дальше?
    A: Ничего особенного.

  2. Q: Ваша команда возникла не на пустом месте. В ней было два призера школьных Всеукров по математике, не считая вашего основного кодера, который может работать по 16 часов в сутки. Мы не такие талантливые/трудоспособные.
    A: В команде ONU_Antananarivu не было ни одного призера Всеукра, однако до 2013 года они тренировались где-то на 70-80% мощности от ONU 1 2/3 и смогли решить достаточное для выхода в Финал количество задач. Их остановило только правило «один ВУЗ — одна команда». В то же время, к 2015-му году они почти перестали тренироваться, а победителем стала команда, занявшая 13-е место двумя годами ранее, а в 2012-м вообще не вышедшая в Полуфинал. Тем не менее, все участницы означенной команды сегодня работают в Корпорации Добра.

Олег Петров

Software Engineer at Snap Inc.
Los Angeles, California

Задачи Областной школьной олимпиады 2018

На Одесской областной олимпиаде школьников 2018 года мы предложили 12 задач различной степени сложности. Результаты можно найти здесь.
Условия задач, их короткий разбор мы попытались сделать на этой странице.
Решать задачи можно на сайте acm.pp.ua после простой регистрации. Соревнование №12.


Первые три задачи получились разбиением одной задачи, на три этапа для последовательного решения.

Задача A. Секунды

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

На часах сейчас $s$ секунд. Сколько секунд они будут показывать через $t$ секунд?

Входные данные: Два целых числа через пробел – $s \left(0 \le s \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$

Выходные данные: Одно целое число – новые показания секунд на часах.

Вход Выход
2 3 4
25 50 15

На что обратить внимание

  • Значения параметра t выходит за пределы знакового 32-битного числа $\left[-2^{31};2^{31}-1\right]$
  • . Необходимо знать как кодируются целые числа и выбрать такой тип, чтобы данные и результаты вычислений не выходили за его пределы.

  • Нужно заметить, что каждые $60$ секунд показания возвращаются к исходному значению. Значит для решения следует использовать операцию остатка от деления на $60.$
A. Решение на С++
A. Решение на Java
A. Решение на C#

Задача B. Минуты и секунды

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Часы сейчас показывают $s$ секунд и $m$ минут. Сколько они будут показывать через $t$ секунд?

Входные данные: Три целых числа через пробел – $s, m \left(0 \le s, m \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$

Выходные данные: Два целых числа через пробел – новые показания минут и секунд.

Вход Выход
44 25 22 26 6
59 58 121 1 0

На что обратить внимание

  • Если предыдущая задача решена, то следует разобраться только с минутами. Нужно разобраться сколько пройдёт минут, если было $s$ секунд и прошло ещё $t$. Для этого придётся суммарное количество секунд разделить на $60$ — число секунд в минуте.
  • Поскольку минутная стрелка через $60$ минут вернётся к тем же показаниям, нужно снова взять остаток от деления на $60.$
  • Хотя условие задачи укладывается всего в пару строк, читать его нужно внимательно. Небольшое упражнение на внимательность состоит в том, что минуты и секунды на входе и выходе должны следовать в различном порядке.
B. Решение на C++

Задача C. Часы, минуты, секунды

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

На часах сейчас $h$ часов, $m$ минут и $s$ секунд. Сколько они будут показывать через $t$ секунд?

Входные данные: Четыре целых числа через пробел – $h \left(0 \le h \le 23\right), m, s \left(0 \le s, m \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$

Выходные данные: Три целых числа через пробел – новые показания часов, минут и секунд.

Вход Выход
23 59 59 66 0 1 5

На что обратить внимание

  • Кроме того, что период повторения часов составляет $24 \times 60 \times 60$ секунд особенно добавлять здесь нечего.
C. Решение на C++
В решении предлагается другой подход решения задачи. Предлагается перевести текущие показания часов в секунды. После этого увеличим текущее время на требуемое число секунд. Полученный результат можно будет снова перевести в часы, минуты и секунды. такой подход работает для самых разных задач в которых данные задаются в сложной системе единиц. Например, фунт стерлингов, шиллинг, пенс, фартинг, гинея, крона. Достаточно перевести все в наименьшие единицы, если все остальные соответствуют их целому числу. В общем случае, такой универсальной единицей может стать наибольший общий делитель всех используемых единиц.

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

Задача D. Вырезаем прямоугольник в клеточку

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется лист из тетради в клеточку размером $H \times W$ клеток. Определите, можно ли из него вырезать прямоугольник размером $h \times w$. Резать можно только по линиям.

Входные данные: Четыре целых числа через пробел – $H, W, h, w$. Все числа положительные и меньше $2^{31}.$

Выходные данные: Выведите $1$ если требуемый прямоугольник вырезать можно или $0$ если нельзя.

Вход Выход
5 8 10 1 0
5 8 6 4 1

На что обратить внимание

  • Вырезать можно двумя способами — вдоль листа или поперек. Нужно убедиться, что в каком-то из этих положений все поместится.
D. Решение на C++

Задача E. Вырезаем прямоугольник снова

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется лист бумаги размером $H \times W$ миллиметров. Определите, можно ли из него вырезать прямоугольник размером $h \times w$ миллиметров.

Входные данные: Четыре целых числа через пробел – $H, W, h, w.$ Все числа не превышают $500$.

Выходные данные: Выведите $1$ если требуемый прямоугольник вырезать можно или $0$ если нельзя.

Вход Выход
5 8 7 7 0
8 8 10 1 1

На что обратить внимание

  • Конечно главное отличие задачи от предыдущей совсем не в том, что клеточки заменили на миллиметры.
  • В этой задаче вырезать можно не только вдоль сторон листа, но и под любым углом к ним.
  • Если Вы уже знаете тригонометрию, то вам достаточно разместить прямоугольник под некоторым углом $\alpha$ и просчитать ширину и высоту охватывающего его листа. Останется только подобрать правильный угол. Недостаток этого способа состоит в том, что необходимо уметь пользоваться тригонометрическими функциями и обратными к ним.
  • Школьники в 8-м классе ещё не знают тригонометрических функций. Но есть возможность получить более изящное решение, без их использования. Это решение приводится под спойлером, но лучше попытайтесь найти его самостоятельно.
E. Решение на C++

И снова две задачи, вторая из которых лишена одного из ограничений. И снова, снятие ограничения делает вторую задачу более сложной. Точнее менее очевидной.

Задача F. Режем масло

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется прямоугольный брусок масла размером $X \times Y \times Z.$ Плоскими разрезами его нужно разделить на кубики со стороной $1.$
Какое минимальное число разрезов нужно будет сделать если каждый из полученных при разрезании кусочков нужно резать отдельно от остальных?

Входные данные: Три целых положительных числа через пробел – $X, Y$ и $Z$ каждое из которых не превышает $2^{21}.$

Выходные данные: Одно целое число — минимальное количество разрезов.

Вход Выход
1 1 2 1
3 2 5 29

На что обратить внимание

  • Я сторонник аналитического подхода к этой задаче. Рассуждаем так. У нас один кусочек. Каждый разрез добавляет ещё один кусочек. Т.е. кусочков получается на $1$ больше, чем разрезов. Но мы легко можем вычислить сколько должно получиться кусочков — мы ведь знаем размеры.
F. Решение на C++

Задача G. Режем масло снова

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется прямоугольный брусок масла размером $X \times Y \times Z.$ Плоскими разрезами его нужно разделить на кубики со стороной 1.
Какое минимальное число разрезов нужно будет сделать если разрезать можно сразу стопку из любого количества кусочков?

Входные данные: Три целых положительных числа через пробел – $X, Y$ и $Z$ каждое из которых не превышает $2^{21}.$

Выходные данные: Одно целое число — минимальное количество разрезов.

Вход Выход
1 1 2 1
3 2 5 6

На что обратить внимание

  • Теперь можно резать по несколько кусков сразу. Если не знаете как это, понаблюдайте как мама нарезает картошку маленькими кубиками. Она ведь режет сразу несколько пластинок, а не по одной?
  • Представьте, что у на некоторой стадии у Вас получилось два кусочка и один из них больше другого по всем размерам. Если Вы будете резать больший из них, то при этом заодно разрежется и второй.
    Это справедливо для любого числа кусков. Значит стоит рассматривать только самый большой кусок.
  • Стоит резать так, чтобы больший из кусков был поменьше. Т.е. примерно пополам (с округлением вверх).
  • Делим на два каждую из сторон до тех пор пока не получим единицу. Количество делений и есть ответ.
G. Решение на C++
Я привожу решение, которое использует логарифм по основанию два. Логарифмы изучаются только в конце выпускного класса. Если вы еще не добрались до логарифмов в школе, не беда. Просто напишите функцию f() при помощи цикла деления пополам с округлением в большую сторону и сосчитайте сколько раз придется делить. Код от этого не станет намного длиннее и работать будет также с близкой скоростью.

Задача H. Ибн аль-Хайсам задумался!

Лимит времени: 0.5 сек
Лимит памяти: 128MiB

Дано целое число $n$. Вычислите остаток от деления на $n$ произведение всех чисел от $1$ до $n-1.$

Входные данные: Целое число $n \left( 1 \lt n \lt 2^{31}\right).$

Выходные данные: Выведите значение выражения, требуемое в условии.

Вход Выход
7 6
10 0

На что обратить внимание

  • Если $n$ не является простым, то все его делители обязательно встретятся в качестве сомножителей при вычислении этого длинного произведения. Значит остаток будет равен нулю.
  • Ой! Число $4$ явно исключение из этого правила. Добавим для него условный оператор.
  • Остались простые числа. Понаблюдаем за ними написав цикл вычисления требуемого значения.
    Везде получается $n-1$? Попробуем отправить решение.
  • Если Вас заинтересовал последний факт и Вы хотите доказать его (хотя на соревновании достаточно простого удачного наблюдения), то Вы повторяете путь, который проделал в своё время Ибн аль-Хайсам. Сейчас этот результат принято называть теоремой Вильсона. Для неё напридумывали много простых и изящных доказательств. Даже геометрических. Но гораздо интереснее попытаться доказать ее самому. Там совсем не сложно догадаться.
H. Решение на C++
Функция prime() осуществляет прямую проверку числа на простоту. Т.е. просто перебираются все возможные нетривиальные делители. В приведенной ниже реализации сделаны некоторые весьма наивные попытки ускорить работу. Например, сразу исключены числа десятичная запись которых заканчивается на 0, 2, 4, 5, 6 или 8. Конечно, кроме самих чисел 2 и 5, которые являются простыми. Далее в цикле проверяются все возможные нечетные делители, т.к. чётные уже исключены. Перебор ведётся до $\sqrt{n}$. Из-за погрешности вычислений может быть пропущен делитель в точности равный $\sqrt{n}$. Чтобы избежать этой ситуации проверка ведется до $\sqrt{n+1}$. Задание единицы в виде 1.L приводит к тому, что вычисления выполняются с повышенной точностью ( long double). В данном случае эта перестраховка используется только как повод упомянуть этот полезный иногда тип данных.

Задача I. Настолько ли просты эти числа?

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Число называется простым если оно делится только на 1 и на само себя. Найдите наибольший общий делитель всех введенных простых чисел.

Входные данные: В первой строке указывается количество простых чисел 1 < n < 10000. Во второй строке через пробел следуют n простых чисел меньших 231.

Выходные данные: Одно целое число — наибольший общий делитель всех введенных простых чисел.

Вход Выход
4
2 3 5 7
1

На что обратить внимание

  • В предыдущей задаче пришлось поработать с простыми числами. В этой почти тривиальной задаче мы закрепляем понимание их определения. Те участники, которые не смогли справится с предыдущей задачей получают эту в качестве некоторого утешительного приза.
  • Простые числа делятся только на 1 и на само себя. Значит наибольшим общим делителем может быть только один из этих двух вариантов.
  • Типичная ошибка — всегда выводить 1. Правильно было бы заметить, что если все числа одинаковы, то НОД всё же не 1, а само число.
I. Решение на C++

Задача J. Деньги

Лимит времени: 0.4 сек
Лимит памяти: 128MiB

В стране выпущены банкноты номиналом 500, 200, 100, 50, 20, 10, 5 и 1 гривну. А также монеты достоинством 0.5, 0.25, 0.1, 0.05, 0.02 и 0.01 гривны. Требуется найти способ выдать сумму в n гривен, используя наименьшее количество банкнот и монет.

Входные данные: Одно положительное действительное число n, не превышающее 1010, которое задаёт сумму с точностью до копеек.

Выходные данные: В одной строке следует вывести пары чисел через пробел — номинал банкноты (или монеты) и количество банкнот (или монет) этого номинала к выдаче. Значения следует перечислять в порядке увеличения номиналов денежных знаков.

Вход Выход
436.24 0.02 2 0.1 2 1 1 5 1 10 1 20 1 200 2

На что обратить внимание

  • Задача и простая и глубокая одновременно. Простая, поскольку решается интуитивно понятным жадным методом. Глубокая, поскольку может (и должна!) навести на мысли о поисках условия при которых этот жадный метод действительно даёт решение задачи. Т.е. каким условиям должны удовлетворять номиналы монет, чтобы жадный выбор давал оптимальное решение? Речь идёт о так называемых канонических монетных системах.
  • Жадный принцип требует начинать выдавать сумму с самых крупных купюр. Условие требует печатать ответ с самых мелких монет. Автор вредничает. Что делать? Конечно можно записать все количества в массив и напечатать его с конца. В приведенном ниже авторском решение используется другой подход — формируется строка ответа в которой новые данные вставляются в начало. Т.е. для формирования ответа можно использовать массивы или строки.
J. Решение на C++

Задача K. Одни плюсы

Лимит времени: 2 сек
Лимит памяти: 128MiB

Для заданного целого положительного числа n составьте равное ему арифметическое выражение, используя только операции сложения, умножения, скобки и число 1, содержащее минимально возможное число единиц.
Например, 7 = (1 + 1 + 1) * (1 + 1) + 1.

Входные данные: Одно целое положительное число n ≤ 104.

Выходные данные: Минимально возможное количество единиц.

Вход Выход
7 6

На что обратить внимание

  • Планировалась как самая сложная задача соревнования. Решение занимает целых 18 строк.
  • Задача относится к одному из самых красивых и популярных направлений в олимпиадном программировании. Имеется в виду так называемая «динамика» — динамическое программирование. Конечно, для решения задачи совсем не обязательно об этом знать, можно и так догадаться. Но знания и тренировка лучший помощник природной смекалке и сообразительности.
  • Для каждого числа есть возможность либо представить его в виде суммы единицы и числа на единицу меньшего, либо в виде произведения двух других чисел. Из этих двух вариантов выбираем тот в котором меньше единиц. А как узнать количество единиц в этих новых числах? Рекурсивным применением этого подхода. Рано или поздно мы получим просто 1 и процесс завершится.
  • Меморизация! Т.е. запоминание полученных результатов. Если мы уже вычислили кратчайшее представление некоторого числа (например, 2=1+1 или 5=(1+1)(1+1)+1), то это нужно запомнить и когда это число встретится в вычислениях снова, без повторных вычислений сразу использовать ранее полученный результат.
K. Решение на C++

Задача L. Комплексный обед

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

В меню столовой имеется n блюд. Стоимость каждого блюда известна. Комплексный обед с точки зрения администрации должен состоять из двух блюд, имеющих общую стоимость не более k. Какое максимальное количество вариантов комплексных обедов можно составить если каждое блюдо может входить только в один комплексный обед.

Входные данные: В первой строке заданы два целых положительных числа n ≤ 105 и k ≤ 109. Во второй строке следуют через пробел целые положительные числа задающие стоимости каждого из этих n блюд.

Выходные данные: Максимально возможное количество вариантов комплексных обедов.

Вход Выход
5 8
1 9 7 2 4
2

На что обратить внимание

  • Задача «на сортировку» или «на жадные алгоритмы».
  • Если расположить все блюда по возрастанию (или убыванию) цены, то нам останется найти для каждого блюда из числа более дорогих парное из числа более дешевых.
  • Логика решения такова. Каждое блюдо из числа более дешевых (в порядке увеличения цены) должно найти себе пару из числа более дорогих. Если какое-то не нашло, то дальше нечего и пытаться — будет только дороже. Дорогие блюда просматриваем в порядке уменьшения цены. Если не подошло для данного блюда, то и для более дорогого тоже не подойдёт.
  • Никакого перебора не понадобится. Просто движемся по отсортированному массиву с двух сторон на встречу друг другу. Если текущее дорого блюдо образует с текущим дешевым пару, то увеличиваем счётчик комплексных обедов и переходим к следующему дорогому и следующему дешевому. Если цена этой пары блюд слишком велика, переходим к следующему блюду из числа дорогих.
L. Решение на C++

В завершение вставим таблицу результатов соревнования:

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах

С чего начать?

Будем предполагать, что Ваша цель не просто изучить программирование, но и научиться решать задачи. Это означает, что Вы вероятно хотите получить в дальнейшем какую-то пользу от своих новых знаний и навыков, а не просто убиваете время. Сразу должен предупредить, что это потребует во много раз больше усилий, чем простое изучение синтаксиса и лексики С++, урду или клингонского языка.

Нам понадобится не только хороший учебник, но и хороший задачник с системой автоматической проверки. Ещё для занятия потребуют довольно много времени. А значит иногда придется работать не за привычным компьютером с установленной средой разработки, а с планшета или телефона. Предлагаю воспользоваться таким комплектом:

  • В качестве учебника возьмём книгу Липмана или Прата. — СКАЧИВАЕМ
  • В качестве задачника и тестирующей системы используем сайт e-olymp.com. — РЕГИСТРИРУЕМСЯ
  • Вместо установки на компьютер компилятора и среды разработки воспользуемся облачными технологиями через одну из простых онлайн IDE: IdeOne, TutorialsPoint C++, jDoodle. — РЕГИСТРИРУЕМСЯ при желании.
  • В качестве справочника стоит выбрать сайт cplusplus.com. Те немногие английские слова, которые придется запомнить для чтения материалов сайта в дальнейшем будут встречаться постоянно. — ИСПОЛЬЗУЕМ

Более подробные рекомендации и важные дополнения можно найти здесь.

Вы наверняка заметили, что в качестве языка программирования я без долгих пояснений выбрал С++. Вокруг выбора первого языка для начального изучения программирования ведутся бесконечные споры. Я не хочу даже пытаться включиться сейчас в эти святые войны. Хотя признаюсь, я не считаю, что у Вас в этом вопросе реально есть какой-то выбор. Даже если вам придется в дальнейшем перейти, например, на Java или C#, попытка использования С++ вероятно будет вполне рациональным расходованием времени.

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

План решения задач может быть таким
1. Линейные вычисления (147)
2. Программы с ветвлением (188)
3. Циклы (204)
4. Потоковая обработка (72)
5. Массивы (64)
6. Многомерные массивы (78)
7. Строки c-string (40)
8. Строки string (73)
9. Последовательные контейнеры (37)
A. Сортировки и жадность (8)
B. Стеки-деки-очереди (49)
C. Ассоциативные контейнеры (9)
D. Графы (44)
E. Дерево отрезков (16)
F. Динамическое программирование (7)

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах

Как не нужно решать задачи

Есть довольно подробные рекомендации, как нужно решать задачи по программированию (в т.ч. для студентов). В конце заметки я дам ссылки на одну из таких статей.
Но я хотел бы сейчас привести наглядный пример того, как не надо решать задачи.
Вот довольно простая задача про разрезание брусочка сыра (точнее прямоугольного параллелепипеда) на кубики со стороной 1. Это одна из задач с которых первокурсники начинают у нас изучать программирование. Решается она одной формулой:

Моделирование и системный подход. Вся супер идея решения состоит в наблюдении, что разрезая что-либо несколькими параллельными разрезами, вы получаете на один кусок больше чем было разрезов. Например, один разрез — два куска. Правда сложно заметить?
Да, придется понаблюдать за тем, что происходит если производить дополнительные разрезы в перпендикулярном направлении. Т.е. после разрезов в одной плоскости получаются пластины, во второй — соломка, в третьей — кубики. Понаблюдайте:

    Именно так человек решает задачи.

  1. Читает условие — иногда несколько раз и обязательно все буквы. Отделяет существенное от неважного.
  2. Представляет себе описанный процесс и его конечный результат отсекая ненужные для решения детали.
  3. Пытается описать формулами процесс или результат. Упрощает формулы.
  4. И наконец — кладет руки на клавиатуру и кодирует.

Возможно Вы заметили, что в первом коротком решении мы не выполнили собственную рекомендацию — не упростили формулу. Действительно, хотя все измерения абсолютно равнозначны, формула не выглядит симметричной. Это сделано чтобы понятнее был процесс вывода формулы. Первое слагаемое [latex]A-1[/latex] в общем числе разрезов показывает как мы резали перпендикулярно оси [latex]Ox[/latex]. Мы сделали [latex]A-1[/latex] разрез и получили [latex]A[/latex] пластин. Второе слагаемое [latex]A\cdot\left(B-1\right)[/latex] показывает как мы резали перпендикулярно оси [latex]Oy[/latex]. Мы сделали [latex]B-1[/latex] разрез в каждой из [latex]A[/latex] пластин полученных при предыдущей серии разрезов. И наконец, на последнем этапе, мы режем каждый из [latex]A\cdot B[/latex] брусочков на кубики при помощи [latex]С-1[/latex] разрезов. Получаем [latex]A\cdot B\cdot\left(C-1\right)[/latex] разрезов. Конечно, результат не должен измениться, если резать в каком-то другом порядке. Если раскрыть скобки и привести подобные мы увидим короткую симметричную относительно измерений формулу.

[latex]\left(A-1\right) + A \cdot \left(B-1\right) + A \cdot B \cdot \left(C-1\right) = ABC-1[/latex]

Аналитический подход. Эта новая формула может быть получена другими очень простыми рассуждениями.

Вначале был один большой кусок. После каждого разреза количество кусочков увеличивается на 1. В самом конце получится [latex]ABC[/latex] кусочков, значит разрезов было на 1 меньше — [latex]ABC-1[/latex].

Это последнее рассуждение демонстрирует подход к которому нужно стремиться — все просто, ясно, лаконично. Не всегда он срабатывает. Часто именно моделирование и системный подход с разбиением на системы и подсистемы позволяет найти решение. Но обычно этот путь более громоздкий. Зато аналитический иногда похож на некий волшебный трюк, когда задача с хлопком исчезает и на её месте появляется ответ. Подробнее об этом, например, здесь

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

Код программы с новой формулой

Это правильный подход. Но как решает задачу человек, который полностью сконцентрирован на программировании. А он её вообще не решает! Он её программирует. Прочитав про разрезание пространственной фигуры в трех областях он уже кодирует трехмерный массив.

Я позаимствовал это решение с форума, но у нас имеются и свои подобные решения. Они работают правильно. Вот только долго. Но это еще не всё. Представляете количество времени потраченное на его качественную отладку и тестирование? А в реальных проектах этот код возможно потом придется долгие годы поддерживать и переписывать на новые языки программирования!
Чтобы разобраться как работает это второе решение достаточно посмотреть следующее видео

Пожалуйста! Не решайте задачи так!

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

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах

Минутка мотивации

Беседа Татьяны Романовой (Google Inc.) с первокурсниками прикладной математики ОНУ 15 сентября 2016

Беседа Татьяны Романовой (Google Inc.) с первокурсниками прикладной математики ОНУ 15 сентября 2016

Слайды выступления Татьяны Романовой (Google Inc.) перед первокурсниками Прикладной математики ОНУ 15 сентября 2016.

Мотивация

Мотивация это то, что заставляет нас поступать так, как мы поступаем. В этой заметке я хотел бы предложить несколько причин, по которым стоит глубоко изучать (и практиковать!) математику, алгоритмы и программирование именно с точки зрения студентов нашего университета.
Конечно, основной мотивацией является хорошее трудоустройство, интересные проекты, высокая зарплата и хорошее интересное общение. Всем этим не обделены специалисты в области информационных технологий и разработки программного обеспечения. Я уже рассказывал о наших студентах, успешно занимающихся спортивным программированием, которые проходят стажировки в Google, Facebook и конечно в местных филиалах компьютерных фирм. Рассказывал также об основанном нашими студентами успешном стартапе Looksery, который весной этого года был приобретён компанией Snapchat за 150 миллионов долларов.

Письмо из Google

Письмо из Google

Недавно появилось ещё одно свидетельство внимания крупных компаний к нашим выпускникам.
За последнюю неделю выпускники прикладной математики разных лет получили похожие письма от компании Google с приглашением на работу. Приглашение в частности обосновывается высоким уровнем подготовки выпускников ОНУ уже работающих в компании. Здесь приводится копия экрана с текстом письма Андрею Терещенко. Аналогичные письма получили Кирилл Чеканов, Михаил Герасименко, Денис Щелконогов и др. Поиск наших выпускников Google провёл по профессиональной социальной сети linked.in.

Какие не очевидные выводы должен (или может?) сделать студент младших курсов?
Конечно, основный вывод в том, что нужно учиться и наш университет для этого подходит.
Второй вывод — не следует ограничиваться обязательной программой. Подготовки «по конспектам» совершенно недостаточно. Нужно читать книги, использовать интернет для самообразования, посещать дополнительные занятия по субботам и искать другие профессиональные мероприятия. В частности очень полезно участие в спортивных соревнованиях программистов. И дело тут не только в соревновательном аспекте. Контесты хороший повод попытаться решать задачи, а не учебные примеры на определённую тему. На соревновании Вы должны выбрать задачу, которую вероятно сможете решить и выбрать те из своих знаний и навыков, которые приведут Вас к цели. Это позволяет трезво оценить накопленные навыки и знания, а при необходимости внести корректировки в процесс своего обучения.
И третий вывод — сообщайте миру о себе и своих возможностях. Для этого хорошо подходит linked.in. Обязательно фиксируйте там все свои достижения — прохождение учебных курсов, освоение новых технологий, языков (и человеческих и машинных).

Это всё со стороны студента. А какая мотивация у преподавателя? Стыдно признаться, но единственный разумный ответ мне подсказывает неизвестный переводчик одиннадцатого сонета Шекспира

Ничто не вечно под луной. Но жизнь
Бессмертна эстафетой поколений.
Коль этим даром, друг мой, дорожишь,
Оставь свой след, отбросив яд сомнений.

Пусть красота живительной струёй
В преемнике, как Феникс, возродится,
А бездарь обойдёт вас стороной.
И злу чтоб не дано было свершиться.

Иначе человечеству конец
и жить ему лишь шесть десятилетий.
Хвала природе, ты – её венец,
За сохраненье рода ты в ответе.

Да не иссякнет мудрости печать,
Что ты сумел потомкам передать!

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах