функция для подсчета шага, достигающего 0 - PullRequest
Новая
       14

функция для подсчета шага, достигающего 0

0 голосов
/ 26 апреля 2019

Мне нужно написать функцию для подсчета общего количества шагов, достигающих нуля.Правило:

  • деление числа на 2
  • , затем вычтите, например, на 1

, если у меня есть число 14

  • 14/2 = 7
  • 7-1 = 6
  • 6/2 = 3
  • 3-1 = 2
  • 2/2 = 1
  • 1-1 = 0

всего шагов 6

Обратите внимание, что входx - это двоичная строка: 

def test(x):
    a = int(x,2)
    steps = 0
    while a != 0:
        if a % 2 == 0:
            a = a // 2  
        else:
            a = a - 1
        steps += 1
    return steps

test("1000")
Out[65]: 4

test("101")
Out[66]: 4

test("001")
Out[67]: 1

test("0010010001")
Out[68]: 10

test("001001")
Out[69]: 5

что мне нужно знать, есть ли способ написать функцию, которая работает быстро?

Ответы [ 3 ]

1 голос
/ 26 апреля 2019

Предполагая, что ваш код правильный, и правило:

  • test (0) = 0
  • test (n) = 1 + test (n / 2), если n равночетный;
    1 + тест (n - 1) в противном случае

важно отметить следующее:

  • четное число заканчивается двоичным 0
  • деление на 2 удаляет 0 с конца (и ничего больше)
  • нечетное число заканчивается двоичным 1
  • вычитание 1 превращает последнюю 1 в 0 (и ничегоеще)

Таким образом, каждый 1 бит, кроме первого, добавляет 2 шага, а каждый значащий 0 бит добавляет 1 шаг.Это означает, что для входных данных, которые начинаются с 1, вы можете написать: 

def test(x):
    return x.count('1') + len(x) - 1

Теперь вам просто нужно учитывать ведущие нули или только конкретный случай "0", если начальные нули невозможны.

0 голосов
/ 26 апреля 2019

Вы также можете использовать рекурсивный подход: 

def stepsToZero(N):
    return N if N < 2 else 2 + stepsToZero(N//2-1)

Это даст вам результаты вплоть до N = 2 ** 993 (что довольно много) с очень лаконичной (и еще более элегантной) функцией.

Что будет работать намного быстрее, так это математическое решение

Например: 

import math
def steps2Zero(N):
    if N < 2: return N
    d = int(math.log(N+2,2))-1
    s = int(N >= 3*2**d-2)
    return 2*d+s

Обратите внимание, что для N = 2 ^ 900 математическое решение в сто раз быстрее, чем рекурсия. С другой стороны, рекурсивная функция реагирует намного меньше секунды и намного более читабельна. Таким образом, в зависимости от того, как это будет использоваться и какого размера, соображения производительности, скорее всего, бессмысленны

0 голосов
/ 26 апреля 2019

Ваш алгоритм не верен для нечетных чисел.Вы делите только тогда, когда число четное, что не соответствует описанию «шагов».

Вы хотите 

def test(x, 2):
x_int = int(x)
steps = 0
while x_int <= 0:
    x_int //= 2
    x -= 1
    steps += 1

Вы должны уточнить свой алгоритм, потому что способ, которым вы его описали, вы не гарантированно сходитесь к 0 для всех входов.То, как вы описали это бесконечный цикл для нечетных чисел.Просто попробуйте 1: 

#test(1)
1 // 2 = 0
0 - 1 = -1
...

Теперь вы никогда не доберетесь до 0, поэтому вам следует проверить x_int <= 0. </p>

Я предлагаю вам пересмотреть, почему вы все равно хотите это сделать,Я совершенно уверен, что вам даже не нужен итеративный алгоритм, чтобы знать, сколько «шагов» нужно, так или иначе, для этого должна быть математическая формула.

...