6

I need help with a program in python 3.3 that is supposed to do Russian peasant multiplication/ancient Egyptian multiplication. The assignment says," If "A" and "B" are the two integers to be multiplied, we repeatedly multiply "A" by 2 and divide "B" by 2, until "B" cannot divide any more and is not zero (integer division). During each set of multiplying "A" and dividing "B", if the value of "B" is an odd number, you add whatever the "A" value is to a total. At the end, the sum of all the "A" values (when "B" is odd) should be equal to the product of the original "A" and "B" inputs. In short, sum up all the "A" values for which "B" is odd and it will be equal (or close) to the product of "A" and "B".

edit

I may have phrased some of the question wrong.

Here is an example:

If "A" is 34, and "B" is 19, multiplying "A" by two and dividing "B" by two each line.

"A" "B"

(34) (19) ("B" is odd, add "A" to total)

(68) (9) ("B" is odd, add "A" to total)

(136) (4) ("B" is even, ignore "A" value)

(272) (2) ("B" is even, ignore "A" value)

(544) (1) ("B" is odd, add "A" to total)

When you sum all the values of "A" for which "B" is odd, you get (34 + 68 + 544 = 646), which is equal to just multiplying "A" and "B", (34 * 19 = 646).

The part I'm having trouble with is adding "A" to a total whenever "B" is an odd number.

This is what I have so far,

x = int(input("What is the first number? "))
y = int(input("What is the second number? "))
answer = 0

while y != 0:
    if (y%2 != 0):
        x*2
        y//2
        answer == answer + x
    if (y%2 == 0):
        x*2
        y//2
print("the product is",(answer))

I'm very new to python and programming, so any help and/or explanations of why its wrong would be greatly appreciated.

4

4 回答 4

3

我不熟悉您尝试实现的算法，但我对您的代码进行了一些修改。

x = int(input("What is the first number? "))
y = int(input("What is the second number? "))
answer = 0

# != 0 is redundant: y is True if it is not 0
while y:
    # no need to have parentheses here
    if y % 2:
        # this needs to be an assignment, not a check for equality
        answer += x  # shorthand for answer = answer + x
    # These happen every time, so does not need to be inside the if
    # these also need to be an assignment, not just an expression
    x *= 2
    y /= 2
# total was never defined
print("the product is", (answer))
于 2013-02-01T01:54:45.607 回答
3

您需要先添加 x 才能回答，然后更新 x

这是正确的代码

x = int(input("What is the first number? "))
y = int(input("What is the second number? "))
answer = 0

while y != 0:
   if (y%2 != 0):
      answer=answer+x
      x=x*2
      y=y//2
   if (y%2 == 0):
      x=x*2
      y=y//2

print("the product is",(answer))
于 2013-02-01T05:59:52.733 回答
0

上一次加 x 是在 y 等于 1 的时候。如果一直减半直到数字达到 0，将需要非常大量的迭代（从逻辑上讲，这将需要永远）。

想想 2x2。如果你将 x 加倍为 4，将 y 减半为 1，x 就是你的答案。

换句话说，认为y是how many of x I need to yield answer。由于您不能相乘，只能相加/加倍/减半，因此您可以选择 - 您可以等到 y 为 2，然后添加 x 的两倍值，或者您可以等到 y 为 1 并简单地添加 x 的值。后者更简单，更清晰，仅此而已。

我认为在这种情况下使用while True循环更清楚：

def mult2(x, y):
    answer = 0
    while True:
        if y % 2:
            answer += x
        if y < 1:
            break
        x *= 2
        y //= 2
    print("the product is", answer)

递归调用函数：

def mult2(x, y):
    """aka 'Russian peasant method'; allowed: addition, halving, doubling."""
    if y==1:
        return x
    else:
        add = x if y%2 else 0
        return mult2(x*2, y//2) + add
于 2014-10-18T16:58:11.890 回答
0

一个旁注。坦率地说，直到现在我才知道算法。它被古埃及人或旧俄罗斯使用的越让我感到惊讶。（实际上，我倾向于认为俄罗斯起源的可能性更大，因为斯拉夫民族似乎与古老的伊特鲁里亚人直接相关）。

旧的起源让我感到惊讶，因为它实际上是你在基础学校学到的简单的手工乘法。唯一的区别是数字首先转换为二进制表示。而是面向机器的，不是吗？:)

对于问题中的数字，十进制表示的 34 等于二进制的 100010，十进制的 19 是二进制的 10011。现在在纸上简单的基本学校乘法：

    100010
x    10011
------------
    100010   i.e. 100010 times 1
   100010        1000100 times 1
  000000        10001000 times 0
 000000        100010000 times 0
100010        1000100000 times 1
------------                   ^ binary digits of the multiplier
1010000110                       (reminder of division by 2)
                       ^ adding the zero means multiplying by 2
i.e. sum only when 1 is the reminder of division

似乎设计方法的人（在古代）知道二进制数是什么。

于 2013-02-02T11:56:28.920 回答