Task 36. Единицы
UniLecsЗадача: В арифметическом выражении можно использовать число 1, сложение, умножение и скобки. Нужно вывести наименьшее количество единиц, ктр нужны, чтобы получить заданное натуральное число N.
Например, чтобы получить число 6 необходимо 5 единиц:
6 = (1 + 1) * (1 + 1 + 1)
Для числа 7 - 6 единиц:
7 = (1 + 1 + 1) * (1 + 1) + 1
Идея: очевидно, что задачу нужно начать разбирать с простых примеров и на их основе получить более общее решение. А это почти наверняка означает задачу из раздела динамического программирования.
Вкратце в чем фишка динамики:
1. Разбиение задачи на подзадачи меньшего размера.
2. Нахождение оптимального решения подзадач рекурсивно.
3. Использование полученного решения подзадач для конструирования решения исходной задачи.
Подзадачи решаются делением их на подзадачи ещё меньшего размера, пока не приходят к тривиальному случаю задачи, решаемой за константное время.
Итак, поехали.
Нужно найти оптимальное решение для n.
Пусть f(n) - равно наименьшему кол-ву единиц, с помощью ктр получим n.
Очевидно, что f(1) = 1.
Также при несложных подсчетах, очевидно, что
f(2) = 2, f(3) = 3, f(4) = 4, f(5) = 5.
f(2) = 1 + 1 = 2;
f(3) = 1 + 1 + 1 = 3;
f(4) = 1 + 1 + 1 + 1 = 4 или f(4) = (1 + 1) * (1 + 1) = 4
f(5) = 1 + 1 + 1 + 1 + 1 = 5 или f(5) = (1 + 1) * (1 + 1) + 1 = 5
Для числа 6 наименьшее кол-во единиц равно 5
f(6) = (1 + 1) * (1 + 1 + 1)
Пусть мы получили искомое кол-во единиц для числа n. Тогда:
1. Пусть последней операцией было сложение. Первое слагаемое i состоит из f(i), тогда второе n-i состоит из f(n-i)
Значение i следует выбрать таким образом, чтобы сумма f(i) + f(n-i) была минимальной.
Получаем первую формулу:
f(n) = min[f(i) + f(n-i)], где 1 <= i <= n
2. Второй вариант, пусть последней операцией было умножение. Первый множитель i состоит из f(i) единиц, второй множитель n/i из f(n/i).
Тут нужно учесть, что n делится на i без остатка.
Получаем вторую формулу:
f(n) = min[f(i) + f(n/i)], где 1 <= i <= n
В итоге получаем результирующую формулу:
f(n) = Min[ min[f(i) + f(n-i)], min[f(i) + f(n/i)] ], где 1 <= i <= n
Реализация:
https://gist.github.com/unilecs/64b33a865bcf734d671bb9ddcddf1c11
Тест: