Разберём простую прекрасную задачу, в которой есть математика и строгое доказательство. Читаем условие:
Для начала надо убедиться, что возможно разложить любое число, большее 7, на сумму пятёрок и троек. Докажем это с помощью математической индукции.
База индукции: N = 8 = 5 + 3. Выполняется.
Шаг индукции: пусть для всех чисел от 8 от N выполнено, докажем, что и для N+1 имеется разложение. Если в разложении N имеется хотя бы одна пятёрка, то можно заменить её на две тройки, таким образом получим разложение для N+1. Если пятёрок нет, тогда имеется как минимум три тройки (так как число больше 7), заменим их на две пятёрки, снова получив корректное разложение числа N+1. Шаг индукции доказан.
Значит, по принципу математической индукции, можно разложить любое число, большее семи.
Теперь можем приступать к написанию решения. Сначала считаем входные данные:
Дополнительным ограничением на ответ является то, что количество монет должно быть минимальным. Это значит, что нам надо брать максимально возможное количество пятёрок.
Самым простым случаем является число N кратное пяти, тогда надо взять N/5 монет у Базилио. Но по аналогии можно рассмотреть и другие четыре случая:
Теперь осталось вывести количество монет, которые берём у Базилио и у Алисы:
Здесь мы рассмотрели простое решение с разбором всех случаев, получив читаемое решение. Всё это можно ужать до:
- константного массива и взятия значений из него в зависимости от остатка от деления на 5,
- или даже до формулы,
существенно уменьшив размер кода и снизив понятность решения.
А также, мы на простом примере потренировались в применении принципа математической индукции для доказательства.
Предыдущий выпуск: Задача 329. Лесенка - 2
Задонатить автору на бусти.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.