两个 n 位数字的递归除法算法

Question

在下面的除法算法中，我不理解为什么将q和r乘以二会起作用，以及如果x是奇数为什么要增加r。

请给出这个递归除法算法的理论证明。

提前感谢您的回答。

function divide(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)

- Tejas P

---

如果你不理解一个算法，应该尝试用纸和笔让它工作起来。提示：你正在处理二进制表示中的一个数字。 - user4668606

Answer 1

假设您想将x除以y，即表示为x = Q * y + R。

假设x是偶数。您可以递归地将x / 2除以y，并获得更小情况下所需的表示形式：x / 2 = q * y + r。

通过乘以二，您会得到：x = 2q * y + 2r。查看您一开始想要获得的x的表示形式，您会发现已经找到了它！让Q = 2q和R = 2r，您找到了所需的Q和R。

如果x是奇数，则再次首先获得更小情况下所需的表示形式：(x - 1) / 2 = q * y + r，将其乘以二：x - 1 = 2q * y + 2r，并将1发送到右侧：x = 2q * y + 2r + 1。同样，您已经找到了所需的Q和R：Q = 2q，R = 2r + 1。

算法的最后一部分只是规范化，以使r < y。当您执行乘以二时，r可能会变得大于y。

- Alexey Subach

Answer 2

算法谜题求解(k,S,U)： 输入：一个整数k，序列S和集合U 输出：使用U中的元素枚举所有长度为k的S扩展，不重复 对于U中的每个e， 将e添加到S的末尾 从U中删除e /现在正在使用e/ 如果k == 1，则 测试S是否是解决谜题的配置 如果S解决了谜题，则 返回“找到解决方案：”S 否则 PuzzleSolve(k-1,S,U) /递归调用/ 从S的末尾删除e 将e重新添加到U中，现在被视为未使用 该算法枚举了U的每个可能的大小为k的有序子集，并测试每个子集是否是我们谜题的可能解。对于求和谜题，U = 0,1,2,3,4,5,6,7,8,9，序列中的每个位置对应于给定的字母。例如，第一个位置可以代表b，第二个位置可以代表o，第三个位置可以代表y，依此类推。

- Nada Joudeh