Всем привет!
Сегодня логическая задача. По другому никак не могу описать.
Потому что сложность у задания стоит «Medium», а решение состоит из двух встроенных функций, с которых обычно начинают знакомиться с Питоном.
В задаче, дано десятичное число, которое нужно разбить на сумму чисел, состоящих из единичек и нулей (первая цифра должна быть значащей, то есть единицей). Искомый результат – минимальное количество разбиений (то есть цифр состоящих из единичек и нулей).
Даны хорошие примеры:
1. 32 = 10 + 11 + 11 ответ: 3
2. 82734 ответ: 8
3. 27346209830709182346 ответ: 9
Кто хочет, может попробовать найти логику решения самостоятельно…
Логика решения:
Для начала я подумал, что чем больше число, тем больше сумма таких чисел, тем быстрее мы получим нужный результат. Соответственно из единичек и нулей, мы оставляем только единички составляем число нужного разряда. Так для двузначного числа «32» максимальным разбиением будет «11», затем снова «11» и только потом «10».
Для числа «82734» следуя такой логике мы можем вычесть 7 раз по «11111», но в конце получится 4957. А это число никак не сводится к нулям и единицам.
Минимальное количество слагаемых не получается из максимальных чисел. Контринтуитивно. Что же тогда делать?
Дальше я зацепился за то, что после вычитания последней «11111» остался только 1 «ход».
Соответственно, можно уменьшить предыдущие слагаемые так, чтобы разряд последнего числа повысился (осталось пятизначное число). Я буквально в табличке (в Excell) переставлял единички на нолики, чтобы в конце осталось «10000» или что-то рядом. И быстро нашел необходимую комбинацию.
82734 = 11111 + 10111+11011+10101+10100+10100+10100+10100
Я смотрел на все это и никак не мог понять, как составить алгоритм, который бы составлял эти числа из «0» и «1».
Тут я посмотрел на следующее число и подумал, что тут что-то не то. Слишком большой разряд. Слишком много итераций. А ответ однозначный «9».
И тут до меня дошло…
Не важно какое число, нужно просто отнимать единички от максимальной цифры в числе. Визуализировать это можно следующим образом:
Тогда решение сводится к поиску максимальной цифры в числе.
Решение
Сначала я попробовал в цикле for сравнивать текущую цифру с максимальной на данный момент. Решение работало, но было слишком медленным. Даже добавление условия (если максимальное на данный момент число равно «9» break) не сильно исправило ситуацию
Тогда я подумал, а почему бы не использовать функцию max() сразу на данное число?
Правда, число было дано в формате строки. И я сразу же получил ошибку, потому что вернуть нужно было целое число (<class 'int’>). Но не беда, подумал я, и с помощью функции int() преобразовал строку в переменную. К моему удивлению такое решение сработало.
Оказалось, что Питон отлично находит максимальный элемент в строке.Так в строке:
'123456789' ,
максимальным элементом будет '9' .
С буквами тоже понятно. В английском максимум соответствует номеру буквы в алфавите. В строке:
'abcdefghijklmnopqrstuvwxyz' ,
максимальным элементом будет ‘z’.
С русским сложнее, там максимум почему-то у буквы ‘ё’. Но если её убрать, то все становится логично. Знаки препинания тоже можно посчитать, но логики я не вижу.В этой строке:
'=+-_!@#$%^&*():;'".,/?|\<>’,
максимум за такой палочкой '|'
Вот так-то…
До скорого