1

我需要一些帮助将这个伪代码翻译成 python，我在代码中提出了一些问题，真的很想得到一些帮助:) 我理解的代码背后的想法，一种分而治之的二进制乘法技术。

在此处输入图像描述

你们怎么会用python写这个？

def mult(A,B):

        n = len(A)
        if (n <= 1):
            return (A[0]*B[0])

        p = A[0:n/2]
        q = A[n/2:n]
        r = B[0:n/2]
        s = B[n/2:n]

        pr = mult(p,r)
        ps = mult(p,s)
        rq = mult(r,q)
        qs = mult(q,s)

        sum = ps + rq # no problem adding like this I guess

?

好吧，我不知道这个“in”在伪代码中的作用以及“end”。而我想这只是使用“<<”运算符的转变。或者在这种情况下可能不是，因为它是一个列表，但是为此创建一个帮助功能很简单。

4

1 回答 1

3

首先，我认为这根本不是伪代码，而是用真实语言编写的代码，可能是从 (S)ML 派生的。如果您知道它是什么语言，那么解释它会容易得多——而不是试图猜测诸如shift含义之类的东西，您可以在该语言的文档中查找它。

话虽这么说，有很多东西你已经清楚地翻译错了。

首先，你打开了这个：

if |A| ≤ 1

……进入这个：

n = len(A)
if (n == 1):

除了添加无意义的额外括号外，您还打破了 A 为empty的递归基本情况。

接下来，par可能只是表示“如果您愿意，您可以并行执行这些操作”，因此可以忽略它。另一方面，鉴于您是从并行算法和数据结构课程的讲义中获取的，您忽略的那件事可能就是重点。显然，在 Python 中，您需要将其映射到不同的东西——例如，创建一个concurrent.futures.ProcessPoolExecutor，提交四个递归调用，然后等待所有四个期货？（尽管这可能是一种可能的后期绑定语言，在这种情况下，您不想在这里等待期货，而是更改使用这些值之一的每个表达式，以便它等待它需要的未来，并将这些表达式也提交给执行者。）

无论如何，您已经将对正在定义的函数的递归调用转换为对某些不同函数的调用。所有这些：

    pr = binary_mult(p,r)
    ps = binary_mult(p,s)
    rq = binary_mult(r,q)
    qs = binary_mult(q,s)

……需要打电话mult。

这let … in … end实际上是一种说法，即第一个……是第二个……的一堆局部变量。例如，您可以end通过在每个变量上用 a替换它来翻译它del，但我认为您可以忽略它。

但是你忽略了最重要的部分，这一点：

shift(pr, n) + shift(sum, n/2) + qs

我不确定最后一个+是+. 它可能是一个不同的符号，或者是光标在 上移动时截取的屏幕截图+，或者是打印输出的扫描件，上面有一点灰尘+，或者其他一些很好的例子，说明为什么你应该发布文本而不是文本图片您需要有关该文本中代码的帮助...</p>

无论如何，您需要做任何正在做的事情（并返回结果）。这是功能的关键部分；所有的let … in东西都是为这个表达式设置的。

根据您对函数含义的猜测，以及我对几乎 SML 语法的猜测，忽略并行位，类似于您所写的内容接近于直接翻译：

def shift(A, n):
    # Taking a wild guess
    return A + [0 for _ in range(n)]

def mult(A, B):
    n = len(A)
    if n <= 1:
        return [A[0] * B[0]]
    else:
        p, q = A[:n//2], A[n//2:]
        r, s = B[:n//2], B[n//2:]
        pr, ps, rq, qs = mult(p, r), mult(p, s), mult(r, q), mult(q, s)
        sum = ps + rq
        return pr << n + sum << n//2 + qs

我敢打赌，我们至少猜错了一件事。例如，可能+应该是按元素添加而不是列表连接。找出答案的唯一方法是用一些数字运行它并检查输出。唯一的问题是，我什至不知道输入应该是什么。也许二进制数字的大端位值列表？在这种情况下，+必须使用进位进行元素添加。

事实上，这些东西可能应该同时用作数字和大端位列表。没有内置的 Python 类型可以这样工作，但是构建一个……或者在 PyPI 上找到一个并不难。bitarray看起来像是合理bitstring的候选人。

于 2013-11-13T01:27:49.920 回答