Как ускорить работу кода?

Question

Ниже на пяти языках записан алгоритм. Получив на вход число 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)

Answer 1

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

Answer 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 итераций), так что там должна стоять единица. А остальные единицы должны стоять справа, чтобы число было наименьшим.

БЛОГ НА HUSL

Как ускорить работу кода?

Ответы (2 шт):