对回文产品问题感到困惑

Question

我一直在学习Ruby,所以我想我会尝试一些项目的Euler难题.令人尴尬的是,我只是解决了问题4 ......

问题4如下:

回文数字两种方式相同.由两个2位数字的乘积制成的最大回文是9009 = 91×99.

找到由两个3位数字的乘积制成的最大回文.

所以我想我会在一个嵌套的for循环中从999循环到100并对回文进行测试,然后当我找到第一个(应该是最大的一个)时突破循环:

final=nil
range = 100...1000
for a in range.to_a.reverse do
  for b in range.to_a.reverse do
    c=a*b
    final=c if c.to_s == c.to_s.reverse
    break if !final.nil?
  end
  break if !final.nil?
end
puts final

这确实输出了回文580085,但显然这不是该范围内两个三位数字的最高乘积.奇怪的是,如果我将范围更改为10 ... 100,则相同的代码成功返回9009,就像在示例中一样.

• 谁能告诉我哪里出错了？
• 还有,有一种更好的方法可以打破内部循环吗？

谢谢

Answer 1

您正在测试999*(999 ... 100),然后是998*(999 ... 100)

因此,在测试997*996之前,您将测试999*500.

那么,我们如何找到合适的号码？

首先注意乘法是反射的,a*b == b*a,所以b不必每次都从999 ... 0,只是... 0.

当你找到一个palindrone时,将两个因素加在一起并保存总和(同时保存这两个因素)

在循环内部,如果(a + b)小于保存的总和,则放弃内循环并移动到下一个a.当a低于sum/2时,你找不到的未来值将高于你已经找到的值,所以你已经完成了.

Answer 2

问题是你可能会找到一个a999和b200 的回文,但是你太快就会中断,所以你永远不会看到998*997(只是示例数字).

您需要查找所有回文,或者一旦找到第一个回答,将其设置b为最小限度并继续查看a循环.