0

Сразу к делу:

n = int(input())

Ввожу число и у меня есть 2 команды:

+ 1
* 2

Начальное значение a = 1, так вот с помощью этих команд за минимальное кол-во ходов нужно получить n, не подскажите как это сделать Протокол:

Input        Output
  11            5   
   3            2

*В первом примере:

1 * 2 = 2
2 * 2 = 4
4 + 1 = 5
5 * 2 = 10
10 + 1 = 11 #  5 ходов

*Во втором примере:

1 * 2 = 2
2 + 1 = 3 #  2 хода
2
  • 1
    Начинать нужно с n и двигаться к 1, предпочитая деление вычитанию
    – extrn
    11 ноя 2019 в 19:56
  • 2
    Учесть что выводить порядок не надо. То число единичных бит в числе плюс число всех разрядов числа минус два) я думаю есть встроенные функции для этого.
    – pavel
    11 ноя 2019 в 21:04

1 ответ 1

1
n = 11

counter = 0
while n > 1:
    if n & 0x1 == 0:
        n //= 2
    else:
        n -= 1
    counter += 1

print(counter)  # 5

Можно с выводом всех вычислений:

n = 10
a = 1
stack = []

counter = 0
while n > a:
    if n & 0x1 == 0:
        n //= 2
        stack.append(2)
    else:
        n -= 1
        stack.append(1)
    counter += 1

print(counter)

while stack:
    operator = stack.pop()
    if operator == 2:
        print('{0:d} * 2 = {1:d}'.format(a, a * 2))
        a *= 2
    else:
        print('{0:d} + 1 = {1:d}'.format(a, a + 1))
        a += 1

# 4
# 1 * 2 = 2
# 2 * 2 = 4
# 4 + 1 = 5
# 5 * 2 = 10

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.