划分算法

Question

我刚刚开始设计分析和算法课程，我们已经从简单的算法开始。

有一个除法算法，我不能有任何意义。

功能划分（X，） 输入：2的整数x和y，其中y> = 1 输出：

if x=0: return (q,r)=(0,0) 
    (q,r)=divide(floor (x/2), y) 
    q=2q, r=2r 

    if x is odd: r=r+1 
    if r>=y: r=r-y, q=q+1 
    return(q,r) 

    * floor is lower bound 

我们本来商数和x的其余除以y尝试这算法110011％101（二进制值）...我尝试了一些东西，我有一个奇怪的答案...转换成十进制值，这是错误的。

所以我尝试使用简单的十进制值而不是二进制第一。

x=25, y=5 

This is what I'm doing 

1st: q=x,r= 12,5 
2nd: q=x,r= 6,5 
3rd: q=x,r= 3,5 
4th: q=x,r= 1,5 
5th: q=x,r= 0,5 

这个东西会如何工作？每次我都会运行它，最后x的最后一个值将是0（条件），它会停止并返回Q = 0，R = 0

有人能指导我，我要去哪里错了...

谢谢

Answer 1

该函数有一个递归结构，这可能是它为什么有点棘手。我假设您的函数声明中存在一个拼写错误，其中divide（x，）应该是divide（x，y）。鉴于希望的结果是剩余的x/y，让我们继续。函数定义中的第一行声明：如果分子为0，则返回0，余数为0.这是有道理的：对于所有整数，当b！= 0且a = 0时，a/b = 0。然后，我们将结果设置为递归调用，使用原分子的一半和当前分母。在某一点上，“原分子的一半”变为0，并达到基本情况。在每次递归调用结束时，似乎是尾递归的一些计算。因为我们在每次深度处除以2，乘以2得到原始结果，如果奇数则加1。单单在文本中很难形象化，所以要在纸上写下一个给定的问题。

在数学上，除法运算法则（它叫做那个）规定，当你输入25,5时，余数必须小于或等于5。

该算法给出0,5。这可能意味着当商数为0或需要检查余数的大小时不考虑余数。

function divide(x,) Input: 2 integers x and y where y>=1 Output: quotient and remainder of x divided by y 

    if x=0: return (q,r)=(0,0) 
    (q,r)=divide(floor (x/2), y) 
    q=2q, r=2r 

    if x is odd: r=r+1 
    if r>=y: r=r-y, q=q+1 
    return(q,r) 

    * floor is lower bound 

Answer 2

我实现你的算法（在ARG列表明显的校正）在Ruby中：

$ irb 
irb(main):001:0> def div(x,y) 
irb(main):002:1> return [0,0] if x == 0 
irb(main):003:1> q,r = div(x >> 1, y) 
irb(main):004:1> q *= 2 
irb(main):005:1> r *= 2 
irb(main):006:1> r += 1 if x & 1 == 1 
irb(main):007:1> if r >= y 
irb(main):008:2>  r -= y 
irb(main):009:2>  q += 1 
irb(main):010:2> end 
irb(main):011:1> [q,r] 
irb(main):012:1> end 
=> nil 
irb(main):013:0> div(25, 5) 
=> [5, 0] 
irb(main):014:0> div(25, 2) 
=> [12, 1] 
irb(main):015:0> div(144,12) 
=> [12, 0] 
irb(main):016:0> div(144,11) 
=> [13, 1] 

它的工作，所以你必须不能正确地跟踪递归，当你试图手工跟踪它。我发现将逻辑写出在每张递归调用的新纸上很有帮助，并将旧纸张放在一堆先前调用的顶部。当我在当前表单上得到一个return语句时，将其填入，将其扔掉，然后将返回值写入堆栈顶部的纸上，以代替递归调用。继续阅读本表中的逻辑，直到获得另一个递归调用或返回。不断重复此操作，直到您将纸张用完为止 - 最后一张纸的返回是最终答案。

Answer 3

如果我没有记错的话，这是在简单的ALU中进行积分分割的最基本的方法之一。这很好，因为您可以并行运行所有递归分区，因为每个分区都只基于查看二进制的一位。

要理解它的功能，只需在纸面上浏览一下，正如Chris Zhang所建议的那样。下面是divide(25,5)样子：

(x,y)=(25,5) 
    divide(12, 5) 
     divide(6,5) 
      divide(3,5) 
       divide(1,5) 
        divide(0,5) // x = 0! 
        return(0,0) 
       (q,r)=(2*0,2*0) 
       x is odd, so (q,r)=(0,1) 
       r < y 
       return(0,1) 
      (q,r)=(2*0,2*1) 
      x is odd, so (q,r)=(0,3) 
      r < y 
      return(0,3) 
     (q,r)=(2*0,2*3) 
     x is even 
     r >= y, so (q,r)=(1,1) 
     return(1,1) 
    (q,r)=(2*1,2*1) 
    x is even 
    r < y 
    return(2,2) 
(q,r)=(2*2,2*2) 
x is odd, so (q,r)=(4,5) 
r >= y, so (q,r)=(5,0) 
return(5,0) 

正如你所看到的，它的工作 - 它可以让你的5含水和0的R你注意到没有，那你永远终究有0项的部分是什么克里斯恰当地称呼“基本案例” - 使递归调用展开的情况。

该算法适用于除法和乘法的任何基数。它使用与以下相同的原理：“123/5 =（100 + 20 + 3）/ 5 = 20 + 4 + r3 = 24r3”，只是以二进制形式完成。