这来自Euler项目的第3个问题:
https://projecteuler.net/problem=3
问题:13195的主要因素是5,7,13和29. 600851475143中最大的素数因子是什么?
因为这是一个难题,我宁愿不使用 jar 装Ruby方法 . 所以这里......
当前逻辑:
num是我们正在寻找的素数因子 .
候选人是潜在的主要因素
sqrt是num的平方根
until candidate >= sqrt
我从Eratosthenes的Sieves借用了这个想法来寻找素数,其中算法检查每个数字的可除性,直到num的平方根 . 候选是要测试num是否有除数的数字 .
if num % candidate == 0
...
end
目标是检查num是否可以被任何东西整除(有因子) . 如果num不能被候选者整除,则候选者将递增1直到 until
语句为真或者直到num可被候选者整除 .
如果num可以被候选者整除,那么我们知道候选者是素数并且它被插入到prime_factor中 . 然后递归发生以测试新定义的num .
prime_factors << num
如果 until
循环为真,那么该num没有除数,因此是素数 . 结果,它被插入到prime_factors中 .
问题:
问题不是它超时,而是它给出了错误的答案 . 似乎我的代码循环超过了需要 . 我添加了一些日志记录 . 我不知道为什么,但我认为它与递归片有关 . 不可否认,我从不在我的代码中使用递归,并希望用它来扩展我的技能 . 因此,从概念上讲,一般来说,递归对我来说是模糊的 . 任何阅读都会有所帮助 .
会发生什么:
prime_factors = [2,2,19]
prime_factors.last = 19
实际发生了什么:
prime_factors = [2,2,19,19,38]
prime_factors.last = 38
整个代码:
def largest_prime_factor(num,prime_factors)
puts "beg fx: num: #{num}, prime_factors: #{prime_factors}
candidate = 2
sqrt = Math.sqrt(num)
loop_count = 0
until candidate >= sqrt
if num % candidate == 0
num = num / candidate
prime_factors << candidate
largest_prime_factor(num,prime_factors)
end
candidate += 1
loop_count +=1
end
puts "outside loop: candidate >= sqrt is #{candidate >= sqrt} num: #{num}, prime_factors: #{prime_factors}, candidate: #{candidate}, sqrt: #{sqrt}, loop: #{loop_count}"
gets
prime_factors << num
prime_factors.last
end
1 回答
所以看起来,正如你所建议的,问题是递归逻辑 .
仅仅因为你递归地调用函数并不意味着“父”停止工作 - 他只是坐着等待“孩子”完成,然后继续前进 . 这就是“过度循环”发生的地方 . 代码实际上并没有过度循环,而是完成了 .
你可以在puts语句中看到这一点 . 请注意,在循环停止后,sqrt会增加,因为脚本现在正在运行父代码,而不是在递归的片段(子代)完成之后 .
对于修复,我做了两件事:1 . 创建一个布尔值,指示代码块已通过递归 . 如果是这样,运行此代码,否则...运行其他东西 . 2.如果候选者不是2,则增加2.这跳过测试除2之外的所有偶数 . 不需要测试其他偶数,因为它不是素数 .