劃分算法

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」，只是以二進制形式完成。