0

Ниже на пяти языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 3. Допускается диапазон значений для величин целого типа: от −2^31 до 2^31 — 1.

чтобы решить задачу изменил код и сделал перебор каждого значения, но их слишком большой диапазон

как ускорить?

for x in range(-2**31,2**31-1):
    i=x
    a = 0
    b = 0
    while x > 0:
        с = x % 2
        if c == 0:
            a += 1
        else:
            b += 1
        x //=  10
    if a == 2 and b==3:
        print(i)

2 ответа 2

2
while x > 0:

Сюда управление попадёт только при положительном x и только тогда изменятся a и b. Зачем тогда перебирать отрицательные значения x, если от этого ничего не зависит? Диапазон перебора можно начать хотя бы с 0:

for x in range(2**31-1):

Далее у вас в этой строке буква с - русская, поэтому в следующей строке будет ошибка - там буква c - английская и интерпретатор считает, что этой переменной ничего не присвоено, это ведь разные переменные:

        с = x % 2
        if c == 0:

Исправьте обе переменные c на одинаковые и лучше если английские.

После этого ваш код моментально начинает находить подходящие значения.

Да, и чтобы прекратить перебор после первого найденного числа добавьте break:

    if a == 2 and b==3:
        print(i)
        break
3
  • Ещё можно не хило так ускорить перебор, если начинать не с нуля, а с 10**(a+b-1). Ведь искомое число должно содержать не менее a+b цифр.
    – GrAnd
    12 окт 2021 в 12:55
  • @GrAnd Да там нечего ускорять, в Google Colab за порядка 15 миллисекунд этот код отрабатывает и так уже )) Но вы молодец, что алгоритмически разобрались с задачей, мне лениво было.
    – CrazyElf
    12 окт 2021 в 12:57
  • Для данных конкретных a и b - да, пятизначное число найдётся быстро. Надо было задать поиск на все 10 разрядов. :)
    – GrAnd
    12 окт 2021 в 13:09
2

Вообще-то, если понять "алгоритм на пяти языках", то можно банально вывести обратную формулу и не морочиться с перебором.

Расчёт в виде числа:

print(10**(a+b-1) + sum(10**i for i in range(b-1)))

или строки:

print('1' + '0'*a + '1'*(b-1))

Ведь согласно алгоритму переменная a будет содержать количество нулей в числе (наименьшее чётное число оканчивается на 0). А b - количество единиц (наименьшее нечётное - 1).

Т.е. искомое число должно состоять только из нулей и единиц. И наименьшее значимое число из нужного количества цифр (2+3=5 в данном случае) будет - 10011. Нули слева быть не могут (иначе число "закончится" раньше чем за 5 итераций), так что там должна стоять единица. А остальные единицы должны стоять справа, чтобы число было наименьшим.

Ваш ответ

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

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