乘法中的进位数如何计算？

Question

在使用Python2进行乘法运算时，我无法计算进位数。我试图调整一个程序，我已经做了计数携带任何加法问题，但我似乎仍然无法使它工作。我目前正在学习Python的基础知识，所以我使用的是非常简单的东西。任何关于如何将此程序转换为应用于乘法的建议都将不胜感激！在

以下是我的加法程序计数：

if len(str(x)) != len(str(y)):
    if len(x) > len(y):
        while len(x) > len(y):
            y = '0' + y
    else:
        while len(y) > len(x):
            x = '0' + x
z = int(x) + int(y)
counter = 0
carries = 0
i = len(str(x))

while i > 1:
    i -= 1
    added = int((x[i])) + int((y[i])) + counter

    if added > 9:
        carries +=1
        counter = 1
    else:
        counter = 0

print str(x), '+', str(y), '=', z
print 'Number of carries: ', str(carries)

Answer 1

我做了与@techguy相同的假设，尽管我处理问题的方式不同。我选择使用递归方法而不是迭代方法，因为对于这类问题来说，这更自然。在

如果我们正在计算加法阶段发生的进位，那么我们需要将用于计数加法进位的逻辑封装在一个方法中，如下所示：

def count_addition_carries_rec(nums, answer=0, carries=0):

    dig_count = max(len(str(nums[0])), len(str(answer)))
    carries_list = [0]
    new_answer = ''
    # convert to string, apply left-padding, and reverse
    rnums = [str(x).zfill(dig_count)[::-1] for x in [nums[0], answer]]

    for i in range(dig_count):
        dig_sum = str(sum([int(num[i]) for num in rnums]) + carries_list[i])
        if i < dig_count - 1:
            new_answer = dig_sum[-1] + new_answer
            carries_list.append(int(dig_sum[:-1].zfill(1)))
        else:
            new_answer = dig_sum + new_answer

    carries_list = [car for car in carries_list if car != 0]

    if len(nums) == 1:
        # If this is the last number in the list, 
        # return the answer and the number of carries that 
        # occurred in the current as well as previous operations.
        return int(new_answer), carries + len(carries_list)
    else:
        # if there are more numbers in the list,
        # repeat the operation with a sublist, consisting of the next
        # number onwards, passing the current sum (new_answer) and 
        # the current count of carries 
        return count_addition_carries_rec(nums[1:],
                                          new_answer,
                                          carries + len(carries_list))

count_addition_carries_rec方法是通用的，因为它可以接受2个以上的整数。nums参数是一个列表，该方法期望它的长度为2或更长。在

计算乘法进位的方法如下：

^{pr2}$

count_multiplication_carries_rec不像加法方法那样通用，但是可以很容易地修复它。您可以创建一个一次用2个数字调用count_multiplication_carries_rec的辅助方法，也可以修改当前实现以处理任意数量的整数。在

使用这两种方法的示例：

>>> count_addition_carries_rec([99,99])
(198, 1)

>>> count_addition_carries_rec([17, 17, 17])
(51, 2)

>>> count_multiplication_carries_rec(15,15)
(225, 2)

>>> count_multiplication_carries_rec(657,34)
(223380, 6)

如您所见，这些方法返回加法/乘法运算的结果以及执行该操作时发生的进位数。在

Answer 2

我假设，通过进位的次数，你想知道一次进位发生了多少次，而不是进位总数。例如，34×48的第一步有一个乘法进位（当4和8相乘时携带3），即使总进位值等于3。在

另外，我假设你还想知道做乘法运算时发生的加法进位数。继续我们的例子，当我们乘以34*40时，我们有一个乘法进位（4*4）。我们现在需要添加两个结果（272和1360）。这将导致一个额外的进位，进位操作的总数等于3。在

基本上，我计算总进位数，不包括超过最大数的进位。这意味着90*9没有任何进位。同样，90+99也不会有任何进位。我是根据你的加法运算方式决定的。如果您不希望发生这种情况，并且希望包含最后一位的进位，只需按照**** ... ****注释中所述的代码更改进行操作。在

代码如下。我包含了我自己的计算加法进位的实现。它应该在功能上等同于您发布的代码。在

def num_add_carries(x, y):
    """
    Return a count of the number of addition carries.

    @param x: A number to add, as an integer.

    @param y: A number to add, as an integer.

    @return: The total number of carry operations.
    """

    # Determine which number is the larger one
    if y <= x:
        min_num = y; max_num = x
    else:
        min_num = x; max_num = y

    # Initialize some parameters
    num_carries = 0
    smin = str(min_num); smin_length = len(smin)
    smax = str(max_num); smax_length = len(smax)

    # Determine the end looping parameter
    #   **** Set to '-1' to include the end carry ****
    end_ix = -1 if smin_length != smax_length else 0

    # Iteratively perform the multiplication, counting the mult carries
    for i, ix in enumerate(xrange(smin_length - 1, end_ix, -1), 1):
        if int(smax[-i]) + int(smin[ix]) > 9:
            num_carries += 1

    return num_carries

def num_mult_carries(x, y):
    """
    Return a count of the total number of multiplication carries, including
    all necessary addition carries.

    @param x: A number to add, as an integer.

    @param y: A number to add, as an integer.

    @return: The total number of carry operations.
    """

    # Determine which number is the larger one
    if y <= x:
        min_num = y ; max_num = x
    else:
        min_num = x; max_num = y

    # Initialize some parameters
    num_carries = 0; adds = [] # List of numbers to add
    smin = str(min_num); smin_length = len(smin)
    smax = str(max_num); smax_length = len(smax)

    # Iteratively perform the multiplication, counting the mult carries
    for i, ix in enumerate(xrange(smin_length - 1, -1, -1)):
        # Perform Multiplication (used for summing, later)
        adds.append(max_num * int(smin[ix]) * (10 ** i))

        # Determine number of multiplication carries
        #   **** Change the '0' to '-1' to include the end carry **** 
        for ix2 in xrange(smax_length - 1, 0, -1):
            if int(smax[ix2]) * int(smin[ix]) > 9:
                num_carries += 1

    # Iteratively perform the addition, counting the addition carries
    s = 0
    while len(adds) > 1:
        s += adds.pop(0)
        num_carries += num_add_carries(s, adds[0])

    return num_carries

print num_add_carries(99, 99)
print num_mult_carries(657, 34)

上述代码的输出为：

^{pr2}$