2

如何设计一种算法来模拟加法乘法。输入两个整数。它们可能是零，正数或负数..

4

6 回答 6

10 
def multiply(a, b):                                                                                                                                                               
    if (a == 1):
        return b
    elif (a == 0):
        return 0
    elif (a < 0):
        return -multiply(-a, b)
    else:
        return b + multiply(a - 1, b)
于 2011-07-05T04:09:11.907 回答
1 
val:= 0
bothNegative:=false

if(input1 < 0) && if(input2 < 0)
  bothNegative=true
if(bothNegative)
  smaller_number:=absolute_value_of(smaller_number)
for [i:=absolute_value_of(bigger_number);i!=0;i--]
do val+=smaller_number

return val;
于 2011-07-05T04:15:15.507 回答
1

一些伪代码：

function multiply(x, y)
  if abs(x) = x and abs(y) = y or abs(x) <> x and abs(y) <> y then sign = 'plus'
  if abs(x) = x and abs(y) <> y or abs(x) <> x and abs(y) = y then sign = 'minus'

 res = 0
 for i = 0 to abs(y)
  res = res + abs(x)
 end

 if sign = 'plus' return res
    else return -1 * res

end function
于 2011-07-05T04:05:36.157 回答
0 
    mul(a,b)
    {
    sign1=sign2=1;
    if(a==0 || b==0)
return 0;
if(a<0){
    sign1=-1;
    a=-a;
    }
    if(b<0){
    sign2=-1;
    b=-b;
    }
    s=a;
    for(i=1;i<b;i++)
    s+=a;
    if(sign1==sign2)
    return s;
    else
    return -s;
    }
于 2014-05-07T14:49:12.223 回答
0

我来到这里是因为我正在寻找不使用*运算的乘法算法。我在这里看到的只是加或减数字 n 次。这是O(n)并且没关系，但是...

如果您有bitwise shift操作，您可以获得O(log n)乘法算法。

这是我的伪代码：

function mul(n, x)
    if n < 0 then   # 'n' cannot be negative
        n := -n
        x := -x
    endif

    y := 0
    while n != 0 do
        if n % 2 == 0 then
            x := x << 1     # x := x + x
            n := n >> 1     # n := n / 2
        else
            y := y + x
            x := x << 1     # x := x + x
            n := n - 1      # n := (n-1)/2
            n := n >> 1
        endif
    endwhile

    return y                # y = n * x
end

请记住，上面的函数 formul(1000000, 2)是 O(log 1000000)而 formul(2, 1000000)只是 O(log 2)。

当然，您会得到相同的结果，但请记住，函数调用中参数的顺序确实很重要。

编辑：使用的旁注n % 2

n % 2使用的实现bitwise shift

这很简单。首先除以n2，然后乘以n2 并检查是否n发生了变化。伪代码：

function is_even(n)
    n_original := n
    n := n >> 1        # n := n / 2
    n := n << 1        # n := n * 2
    if n = n_original then
        return true    # n is even
    else
        return false   # n is not even
    endif
end

n % 2使用的实现bitwise and

function is_even(n)
    if n and 1 = 0 then
        return true
    else
        return false
    endif
end
于 2020-01-09T16:38:44.990 回答
0

这对于整数如何：

int multiply(int a, int b)
{
    int product = 0;
    int i;
    if ( b > 0 )
    {
        for(i = 0; i < b ; i++)
        {
            product += a;
        }
    }
    else
    {
        for(i = 0; i > b ; i--)
        {
            product -= a;
        }
    }

    return product;
}
于 2017-09-25T07:28:52.117 回答