以 1 和 2 的形式为整数查找二进制的算法
Algorithm to find the Binary in Terms of 1 and 2 for an Integer
问题
在开发虚拟确定性有限自动机时，我试图创建一种算法，从十进制值输出唯一的二进制字符串。二进制的十进制值是通过将 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
Rory Daulton 在这方面帮助了我很多，下面是他的解决方案和测试的实现 运行。但是，它失败了几个整数。
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]))
提前致谢！
您的问题接近于找到数字的标准 (0/1) 二进制表示形式，所以让我们直接使用它。这是一个算法--我把代码留给你。
首先，考虑比 2 的幂小 1 的数字。这是序列 1、3、7、15、31 等——您可以通过将前一个数字相乘并相加来找到下一个数字一。找到此序列中小于或等于给定数字的最大数字。对于 19 的示例，即 15。请注意您的号码在序列中的位置。在您的示例中，15 是序列中的第 4 个数字，因此请记住 4。
然后从给定的数字中减去该数字。这里我们得到 19 - 15 即 4.
将计算出的数字转换为标准二进制——有多种 well-known 方法可以做到这一点，这在 Python 中是微不足道的。在第一步中用任何需要的零作为前缀，以获得与其他数字（序列中的位置）相同的位数。这里我们得到 100，我们需要 4 个二进制数字，所以我们得到 0100。
最后，将该二进制文件中的每个 1 替换为 2，将每个 0 替换为 1。这里我们得到 1211，这是我们想要的结果。
该算法的工作原理基本上是注意从您想要的表示形式中的每个数字中减去 1 会得到一个标准的二进制数，该数字以简单的方式与给定的数字不同。
我的算法中的一个特例是当给定数字小于 2 的幂时，因此其标准二进制表示中没有零。因此它的标准二进制也是它的特殊二进制，我们最终只使用它的标准二进制表示。在我的算法中，我们将给定数字更改为零，得到一串零，然后将其转换为一串 1，这是正确的。 （此答案经过编辑以处理这种特殊情况。）
我想到了一个更简单的解决方案。
代码
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（即dmod2等于0）。否则，令整数 m 为 1。将 m 连接到 b 的开头 (b = mb)。然后，用b减去m并除以2。当b大于0时，重复上述步骤。
示例：
dec = 11
11 = ___ * 2 + ___ becomes:
11 = 5 * 2 + 1 <- LSB
5 = 2 * 2 + 1
2 = 0 * 2 + 2 <- MSB
bin = 211
问题
在开发虚拟确定性有限自动机时，我试图创建一种算法，从十进制值输出唯一的二进制字符串。二进制的十进制值是通过将 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
Rory Daulton 在这方面帮助了我很多，下面是他的解决方案和测试的实现 运行。但是，它失败了几个整数。
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]))
提前致谢！
您的问题接近于找到数字的标准 (0/1) 二进制表示形式，所以让我们直接使用它。这是一个算法--我把代码留给你。
首先，考虑比 2 的幂小 1 的数字。这是序列 1、3、7、15、31 等——您可以通过将前一个数字相乘并相加来找到下一个数字一。找到此序列中小于或等于给定数字的最大数字。对于 19 的示例，即 15。请注意您的号码在序列中的位置。在您的示例中，15 是序列中的第 4 个数字，因此请记住 4。
然后从给定的数字中减去该数字。这里我们得到 19 - 15 即 4.
将计算出的数字转换为标准二进制——有多种 well-known 方法可以做到这一点，这在 Python 中是微不足道的。在第一步中用任何需要的零作为前缀，以获得与其他数字（序列中的位置）相同的位数。这里我们得到 100，我们需要 4 个二进制数字，所以我们得到 0100。
最后，将该二进制文件中的每个 1 替换为 2，将每个 0 替换为 1。这里我们得到 1211，这是我们想要的结果。
该算法的工作原理基本上是注意从您想要的表示形式中的每个数字中减去 1 会得到一个标准的二进制数，该数字以简单的方式与给定的数字不同。
我的算法中的一个特例是当给定数字小于 2 的幂时，因此其标准二进制表示中没有零。因此它的标准二进制也是它的特殊二进制，我们最终只使用它的标准二进制表示。在我的算法中，我们将给定数字更改为零，得到一串零，然后将其转换为一串 1，这是正确的。 （此答案经过编辑以处理这种特殊情况。）
我想到了一个更简单的解决方案。
代码
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（即dmod2等于0）。否则，令整数 m 为 1。将 m 连接到 b 的开头 (b = mb)。然后，用b减去m并除以2。当b大于0时，重复上述步骤。
示例：
dec = 11
11 = ___ * 2 + ___ becomes:
11 = 5 * 2 + 1 <- LSB
5 = 2 * 2 + 1
2 = 0 * 2 + 2 <- MSB
bin = 211