Алгоритм поиска двоичного числа с точки зрения 1 и 2 для целого числа

Проблема

При разработке виртуального детерминированного конечного автомата я пытаюсь создать алгоритм, который выводит уникальные двоичные строки из десятичных значений. Десятичное значение из двоичного кода находится путем умножения соответствующего возведения в степень 2 либо на 1, либо на 2. Например,

    19 becomes:
    1    2    1    1

С:

    2^3  2^2  2^1  2^0
    1    2    1    1
  * __________________
    8  + 8  + 2  + 1

Попытки

Попытка 1

Я пробовал разные алгоритмы, но этот подошёл ближе всего:

def decToBin2(dec):
    bin = ''
    while dec > 0:
        bin = str(dec % 2) + bin
        dec = dec/2
    return bin

Однако бинарные решения, использующие эту функцию, включают 0, чего не должно быть. Следовательно, я немного боролся.

Попытка 2

Рори Долтон очень помог мне с этим, и вот реализация его решения и тестовый прогон. Тем не менее, это не удается для нескольких целых чисел.

def decToBin2(dec):
    if dec == 0:
        return ''

    bin = ''
    # Find the largest power of 2 that is less than dec
    fac = 0
    while 2**(fac) <= dec:
        fac = fac + 1
    fac -= 1

    # Subtract that power of 2 and add 1
    dec = dec - 2**(fac) + 1

    # Convert to binary, but 0s become 1s and 1s become 2s
    while dec > 0:
        bin = str(dec % 2 + 1) + bin
        dec = dec/2

    # Pad the left side with 1s
    while len(bin) < fac:
        bin = '1' + bin

    return bin

Тестовый забег:

✓ 0 = 0 : 
✗ 1 != 2 : 2
✓ 2 = 2 : 2
✗ 3 != 5 : 21
✓ 4 = 4 : 12
✓ 5 = 5 : 21
✓ 6 = 6 : 22
✗ 7 != 11 : 211
✓ 8 = 8 : 112
✓ 9 = 9 : 121
✓ 10 = 10 : 122
✓ 11 = 11 : 211
✓ 12 = 12 : 212
✓ 13 = 13 : 221
✓ 14 = 14 : 222
✗ 15 != 23 : 2111
✓ 16 = 16 : 1112
✓ 17 = 17 : 1121
✓ 18 = 18 : 1122
✓ 19 = 19 : 1211
✓ 20 = 20 : 1212
✓ 21 = 21 : 1221
✓ 22 = 22 : 1222
✓ 23 = 23 : 2111
✓ 24 = 24 : 2112
✓ 25 = 25 : 2121
✓ 26 = 26 : 2122
✓ 27 = 27 : 2211
✓ 28 = 28 : 2212
✓ 29 = 29 : 2221
✓ 30 = 30 : 2222
✗ 31 != 47 : 21111
✓ 32 = 32 : 11112
✓ 33 = 33 : 11121
✓ 34 = 34 : 11122
✓ 35 = 35 : 11211
✓ 36 = 36 : 11212
✓ 37 = 37 : 11221
✓ 38 = 38 : 11222
✓ 39 = 39 : 12111
✓ 40 = 40 : 12112
✓ 41 = 41 : 12121
✓ 42 = 42 : 12122
✓ 43 = 43 : 12211
✓ 44 = 44 : 12212
✓ 45 = 45 : 12221
✓ 46 = 46 : 12222
✓ 47 = 47 : 21111
✓ 48 = 48 : 21112
✓ 49 = 49 : 21121
✓ 50 = 50 : 21122
✓ 51 = 51 : 21211
✓ 52 = 52 : 21212
✓ 53 = 53 : 21221
✓ 54 = 54 : 21222
✓ 55 = 55 : 22111
✓ 56 = 56 : 22112
✓ 57 = 57 : 22121
✓ 58 = 58 : 22122
✓ 59 = 59 : 22211
✓ 60 = 60 : 22212
✓ 61 = 61 : 22221
✓ 62 = 62 : 22222
✗ 63 != 95 : 211111
✓ 64 = 64 : 111112
✓ 65 = 65 : 111121
✓ 66 = 66 : 111122
✓ 67 = 67 : 111211
✓ 68 = 68 : 111212
✓ 69 = 69 : 111221
✓ 70 = 70 : 111222
✓ 71 = 71 : 112111
✓ 72 = 72 : 112112
✓ 73 = 73 : 112121
✓ 74 = 74 : 112122
✓ 75 = 75 : 112211
✓ 76 = 76 : 112212
✓ 77 = 77 : 112221
✓ 78 = 78 : 112222
✓ 79 = 79 : 121111
✓ 80 = 80 : 121112
✓ 81 = 81 : 121121
✓ 82 = 82 : 121122
✓ 83 = 83 : 121211
✓ 84 = 84 : 121212
✓ 85 = 85 : 121221
✓ 86 = 86 : 121222
✓ 87 = 87 : 122111
✓ 88 = 88 : 122112
✓ 89 = 89 : 122121
✓ 90 = 90 : 122122
✓ 91 = 91 : 122211
✓ 92 = 92 : 122212
✓ 93 = 93 : 122221
✓ 94 = 94 : 122222
✓ 95 = 95 : 211111
✓ 96 = 96 : 211112
✓ 97 = 97 : 211121
✓ 98 = 98 : 211122
✓ 99 = 99 : 211211
✓ 100 = 100 : 211212

Полезный фрагмент

Чтобы проверить свою функцию решения, вы можете ввести свою двоичную строку в эту функцию, которую я написал, которая умножает каждое возведение в степень 2 на его вес.

def binToDec(bin):
    if bin == '':
        return 0
    return binToDec(bin[1:]) + (2**(len(bin) - 1) * int(bin[0]))

Заранее спасибо!


binary algorithm math automata
person Anthony Krivonos    schedule 05.04.2018    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Ваша проблема близка к поиску стандартного (0/1) двоичного представления числа, поэтому давайте просто воспользуемся этим. Вот алгоритм - я оставлю код вам.

Во-первых, рассмотрите числа, которые на единицу меньше степени 2. Это последовательность 1, 3, 7, 15, 31 и т. д. — вы найдете следующее число, умножив предыдущее число и прибавив единицу. Найдите наибольшее число в этой последовательности, которое меньше или равно заданному числу. Для вашего примера 19 это 15. Обратите внимание на положение вашего числа в последовательности. В вашем примере 15 — это 4-е число в последовательности, поэтому запомните 4.

Затем вычтите это число из заданного числа. Здесь мы получаем 19 - 15, что равно 4.

Преобразуйте это рассчитанное число в стандартный двоичный формат — для этого есть несколько хорошо известных способов, и в Python это тривиально. Добавьте к этому префикс с любыми необходимыми нулями, чтобы получить то же количество цифр, что и другое число (позиция в последовательности) на первом шаге. Здесь мы получаем 100, и нам нужны 4 двоичные цифры, поэтому мы получаем 0100.

Наконец, замените каждую 1 в этом двоичном файле на 2 и каждый 0 на 1. Здесь мы получаем 1211, что и является желаемым результатом.

Этот алгоритм в основном работает, отмечая, что вычитание 1 из каждой цифры в желаемом представлении приводит к стандартному двоичному числу, которое отличается от заданного числа простым способом.

Особый случай в моем алгоритме — это когда заданное число на единицу меньше степени двойки, поэтому в его стандартном двоичном представлении нет нулей. Таким образом, его стандартный двоичный файл также является его специальным двоичным файлом, и в итоге мы просто используем его стандартное двоичное представление. В моем алгоритме мы меняем заданное число на ноль, получаем строку нулей, а затем преобразуем ее в строку единиц, что правильно. (Этот ответ был отредактирован для обработки этого особого случая.)

person Rory Daulton    schedule 05.04.2018
comment
Спасибо за решение, Рори! Я попытался реализовать ваш алгоритм, и он работает... в большинстве случаев (я отредактировал свой вопрос). Есть что-то, что мне не хватает? - person Anthony Krivonos; 05.04.2018
comment
Неудачные случаи возникают, когда длина двоичной строки увеличивается, и в качестве старшего разряда выводится 2 вместо 1. - person Anthony Krivonos; 05.04.2018
comment
Спасибо! Я пришел к решению, которое скоро опубликую. И последнее: не могли бы вы объяснить в математических терминах строку Then subtract that number from your given number. Here we get 19 - 15 which is 4.? Почему вы делаете это, чтобы получить новый взвешенный двоичный файл? - person Anthony Krivonos; 05.04.2018
comment
@AnthonyKrivonos Логика следующая: мы пытаемся свести вашу проблему к хорошо известной проблеме преобразования числа в двоичную форму. Для этого давайте разделим последовательность 1 и 2 общей длины L, которая представляет число N, на сумму двух чисел: A1 = последовательность только 1 длины L и последовательность 0 и 1, которая, по-видимому, является просто двоичное представление некоторого числа (B). А первый просто 2^L-1. Итак, B = N - A1 и мы знаем, как его преобразовать. Осталось только найти L, получить и преобразовать B и добавить A1, то есть добавить 1 в каждой позиции. - person SergGr; 05.04.2018
comment
@AnthonyKrivonos: Ваш взвешенный двоичный файл состоит из единиц и двоек. Если мы вычтем 1 из каждой цифры, мы получим число, состоящее из нулей и единиц, которое является обычным двоичным числом и которое мы знаем, как это сделать. Таким образом, мы вычли число 1111 (или другую длину) из заданного числа. Это число 1111 в двоичном формате на единицу меньше, чем степень числа 2. Вы можете увидеть это, добавив к нему единицу: вы получите все нули, кроме нового бита переполнения — получите 10000. Этот вид числа является степенью двойки, в данном конкретном случае 2**4. Это ясно? - person Rory Daulton; 05.04.2018
comment
@AnthonyKrivonos: Последовательность в моем первом шаге — это все те двоичные числа, состоящие только из единиц: 0b1 = 1 = 2**1-1, 0b11 = 3 = 2**2-1, 0b111 = 7 = 2**3-1, 0b1111 = 15 = 2**4-1 и т. д. - person Rory Daulton; 05.04.2018
comment
Большое спасибо за объяснение! Все это имеет смысл с вашим методом. Однако я только что придумал решение, которое намного легче и столь же эффективно. Пожалуйста, проверьте это. - person Anthony Krivonos; 05.04.2018

arrow_upward
1
arrow_downward

Я придумал гораздо более простое решение.

Код

def decToBin2(dec):
    bin = ''
    while dec > 0:
        summand = 2 if dec % 2 == 0 else 1
        bin = str(summand) + bin
        dec = (dec - summand)/2
    return bin

Объяснение:

Предположим, что целое число d должно быть преобразовано в двоичное представление и пустая строка b. Если d четно, пусть целое число m равно 2 (то есть d mod 2 равно 0). В противном случае пусть целое число m равно 1. Соедините m с началом b (b = mb). Затем вычтите m из b и разделите это решение на 2. Повторяйте вышеупомянутые шаги, пока b больше 0.

Пример:

dec = 11
11 = ___ * 2 + ___ becomes:
11 = 5 * 2 + 1 <- LSB
5 = 2 * 2 + 1
2 = 0 * 2 + 2 <- MSB
bin = 211
person Anthony Krivonos    schedule 05.04.2018
comment
Если вы подумаете об этом, вы можете заметить, что логически ваше решение такое же, как у @RoryDaulton. Вы только что объединили две (три) петли в одну. В решении Рори первый цикл используется для расчета мощности, второй — для преобразования, а основной линией в этом цикле является summand = dec % 2, что логически совпадает с summand = 1 if dec % 2 == 1 else 0, а третий цикл используется для добавления обратно 1. Если вы попытаетесь объединить вторую и третью петли, вы получите summand = (1 if (dec - 1) % 2 == 1 else 0) + 1, что логически эквивалентно вашей строке. И теперь вам не нужен первый цикл. - person SergGr; 05.04.2018
comment
Но, конечно, несмотря на то, что он логически эквивалентен, ваш код ИМХО намного проще, чем код для оригинального решения Рори. Я бы, вероятно, пометил этот ответ как принятый, даже если он ваш (да, это разрешено в SO). - person SergGr; 05.04.2018