Python 使用 "Elementary School" 算法添加二进制数

Question

我必须编写一个代码，接受两个输入二进制数（作为字符串）并使用 "elementary school" 算法将它们相加。这是代码输入和输出的样子：

>>>addBinary("11","1")
'100'

我试过自己写一些代码，但我卡住了：

def addBinary(s,t, b = 0):
    if '' == s or '' == t:
        return s + t
    if 1 == len(s) or 1 == len(s):    
        if 0 == b:
            if (0 == s[-1] and 1 == t[-1]) or (1 == s[-1]and 0 == t[-1]):
                return addBinary(s[:-1],t[:-1]) + '1'
            elif 0 == s[-1] and 0 == t[-1]:
                return addBinary(s[:-1],t[:-1]) + '0'
            else:
                return addBinary(s[:-1],t[:-1],1) + '0'
        else:
            if (0 == s[-1] and 1 == t[-1]) or (1 == s[-1]and 0 == t[-1]):
                return addBinary(s[:-1],t[:-1],1) + '0'
            elif 0 == s[-1] and 0 == t[-1]:
                return addBinary(s[:-1],t[:-1]) + '1'
            else:
                return addBinary(s[:-1],t[:-1],1) + '0'

当我只剩下字符串中的 1 个元素时，我遇到了麻烦。我在创建基本案例时遇到问题

PS：这段代码我必须使用递归。我不允许使用循环。

Answer 1

作为旁注，最后两行应该是：

    else:
        return addBinary(s[:-1],t[:-1],1) + '1'

当长度为 1 时，您不应该做任何不同的事情。当其中一个长度为零时，您应该做一些不同的事情，在这种情况下您需要正确处理进位。当 b 为 1 时，return s + t 不正确。

Answer 2

一些问题：

只有 return s + t 当 b = 0 时，否则 returned 值将不正确。
当其中一个字符串只有一个数字时，不需要特殊情况。
然而，有必要处理其中一个字符串为空并且根据第一条规则无法使用s + t退出的情况。
可以避免多次重复几乎相同的代码

有多种方法可以做到这一点，但这里是一种方法：

def addBinary(s, t, carry = 0):
    if ('' == s or '' == t) and carry == 0:
        return s + t
    digit = carry
    carry = 0
    if s != '' and s[-1] == '1':
        carry = digit
        digit = 1 - digit
    if t != '' and t[-1] == '1': 
        carry += digit
        digit = 1 - digit
    return addBinary(s[:-1], t[:-1], carry) + str(digit)

请注意，digit = 1 - digit 只是一种将 1 翻转为 0 以及将 0 翻转为 1 的方法。

Answer 3

def add_binary(A:str,B:str)->str:
    result=[]
    carry=0
    i,j=len(A)-1,len(B)-1 # find the max index of strings
    while i>0 or j>0 or carry:
        total=carry # total is initially "carry" then we add values
        if i>=0:
            total+=int(A[i]) # convert the str to int, then add to "total"
            i-=1
        if j>=0:
            total+=int(B[j]) # same as above total operation
            j-=1
        result.append(str(total%2)) # if total=2, we write 0, if total=1, it is 1, if 0 it is 0
        carry=total//2 # if total=2 carry=1, otherwise carry=0
    # so far this is the first iteration
    return ''.join(reversed(result))

我们这样做 reversed(result) 因为“010101010”，我们从末尾开始求和，并将其推入数组。所以二进制数字的最后一个元素被求和并作为数组的第一个元素被推入。这就是我们反转它的原因。

Python 使用 "Elementary School" 算法添加二进制数

Python Adding Binary Numbers Using "Elementary School" Algorithm

python

binary

recursion

add