使用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)。如果两者都是奇数且u5. 重复步骤2-4,直到u=v,或者(再进行一步)直到u=0。在任一情况下,GCD是2的k次方乘以v,其中k是在步骤2中找到的公共因子数。
我所制作的算法如下:
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)。如果两者都是奇数且u5. 重复步骤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, *]
有人能解释一下为什么会出现这种情况以及如何解决吗?
谢谢!