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

Есть довольно подробные рекомендации, как нужно решать задачи по программированию (в т.ч. для студентов). В конце заметки я дам ссылки на одну из таких статей.
Но я хотел бы сейчас привести наглядный пример того, как не надо решать задачи.
Вот довольно простая задача про разрезание брусочка сыра (точнее прямоугольного параллелепипеда) на кубики со стороной 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].

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

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

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

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

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

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

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

Ровно 20 простых делителей

Задача. За 2 секунды проверить предположение о том, что у некоторого числа [latex]n \le 10^{18}[/latex] имеется ровно 20 простых делителей.
Попытаться решить задачу и проверить своё решение можно здесь.

Тесты

Вход Выход Примечание
10000000000 Yes [latex]2^{10}\cdot 5^{10}[/latex]
1048576 Yes [latex]2^{20}[/latex]
999999999987679232 Yes [latex]2^19 \cdot 1907348632789[/latex]
2 No [latex]2^{1}[/latex]
1000000000000000003 No Простое число. Немного выходит за пределы ограничения задачи, но допустимо для типов unsigned long long
1000000000012845056 Yes [latex]2^{19}\cdot 1907348632837[/latex] Немного выходит за пределы ограничения задачи, но допустимо для типов unsigned long long
99999989699999923 No [latex]99999989 \cdot 1000000007[/latex]
8388608 No [latex]2^{23}[/latex] — слишком много делителей

Решение

Идея решения состоит в попытках деления исходного числа [latex]n[/latex] на последовательно увеличивающиеся целые числа [latex]d,[/latex] начиная с двойки. Если удается произвести деление без остатка, то очередной делитель найден. Исходное число можно разделить на этот делитель и в дальнейшем искать делители полученного частного, т.е. [latex]n \leftarrow \frac{n}{d}.[/latex] Теперь нам остается найти на один делитель меньше. Такая процедура должна будет успешно завершиться ровно 19 раз. Частное от последнего 19-го деления должно оказаться простым числом — тогда простых делителей окажется ровно 20.
При подготовке тестов выяснилось, что трудности могут вызывать следующие ситуации:

  1. No — отрицательный вердикт: слишком мало делителей. В худшем случае одно большое простое число.
  2. Yes — положительный вердикт: 19 небольших делителей и большой 20-й. В худшем случае рассматривается число [latex]2^{19} \cdot 1907348632789 = 999999999987679232[/latex]

В обоих случаях трудности вызывает поиск делителей довольно большого простого числа. Необходимо аккуратно ограничить диапазон поиска возможных делителей так, чтобы не выполнять излишней работы, но и не пропустить делителей.
Зададимся вопросом, как долго нам придётся перебирать возможные делители (начиная с числа 2) пока не встретим первый (наименьший) делитель?
Рассмотрим первый случай (слишком мало делителей). Пусть нам известно, что число имеет [latex]m[/latex] делителей. Первый, встретившийся нам делитель (т.е. наименьший) должен быть таким, чтобы [latex]d^{m} \le n, [/latex] т.е. [latex]d \le n^{\frac{1}{m}} = \sqrt[m]{n}.[/latex] Это очень хорошее ограничение, т.к. в первом случае нам придется перебирать возможные делители до [latex]\left( 10^{18} \right)^{\frac{1}{20}} = 10^{\frac{18}{20}} \le 7.[/latex] Это совсем немного вариантов. Т.е. достаточно проверить деление на 3, 5 и 7 для самого большого возможного [latex]n[/latex]. При правильном выборе границ поиска «страшный» случай огромного простого числа [latex]n[/latex] оказывается очень лёгким.

Границы поиска делителей в худшем случае
Теперь рассмотрим второй случай. У нас имеется 19 маленьких делителей (в худшем случае это двойки) и одно большое простое число. Насколько большие делители нужно проверить прежде чем заключить, что оставшееся число простое?
Оставшееся после 19 делений на два число не может превышать [latex]\frac{10^{18}}{2^{19}}=0.5 \cdot 5^{18}.[/latex] Если оставшееся число не является простым, то у него должен быть делитель не превышающий квадратного корня из этого числа. Т.е. поиск делителей в этом последнем случае не может продлиться дольше чем до [latex]\sqrt{0.5 \cdot 5^{18}} = 1381067.[/latex]

Код

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

  • При извлечении корня может быть получено неточное значение. Это связано как с ошибкой округления. Например, при работе с числами типа double [latex]\sqrt[3]{1000000}[/latex] оказывается не 100, как мы ожидаем, а примерно [latex]99.9999999999999716.[/latex] Из-за этого мы можем не найти делитель в точности равный правой границе интервала поиска. Для компенсации возможной ошибки к правой границе была добавлена некоторая небольшая величина. Конкретное значение выбирается на основании пессимистической оценки возможной погрешности.
  • Верхняя граница поиска делителей не превышает [latex]\sqrt[m]{n}[/latex] если число делителей [latex]m \ge 2.[/latex]. Когда мы хотим убедиться, что последнее [latex]\left(m=1\right)[/latex] оставшееся число является простым, мы ищем его делители до [latex]\sqrt[2]{n}.[/latex]. Т.е. предполагаем, что число не простое и ищем его делители.

Задание

Существенным недостатком программы является то, что она перебирает в качестве возможных простых делителей все чётные числа. Естественно, ни одно из них (кроме 2) не может оказаться простым делителем и работа выполняется впустую. Можно надеяться существенно уменьшить время работы программы за счёт правильной организации перебора возможных делителей.
Попытайтесь это сделать.

Числа Фибоначчи

Рассмотрим общеизвестный ряд чисел A000045:
[latex]0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, \ldots[/latex] Этот ряд представляет собой неотрицательную ветвь последовательности Фибоначчи. Будем считать, что последовательность задаётся следующим рекуррентным соотношением
[latex]f_n=\left\{\begin{matrix}
0, & n=0\\
1, & n=1\\
f_{n-1}+f_{n-2}, & n>1
\end{matrix}\right.[/latex]

Давайте напишем функцию, которая вычисляет [latex]n[/latex]-е по порядку число Фибоначчи, используя приведенное соотношение:

Для теста мы вывели на печать вычисленное этим способом 6-е по порядку число Фибоначчи. Программа напечатала 8. И не ошиблась. Давайте посмотрим как происходили вызовы функций:

Порядок вызовов при вычислении шестого по счёту числа Фибоначчи по прямому рекурсивному алгоритму

Порядок вызовов при вычислении шестого по счёту числа Фибоначчи по прямому рекурсивному алгоритму

Легко видеть, что для вычисления каждого числа Фибоначчи (кроме двух первых) выполняется строго два вызова функции. Т.е. если нам понадобится вычислить, следующее (седьмое) число Фибоначчи, то количество вызовов практически удвоится. И действительно, каждое следующее число вычисляется вдвое дольше, чем предыдущее. При наличии терпения ещё можно как-то дождаться конца вычисления 50-го числа, но дальше вычисляется уж очень долго.
В чём причина? Почему человек, вычисляя на листе бумаги, легко обгоняет компьютер?
Конечно, неэффективный алгоритм.
На рисунке цветом выделены те блоки, вычисление которых действительно необходимо. Число таких блоков растёт с увеличением номера числа линейно, говорят [latex]O\left( n\right)[/latex]. А вот остальные блоки — сплошные повторы и их число растёт как [latex]O\left( 2^n\right)[/latex].
Попробуйте изменить программу так, чтобы она работала быстро (без повторных вычислений.
В качестве упражнения, я попрошу не использовать циклов.
После того, как у Вас всё получится (или окончательно опустятся руки), загляните под спойлер и постарайтесь разобраться с моим вариантом решения задачи.
Рекурсивное решение без повторов

Мотивация

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

Письмо из Google

Письмо из Google

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

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

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

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

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

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

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

Related Images:

Дистанционные учебные курсы

Последнее обновление 8 октября 2016.

http://www.princeton.edu/

http://www.princeton.edu/

Хочу порекомендовать пройти некоторые дистанционные учебные курсы на сайте Coursera.

  • 10 октября 2016 стартует курс по Структурам данных. Довольно полезный. К сожалению, все больше учебных курсов становятся платными. Однако, есть возможность получить его бесплатно как вольный слушатель. Сертификата Вам в этом случае не выдадут, но знания получите
  • Во-первых, 3 октября 2016 началась первая часть учебного курса по Алгоритмам. Один из ведущих преподавателей знаменитый Роберт Седжвик. Даже если Вы опоздали к указанной дате (даже на год или два) стоит записаться и пройти.
  • Во-вторых, одновременно с предыдущим запускается ещё один курс Седжвика — Анализ алгоритмов

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

По обоим курсам указано, что

No certificates, statements of accomplishment, or other credentials will be awarded in connection with this course.

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

http://online.stanford.edu/

http://online.stanford.edu/

Наша выпускница Татьяна Полунина порекомендовала другой курс, который только начался 3 октября 2016. Я не знаком детально с этим курсом, но полностью полагаюсь на рекомендацию и добавляю курс в список:

Это курс из Стэнфордского университета и по окончании можно получить сертификат от преподавателя.

Также можно пройти курс Основы алгоритмов. Это первый из набора в шесть курсов. Если брать все шесть, то нужно платить. Если брать каждый по очереди и без сертификата, то получится бесплатно.

Не все студенты морально готовы проходить онлайн курсы на английском языке. Я уверен, что это стоит делать при любом уровне невладения английским. Однако, идя на уступки этой нерешительности, рекомендую несколько полезных курсов на русском языке. Все они стартуют с понедельника 10 октября 2016 и подготовлены для Coursera сотрудниками МФТИ.

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

Решаем задачи

Чтобы тренироваться решать задачи мы будем чаще всего использовать сайт e-olymp.com. Также можно обратиться к

  • codewars.com — Решаем задачи («ката») разного уровня сложности и набираем уровень.
  • programmr.com — Будьте внимательны, есть ошибки в тестах. Например, задача на площадь треугольника предполагает целочисленное деление при вычислении полупериметра. (Проверялось 11.5.2017).
  • tutorialspoint.com — учебный курс с задачами.

Образец: Принадлежит ли точка треугольнику?

Задача. Даны три попарно не совпадающие и не лежащие на одной прямой точки [latex]A, B[/latex] и [latex]C[/latex], заданные своими координатами. Определить принадлежит ли точка [latex]D(x_d,y_d)[/latex] треугольнику [latex]ABC[/latex].
Сразу заметим, что задача легко обобщается для любого выпуклого многоугольника.

Тесты

В тестах нужно обязательно отразить следующие случаи:

  1. Точка строго вне треугольника
  2. Точка строго внутри треугольника
  3. Точка совпадает с одной из вершин треугольника
  4. Точка лежит на одной из сторон треугольника
  5. Точка лежит на продолжении одной из сторон треугольника
  6. Одна из сторон треугольника параллельна одной из осей координат
  7. Две стороны треугольника параллельны осям координат
xa ya xb yb xc yc xd yd Принадлежит?
-1 -1 1 -1 0 1 2 2 нет
-2 -2 1 -1 0 1 0 0 да
-1 -1 1 -1 0 1 0 1 да
-1 -1 1 -1 0 1 0.5 0 да
-1 -1 1 -1 0 1 1 3 нет
-1 -1 1 -1 0 1 0 0 да
0 0 2 0 0 2 1 1 да
0 0 2 0 0 2 5 5 нет

Плохое решение

В школьных учебниках такие задачи часто рекомендуют решать проверкой условия [latex]S_{ABC}=S_{ABD}+S_{BCD}+S_{CAD}[/latex]. При компьютерной реализации это приводит к необходимости сравнения двух действительных чисел на равенство. Эта крайне неприятная операция может быть проделана только с определённой степенью достоверности. Т.е. придётся проверять не превышает ли некоторого «с потолка» выбранного малого числа абсолютное [latex] \left| S_{ABD}+S_{BCD}+S_{CAD}-S_{ABC} \right| < \varepsilon[/latex] или относительное [latex]\left| 1-\frac{S_{ABD}+S_{BCD}+S_{CAD}}{S_{ABC}} \right| < \varepsilon[/latex] отклонение. Оставим эти вопросы для курса численных методов и методов приближённых вычислений и не будем идти по этому пути.

Неплохое решение

Начнём с простого наблюдения:

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

Запишем уравнение прямой, проходящей, например, через точки [latex]A[/latex] и [latex]B[/latex]. Получим [latex] \left( x-x_A \right) \left( y_B-y_A \right)-\left( y-y_A \right) \left( x_B-x_A \right) = 0[/latex]. Уравнение я записал в такой форме, чтобы не приходилось выполнять деление и переживать о нуле в знаменателе.

Неважно как называть стороны, важно научиться их различать.

Неважно как называть стороны, важно научиться их различать.

Теперь для любой точки [latex] \left( x;y \right)[/latex] мы можем вычислить левую часть приведенного равенства. Для точек, лежащих на прямой мы должны получать ноль. В тоже время прямая разобьёт плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения. А точки из другой полуплоскости — отрицательные.
Мы готовы проверить первое условие — принадлежит ли точка [latex]D \left( x_d,y_d \right) [/latex] той же полуплоскости, что и точка [latex]C \left( x_c,y_c \right) [/latex] относительно прямой [latex] \left( AB \right) [/latex]? Для этого подставим обе точки в левую часть приведенного выше уравнения прямой и убедимся, что получены значения одного и того же знака. А если одна из точек даст точно ноль? Это означает, что точка лежит на прямой. По условию задачи это может быть только точка [latex]D[/latex]. Тогда она принадлежит треугольнику независимо от знака выражения, вычисленного для точки [latex]C[/latex].

Обратите внимание, что мы не утверждаем, что для любой точки на прямой наши приближённые вычисления обязаны дать точный ноль. Это было бы неверно. Мы только утверждаем, что если проведенные с доступной нам точностью вычисления всё же дали точный ноль, то мы вынуждены считать данную точку лежащей на данной прямой.

Естественно, что нам придётся записать аналогичные условия для двух оставшихся сторон треугольника (или для всех оставшихся сторон выпуклого многоугольника).

Плохой код

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

Нажмите здесь, чтобы выполнить этот код.

Приведенный код имеет существенные недостатки. Нам пришлось трижды записывать уравнение прямой проходящей через две точки и дважды подставлять в каждое из них координаты, чтобы проверить знак. Это значит, что нам пришлось шесть раз написать некоторую формулу с различными подстановками. При том подходе, что мы использовали имеем две проблемы. Во-первых, условие стало слишком сложным, чтобы его можно было легко воспринять. Во-вторых, и это гораздо хуже, такой код в [latex]\frac { 1-{ \left( 1-p \right) }^{ 6 } }{ p }[/latex] раз увеличивает вероятность совершить ошибку. Забавно, но это означает, что вероятность ошибки начинающего программиста увеличивается вдвое, а у опытного — в шесть раз. Хорошо, что опытные программисты не пишут такой код.

Неплохой код

Воспользуемся тем, что мы уже умеем создавать собственные функции для того, чтобы несколько сократить объём кода и сделать его более лёгким для восприятия.
Запишем условие на языке программирования С++:

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

Чеширский код

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать...

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать…

Возможно слишком смело называть это хорошим кодом, но мы сделаем ещё один шаг в нужном направлении. В прошлом коде мы избавились от повторов в кодировании алгоритма. Однако остались повторы в кодировании данных. Вы заметили, что у нас четыре пары переменных? Т.е. просматривается структура состоящая из пары координат x и y, которую стоит объединить и назвать «точкой». Такие структуры в программировании на Си описывают с помощью ключевого слова struct. Это полезная промежуточная структура перед переходом к объектно-ориентированному программированию при помощи классов.

Нажмите здесь, чтобы выполнить этот код.
Вы заметили как забавно увеличивается размер программы по мере того, как мы пытаемся сделать его более логичным и наглядным? Это характерно для маленьких программ. Такие дополнительные структуры становятся всё более оправданными для больших и огромных программ.