为什么Josef Stein的二进制GCD算法的这个实现只适用于某些情况？

Question

为什么Josef Stein的二进制GCD算法的这个实现只适用于某些情况？

algorithmrecursionruntime-errorschemelisp

4

使用Scheme语言，我构建了一个迭代实现的二进制GCD算法（也称为Stein算法），用于计算数字u和v的最大公约数。该算法的步骤如下：

1. gcd(0,v)=v，因为任何数都能整除零，而v是能够整除v的最大数。同样地，gcd(u,0)=u。通常不定义gcd(0,0)，但将gcd(0,0)设置为0很方便。

2. 如果u和v都是偶数，则gcd(u,v)=2·gcd(u/2,v/2)，因为2是一个公共因子。

3. 如果u是偶数且v是奇数，则gcd(u,v)=gcd(u/2,v)，因为2不是公共因子。同样地，如果u是奇数且v是偶数，则gcd(u,v)=gcd(u,v/2)。

4. 如果u和v都是奇数，并且u≥v，则gcd(u,v)=gcd((u-v)/2,v)。如果两者都是奇数且u

5. 重复步骤2-4，直到u=v，或者（再进行一步）直到u=0。在任一情况下，GCD是2的k次方乘以v，其中k是在步骤2中找到的公共因子数。

我所制作的算法如下：

(define (stein u v)
  (cond
    ((or (= u 0)(= u v))
      v)
    ((and (even? u) (even? v))
      (* 2 (stein (/ u 2)(/ v 2))))
    ((and (even? u) (odd? v))
      (stein (/ u 2) v))
    ((and (odd? u) (even? v))
      (stein u (/ v 2)))
    ((and (and (odd? u) (odd? v))(>= u v))
      (stein (/ 2 (- u v)) v))
    ((and (and (odd? u)(odd? v))(< u v))
      (stein (/ 2 (- v u)) u))))

我的问题是，每当我遇到一个数字是奇数而另一个数字是偶数的情况（无论是输入数据本身就这样还是程序调用自身时变成这样），输出要么为空，要么返回错误：Error: *: number required, but got #<undef> [stein, stein, stein, *]

有人能解释一下为什么会出现这种情况以及如何解决吗？

谢谢！

- Jodast

1

你应该在你的cond中加入一个“捕获所有”情况，以避免程序崩溃。你的情况应该是穷尽的，但是你没有捕获它们不是的情况。#<undef>来自于递归情况中的掉落；你的低级stein掉落了cond并返回#<undef>。高级stein试图将#<undef>乘以2。 - Kaz

@Kaz 我应该怎么做？ - Jodast

1

（cond（无论什么呃）...（＃t（不应到达））） - Kaz

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Renzo · Accepted Answer

这两行代码存在错误:

(stein (/ 2 (- u v)) v))

并且

(stein (/ 2 (- v u)) u))))

您应该将差值除以2，而不是反过来。也就是说：

(stein (/ (- u v) 2) v))

并且

(stein (/ (- v u) 2) u))))

最后，需要一个测试来检查第二个参数是否等于0，否则在某些情况下函数会无限循环。

类似这样：

(define (stein u v)
  (cond
    ((or (= u 0)(= u v))
      v)
    ((= v 0) u)
    ((and (even? u) (even? v))
      (* 2 (stein (/ u 2)(/ v 2))))
    ((and (even? u) (odd? v))
      (stein (/ u 2) v))
    ((and (odd? u) (even? v))
      (stein u (/ v 2)))
    ((and (and (odd? u) (odd? v))(>= u v))
      (stein (/ (- u v) 2) v))
    ((and (and (odd? u)(odd? v))(< u v))
      (stein (/ (- v u) 2) u))))