Lua：递归多个数字的最大公约数欧几里得计算 - 永无止境的循环。

2015-7-17 8:32:4
收藏：0
阅读：87
评论：1

我尝试使用递归计算几个数字的最大公约数。

以下是我的尝试。超过两个数字就是一个无尽循环。 我不确定 pgcd(unpack(arg)) 部分是否正确，但我没有其他想法。

编辑 实际上，似乎 arg.n > 2 不高效...

function pgcd(...)
    local arg = table.pack(...)
    if arg.n > 2 then
        local tmp = table.remove(arg, 1)
        return pgcd(tmp, pgcd(unpack(arg)))
    else
        a, b = unpack(arg)
        repeat
            a, b = b, a % b
        until a % b == 0
        return b
    end
end

print(pgcd(18, 12)) -- 正常工作

print(pgcd(18, 12, 9)) -- 无限循环
点赞
用户3675489
用户3675489

实际上，这个测试的结束一次过多。

function pgcd ( ... )
    local arg = table.pack(...)
    if arg.n > 2
    then
        local tmp = table.remove(arg,1)
        return pgcd (tmp, pgcd( unpack(arg) ) )
    else
        a,b = unpack(arg)
        repeat
        a , b = b , math.fmod(a,b)
        until b == 0 -- 这个测试过头了一次

        return a
    end
end

print (pgcd(18,12))  -- 运行正常

print (pgcd(18,12,6)) -- 运行正常
2015-07-17 09:14:53

作者:

用户3675489

用户3675489
推荐文章