На числовой строке от отрицательного бесконечного до положительного бесконечного, если вы начинаете с 0, вы можете либо вернуться назад, либо вперед. но каждая длина прыжка на 1 больше, чем предыдущий прыжок. Учитывая число в числовой строке, мы можем связаться с ней, используя любую комбинацию прыжков. Если да, напечатайте путь минимальной длиныМинимальный путь в числовой строке
Это, кажется, вопрос для интервью, поэтому я не буду предлагать сложное решение. Однако, попытайтесь доказать следующее (п Е (I) означает суммирование от 1 до п):
Для всех целых чисел в
{ k : k <п Σ (я),п Е (i)- k is odd, k ϵ N }, k не может быть достигнуто с 0 с использованием любой комбинации прыжков взад или вперед с длиной 1 до длины n.
Используя это, ответ на ваш вопрос становится довольно простым. Если у вас все еще есть какие-либо трудности, пожалуйста, укажите в комментариях.
Являются ли размеры прыжка целыми? Они начинаются с одного размера? Кроме того, что вы пробовали до сих пор? – templatetypedef
Для первого вопроса да, он всегда доступен, так как вы можете использовать + n, - (n + 1) для вычитания 1 и -n + (n + 1), чтобы добавить 1. Вы можете повторить это навсегда. Самый короткий путь требует немного больше мысли. – moreON
Да, размеры прыжка - целые числа –