这个 Python 加法算法的实现有什么问题？

Question

我已经开始在 Coursera 上关注斯坦福的 CS161，"an online course on Algorithms and Data Structures."

我查找了有关整数运算的小学算法。

我有伪代码的加法算法，有兴趣在 Python 2.7（根据 MIT 标准）中实现它。

我分析了我的实现并认为它几乎是正确的，但是 Python 解释器提供了一些可能关于未初始化列表和变量的反馈。

注意我对Python还不是很精通，由于对基本数据结构和代码结构缺乏了解，可能会有一些明显的句法错误.

我对下面的代码有几个问题：

def add(a,b):
    i = 0
    carry = 0
    x[i] = [None]*N
    y[i] = [None]*N
    while x[i] > 0 and y[i] > 0:
        x[i], y[i] = a%10, b%10
        a , b = a/pow(10,i+1), b/pow(10,i+1)
        N += i
    for i in range(N):
        x[i] = x[N-i]
        y[i] = y[N-i]
        r[i] = (x[i] + y[i] + carry)%10
        carry = (x[i] + y[i] + carry)/10
    r[N] = carry
    return r

算法说明：

add()函数以两个N位整数a和b作为输入，returns是一个N或N+1位整数对应于a和b.

它首先将a和b分成大小为N的列表，通过从中提取每个数字来保存和存储a（分别为b）的N个数字10 的最大幂数的最小幂数。

然后将所有 x[i] 替换为 x[N-i]（分别将 y[i] 替换为 y[N-i]），然后通过处理加法的进位来计算 x[i]+y[i]在每次迭代中。

进位按值动态递增。当for循环结束时，我们将和的最新位r[N]赋值作为进位值(>=0).

问题：

初始化列表 x[i] 和 y[i] 通过将其元素的值分配为 [None] N 次是一件好事吗？
在 x[i] 和 y[i] 这样初始化的情况下，while 循环是否应该再次工作，因为我的条件是 x[i] 和 y[i]？
如何return一个完整的列表即列表r[N]？我们应该输入 return r[N] 还是只输入 return r？

欢迎其他有用的贡献和评论。

Answer 1

是的，这很好，具体取决于上下文。您可以做得更好：x = [None for _ in xrange(N)]，但性能非常相似，这不太重要 - 可读性才是最重要的。
如果 0 是合法值，我会执行 x[i] is None 以查看该值是否为 none。否则，我只是做 x[i] 检查我是否不是 None 也不是 0 或 False.
return r

看下面的代码。我修复了 add()，包括越界索引和算法问题。然后实现了 addSimplified() ，它在没有额外的辅助数组的情况下做同样的事情。

def add(a, b):

    N = max(len(str(a)), len(str(b)))
    carry = 0

    x = [None] * N
    y = [None] * N
    r = [None] * (N + 1)

    for i in xrange(N):
        x[i], y[i] = a % 10, b % 10
        a, b = a / 10, b / 10

    for i in xrange(N):
        r[i] = (x[i] + y[i] + carry) % 10
        carry = (x[i] + y[i] + carry) / 10
    r[N] = carry

    return r


def addSimplified(a, b):

    N = max(len(str(a)), len(str(b))) + 1
    carry = 0

    r = [0] * N

    for i in xrange(N):
        step = (a / pow(10, i) % 10)  + (b / pow(10, i) % 10) + carry
        r[i] = step % 10
        carry = step / 10

    return r

print add(100, 20), addSimplified(100, 20)
print add(166, 66), addSimplified(166, 66)
print add(1920606,  9500666), addSimplified(1920606,  9500666)

这个 Python 加法算法的实现有什么问题？

What's wrong with this Python implementation of an addition algorithm?

python

algorithm

addition

python-2.7