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

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

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

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

Latest posts by Мазурок Игорь Евгеньевич (see all)

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

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

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

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

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

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

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

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

Монстр

Антон Куперман
Антон Куперман

Latest posts by Антон Куперман (see all)

Задача 787A с сайта codeforces.com.

Задача

Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени b, b + a, b + 2a, b + 3a, …, а Морти кричит в моменты времени d, d + c, d + 2c, d + 3c, ….

Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.

Ввод

Первая строка входных данных содержит два целых числа a и b (1 ≤ a, b ≤ 100).

Вторая строка входных данных содержит два целых числа c и d (1 ≤ c, d ≤ 100).

Вывод

Выведите первый момент времени, когда Рик и Морти закричат одновременно, или  - 1, если они никогда не закричат одновременно.

Тесты

Ввод
Вывод
20 2
9 19
82
2 1
16 12
-1

Код

Решение

В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при и c. Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.

KM194. Взаимно простые числа

Задача

Даны два взаимно простых натуральных числа [latex]a[/latex] и [latex]b[/latex]. Рассмотрим множество [latex]M[/latex] целых чисел, представимых в виде [latex][ax+by][/latex] , где [latex]x[/latex] и [latex]y[/latex] — целые неотрицательные числа. Каково наибольшее целое число [latex]c[/latex], не принадлежащее множеству [latex]M[/latex]?

Входные данные

[latex]a[/latex] и [latex]b[/latex] — два взаимно простых натуральных числа.

Выходные данные

[latex]c[/latex] — наибольшее целое число c, не принадлежащее множеству [latex]M[/latex].

Тесты

Входные данные Выходные данные
[latex]a[/latex] [latex]b[/latex] [latex]c[/latex]
5 3 7
2 1 -1
3 2 1

Код программы

Решение

Нарисуем на плоскости систему координат [latex]Oxy[/latex] и сформулируем нашу задачу на геометрическом языке. Каждую пару целых чисел [latex]\left(x,y\right)[/latex] мы будем называть «целой точкой» и изображать красной точкой, если обе её координаты неотрицательны [latex]\left(x\geq0, y\geq0\right)[/latex], и синей точкой — если хотя бы одна координата отрицательна.

Взаимно простые натуральные числа [latex]a[/latex] и [latex]b[/latex] мы считаем фиксированными (для примера возьмём [latex]a=5, b=3[/latex]). Для каждого [latex]n[/latex] уравнение [latex]ax+by=n[/latex] определяет, как известно, прямую. Обозначим её через [latex]l_{n}[/latex]. Разумеется, все прямые [latex]l_{n}[/latex] параллельны друг другу. Пусть [latex]n[/latex] — целое. Будем считать прямую [latex]l_{n}[/latex] красной, если она проходит хотя бы через одну красную точку, и синей — в противном случае. Мы должны выяснить, каково наибольшее [latex]c[/latex], которому соответствует синяя прямая [latex]l_{с}[/latex], и доказать, что тогда из двух прямых [latex]l_{n}[/latex] и [latex]l_{c-n}[/latex] одна-синяя и одна-красная ([latex]n[/latex] — любое целое число).
Мы будем пользоваться в нашем решении перемещениями плоскости, которые отображают множество целых точек на себя и одновременно каждую прямую [latex]l_{n}[/latex] переводят в ту же самую или некоторую другую прямую [latex]l_{\acute{n}}[/latex] из нашего семейства. Это, во-первых, параллельные переносы на любой вектор [latex]\left(p, q\right)[/latex] с целыми [latex]p[/latex] и [latex]q:[/latex] [latex]\left(x,y\right)|\dashrightarrow \left(x+p, y+q\right),[/latex] и, во-вторых, повороты на [latex]180^{\circ}[/latex] (или, что то же самое, симетрии относительно точки) с любыми центрами [latex]\left(\frac{p}{2}, \frac{q}{2}\right)[/latex], где [latex]p[/latex] и [latex]q[/latex] — целые: [latex]\left(x,y\right)|\dashrightarrow \left(p-x, q-y\right).[/latex] Докажем, что на каждой прямой [latex]l_{n}[/latex] целые точки встречаются через равные промежутки.
Лемма. Если [latex]\left(x_{0},y_{0}\right)[/latex] — целая точка на прямой [latex]l_{n}[/latex], то ближайшими к ней целыми точками на [latex]l_{n}[/latex] будут [latex]\left(x_{0}-b,y_{0}+a\right)[/latex] и [latex]\left(x_{0}+b,y_{0}-a\right)[/latex] ([latex]a[/latex] и [latex]b[/latex] взаимно просты).
Рассмотрим прямую [latex]l_{0}[/latex], проходящую через [latex]\left(0, 0\right)[/latex]. Пусть [latex]\left(-b_{1}, a_{1}\right)[/latex] — ближайшая к [latex]\left(0, 0\right)[/latex] целая точка [latex]l_{0}[/latex] такая, что [latex]b_{1}>0[/latex], [latex]a_{1}>0[/latex] (мы ещё не знаем, что [latex]b_{1}=b, a_{1}=a[/latex]), [latex]\left(x_{0}, y_{0}\right)[/latex] — целая точка [latex]l_{n}[/latex]. При переносе на вектор [latex]\left(x_{0}, y_{0}\right)[/latex] отрезок прямой [latex]l_{0}[/latex] от [latex]\left(0, 0\right)[/latex] до [latex]\left(-b_{1}, a_{1}\right)[/latex] перейдет в отрезок [latex]l_{n}[/latex] от [latex]\left(x_{0}, y_{0}\right)[/latex] до [latex]\left(x_{0}-b_{1}, y_{0}+a_{1}\right)[/latex] будет ближайшей к [latex]\left(x_{0}, y_{0}\right)[/latex] точкой [latex]l_{n}[/latex] сверху. Точно так же при переносе на вектор [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] — тот же отрезок прямой [latex]l_{0}[/latex] перейдёт в отрезок прямой [latex]l_{n}[/latex] от [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] до [latex]\left(x_{0}, y_{0}\right)[/latex]. Следовательно, и на этом отрезке целыми точками будут только его концы.
Отсюда уже следует, то на любой прямой [latex]l_{n}[/latex] (уесли на ней есть хоть одна целая точка) промежуток между соседними целыми точками один и тот же: [latex]a_{1}[/latex] единиц по оси [latex]Oy[/latex] и [latex]b_{1}[/latex] — по оси [latex]Ox[/latex]. Это, в частности, относится и к прямой [latex]l_{0}[/latex]. Поскольку [latex]\left(-b, a\right)[/latex] принадлежит [latex]l_{0}[/latex], то отсюда следует, что [latex]b=db_{1}, a=da_{1}[/latex], где [latex]d[/latex] — некоторое целое число. Но числа [latex]a[/latex] и [latex]b[/latex] по условию взаимно просты. Значит, [latex]d=1[/latex], то есть [latex]a=a_{1}, b=b_{1}[/latex]. Лемма доказана.
Из этой леммы следует, что каждая прямая [latex]l_{n}[/latex], где [latex]n[/latex] — целое, переходит ровно через одну точку внутри полосы [latex]0\leq x\leq b-1[/latex]. При этом, очевидно, если прямая красная, то есть где-то переходит через красную точку, то её целая точка в выделенной полосе тоже будет красной (а точка синей прямой, разумеется, синяя).
Теперь заметим, что при симетрии относительно точки [latex]\left(\frac{b-1}{2} -\frac{1}{2}\right)[/latex] [latex]\left(x,y\right)\mapsto\left(\acute{x}, \acute{y}\right) =\left(b-1-x, -1-y\right)[/latex], полоса [latex]0\leq x\leq b-1[/latex] переходит в себя, причем красные точки переходят в синие, и наоборот. Прямая [latex]l_{n}[/latex] после этой симметрии переходит в прямую [latex]l_{ab-a-b-n}[/latex]: если [latex]ax+by=n[/latex], то [latex]a\acute{x}+b\grave{y}=a\left(b-1-x\right)+b\left(-1-y\right)=ab-a-b-n.[/latex] (Через центр симметрии, где [latex]a\left( \frac{b-1}{2}\right)+b\left(- \frac{1}{2}\right) = \frac{ab-a-b}{2},[/latex] ни одна из наших прямых может и не проходить.)
Ясно, что самая нижняя красная прямая — это [latex]l_{0}[/latex]. Следовательно, самая верхняя синяя прямая — это [latex]l_{ab-a-b}.[/latex] Итак, наибольшее число, не принадлежащее множеству, — это [latex]c=ab-a-b,[/latex] и из двух чисел [latex]n[/latex] и [latex]c-n[/latex] одно принадлежит [latex]M[/latex], а другое — нет.

Ссылки

Ideone;
Решение задачи Журнал «Квант» №11 г.1973 (стр. 44-45);
Условие задачи Журнал «Квант» №3 г.1973 (стр. 35).

КМ 29. Монеты

Герман Веранян
Герман Веранян

Latest posts by Герман Веранян (see all)

Задача

Задача из журнала «Квант» №6 1970 г. стр. 28 В.И.Арнольд

[latex]n[/latex] одинаковых монет лежат на столе, образую замкнутую цепочку. Сколько оборотов сделает монета [latex]M[/latex] такого же размера за то время, пока она один раз обкатится по внешней стороне всей цепочки, как показано на рисунке (монета [latex]M[/latex] =2 коп.)?
Как изменится ответ, если монета [latex]M[/latex] будет иметь радиус, отличающийся в [latex]k[/latex] раз от радиуса каждой из монет в цепочке?

Условие
Представлю вам предложенное для данной задачи изображение из самого журнала.

Тесты

Входные данные Выходные данные
 № [latex]n[/latex] [latex]k[/latex]  Количество оборотов
 1  3  1  3
 2  12  1  6
 3  182  1  62.667
4  12  2.22 3.19998
 5  145  2.28101  22
 6  8  0.53884  8

 

Код.

 

Решение.

Примем радиус монет, составляющих цепочку, за единицу. За то время, пока монета радиуса [latex]k[/latex] прокатится по дуге [latex]\alpha[/latex] неподвижной окружности радиуса 1, она повернется на угол [latex]\alpha(1+1/k)[/latex] следовательно весь угол на который повернётся монета, равен [latex]\alpha+\alpha/k[/latex](в частности, при [latex]k[/latex]=1 этот угол равен 2[latex]\alpha[/latex]).
Теперь найдем сумму дуг,состоящих из таких точек неподвижных монет, которых монета [latex]M[/latex] касалась при качении по цепочке. Если принять центры монет цепочки за точки [latex]O_1[/latex], [latex]O_2[/latex], … , [latex]O_n[/latex], то сумма дуг, лежащих внутри многоугольника [latex]O_1[/latex][latex]O_2[/latex]…[latex]O_n[/latex], равна сумме его внутренних углов, то есть [latex]\pi(n-2)[/latex]. Сумма дуг, лежащих вне многоугольника, следовательно, равна [latex]\pi(n+2)[/latex].Из неё нужно вычесть ещё сумму дуг лежащих в углублениях между двумя соседними монетами, в которые [latex]M[/latex] не попадает. В каждом из [latex]n[/latex] углублений сумма двух таких дуг равна [latex]2\pi/3[/latex] при [latex]k[/latex]=1 и [latex]2arccos\frac{1}{k+1}[/latex] в общем случае. Итак, сумма дуг, по которым прокатится монета [latex]M[/latex], равна [latex]\pi(n+2)-2\pi n/3[/latex] (в общем случае [latex]\pi(n+2)-2n\arccos\frac{1}{k+1}[/latex]. Чтобы узнать искомое число оборотов, нужно умножить эту велечину на [latex]2[/latex]( в общем случае на [latex]1+1/k[/latex]) и разделить на 2[latex]\pi[/latex].
А значит ответ ([latex]\frac{n}{3}+2[/latex]) оборота при k=1, и [latex]\frac{k+1}{2k}(n-\frac{2}{\pi}n \arccos\frac{1}{k+1}+2)[/latex] оборота в общем случае.

Ссылка на решение:Ideone

ML30. Объём параллелепипеда

Задача. Найти объём параллелепипеда три стороны которого образованы векторами [latex] \overrightarrow{a}=(a_x,a_y,a_z),[/latex] [latex]\overrightarrow{b}=(b_x,b_y,b_z)[/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z).[/latex]

Входные данные: Координаты векторов [latex]\overrightarrow{a},[/latex] [latex] \overrightarrow{b},[/latex] [latex]\overrightarrow{c}. [/latex]

Выходные данные: Объём параллелепипеда.

Тесты

Входные данные Выходные  данные
0 0 1 0 1 0 1 0 0  1
0 0 0 1 0 0 0 0 1  0
1 0 0 0 0 1 0 0 1  0
2 5 3 4 1 0 -2 7 6  18
3 5 1 0 -7 2 6 -4 5  21

Код программы

Решение

Для решения данной задачи можно составить матрицу и вывести из неё формулу для нахождения определителя:
[latex]\triangle = \begin{vmatrix}a_x & a_y & a_z \\ b_x & b_y & b_z \\ c_x & c_y & c_z\end{vmatrix} =[/latex] [latex] a_x \left(b_y c_z+c_y b_z\right)[/latex] [latex]-a_y \left(b_x c_z+c_x b_z\right)+[/latex] [latex]a_z\left(b_x c_y+c_x b_y\right).[/latex]

Модуль определителя матрицы равен объёму параллелепипеда.

Решение на ideone.

D2547. Cумма ряда

Антон Куперман
Антон Куперман

Latest posts by Антон Куперман (see all)

Задача

Доказать сходимость и найти сумму ряда [latex]\sum \limits_{n=1}^{\infty}\left(\frac{1}{2^n}+\frac{1}{3^n}\right)[/latex].

Код

 

Решение

Ряд сходится,так как он является суммой двух бесконечно убывающих  геометрических  прогрессий. Знаменателем первой прогрессии([latex]s_1[/latex]) будет [latex]\frac{1}{2}[/latex], а знаменателем второй([latex]s_2[/latex]) — [latex]\frac{1}{3}[/latex]. Тогда по формуле суммы бесконечно убывающей прогрессии [latex]s=\frac{b_1}{1-q}[/latex], где [latex]b_1[/latex] первый член прогрессии, а [latex]q[/latex] — ее знаменатель. Затем суммируем суммы прогрессий и получаем ответ.

Ответ

[latex]\sum \limits_{n=1}^{\infty}\frac{1}{2^n}+\frac{1}{3^n}=\frac{3}{2}=1.5[/latex].

Ссылки

1.Решение на Ideone

2.Решение на WolframAlpha