我刚开始学习设计分析和算法课程,我们从简单算法开始。
有一个除法算法,我完全搞不懂。
函数除法(x,)
输入:2个整数x和y,其中y>=1
输出:x的商和余数除以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

我们应该尝试这个算法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
有人能告诉我哪里出错了吗…
谢谢

最佳答案

我用ruby实现了你的算法(在arg列表中有明显的修正):

$ 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语句时,将其填充起来,扔掉,并将返回值写在堆栈顶部的一张纸上,以代替递归调用继续执行此工作表中的逻辑,直到到达另一个递归调用或返回。不断重复这一点,直到你用完了堆栈上的纸张-从最后一张纸返回是最终的答案。

关于algorithm - 除法算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/21149719/

10-16 02:37