项目Euler问题的Ruby解决方案#4:最大回文积

Question

我已经解决了Project问题#4，但是我想要一些关于如何提高效率的技巧。我是Ruby的初学者，所以请对那些愚蠢的东西友好一点(但还是要告诉我)。

项目欧拉4:最大回文产品

回文数字的读取方式是相同的。由两位数乘积而成的最大回文数为9009 = 91×99.找到最大的回文由两个3位数的乘积而成.1

class Euler4
  def isPalindrome(n)
    n == n.to_s.reverse.to_i
  end
end

  puts "Setting Variables"
  x = 999
  y = 999

  highest = 1

  found = false

  while (x > 100 && !found)
    y = 999
    while (y > 100 && !found)
      puts "Working with"
      puts x
      puts " and "
      puts y

      if Euler4.new.isPalindrome(x*y)
        puts "Found Palindrome"
        puts x
        puts y
        puts x*y
        if highest < (x*y)
          highest = x * y
        end
      end
      y = y - 1
    end

    x = x - 1

  end

puts "Highest Found"
puts highest

Answer 1

让我们从一些小事情开始：

def isPalindrome(n)
  n == n.to_s.reverse.to_i
end

我怎么知道一个数字是否是回文？

• 将其转换为字符串。
• 产生那个字符串的反面。
• 将反向字符串转换为数字。
• 比较这些数字是否相等。

作为你自己:为什么我们需要做最后两个步骤？我们本可以说：

• 将其转换为字符串。
• 产生那个字符串的反面。
• 比较字符串是否相等。

并完全跳过“转换为整数”的步骤。

下一件小事。我删除了您程序中不使用变量found的每一行：

found = false
while (x > 100 && !found)
  while (y > 100 && !found)

看到那个代码有什么问题吗？因为我没有看到它被设置为true，因此它将永远是false。我不知道为什么总是假的变量对你有用。

下一步:检查所有对：(999,999)，(999,998)，. (999,101)，然后用(998,999)重新开始。但当您检查(999,998)时，您已经检查了(998,999)！您不需要在999开始y。在y上启动x就足够了。然后，你只检查每对一次，而不是检查其中绝大多数两次。

下一步:如果您找到一个(x，y)对是回文，您不需要检查(x，y- 1)；即使它是回文，它也会更小。也许这就是你试图用你的“找到的”变量做的事情，但是你从来没有正确地写过逻辑。

下一步:删除所有打印调试跟踪。如果需要调试程序，请使用调试器。

Answer 2

一些风格的评论：

首先，不需要将isPalindrome()放入类中，只需简单地声明并直接使用它。此外，ruby首选样式是使用snake_case，如果该函数是一个谓词(一个接受值并返回true/false的函数)，则应该在结尾添加一个问号：

def is_palindrome?(n)
  # ...
end

# usage
is_palindrome? 6006    # => true
is_palindrome?(1234)   # => false   

其次，您有一些代码如下所示：

x = 999
while (x > 100)
  # ...
end

Ruby有范围，范围和枚举器的构造。范围是序列号的集合，而枚举数是循环结构，循环遍历集合，如数组中的项或范围中的数字。虽然范围只计数向上，但是有一个用于向下计数的函数，downto()返回一个枚举数。

# Range Example: Counting Up
(5..9).each { |i| print i }  # .each here makes an enumerator over the range
# => 12345

# Enumerator Example: Counting Down
9.downto(5) do |i|   # downto() creates an enumerator that starts at 9 and ends at 5
  print i
end
# => 98765

最后，您有如下代码：

puts "Found Palindrome"
puts x
puts y
puts x*y

Ruby有几种方便打印文本的方法。首先是字符串插值。在字符串上使用双引号，在字符串中使用#{ code }。当ruby解析字符串时，代码将被执行，结果将替换字符串中的代码。

puts "Found a palindrome: #{x} x #{y} = #{x*y}"
# => "Found a palindrome: 993 x 913 = 906603"

Ruby也有C风格的格式字符串。在字符串中使用‘'%d'，%f'，'%s’等，然后在字符串末尾提供一个包含所有参数的数组。

puts "Found a palindrome: %d x %d = %d" % [x, y, x*y]
# => "Found a palindrome: 993 x 913 = 906603"

一些代码注释

正如Eric提到的，您可以通过不执行重复工作和明智地管理您循环的值来加快速度。

Answer 3

如前所述，如果您尝试过999 * 998，也不需要检查998 * 999，因为结果是相同的。但是，您也可以通过将下界设置为产生回文的两个因素的下界来限制范围。

例如，a = 995和b = 583生成一个回文：580085。我们不知道它是否是最高的，但是我们知道一个回文要更大，它的较小的因子必须等于或大于b。

我们可以不断减少b，我们会找到995 * 517 = 514415 --但为什么要费心呢？

因此，对于下一个循环，我们只需要尝试范围994..583。

一种(快速编写的)方法可以是：

palindromes = []
minimum = 100    # initial lower bound

999.downto(minimum) do |a|
  a.downto(minimum) do |b|
    product = a * b
    if product.to_s.reverse == product.to_s
      minimum = b                    # set new lower bound
      palindromes << [a, b, product] # note the factors and product
      break                          # break out of inner loop
    end
  end
end

# find and print the greatest palindrome
a, b, product = palindromes.max_by(&:last)
puts "#{a} * #{b} = #{product}"

这将尝试7227个组合(奇怪的是，这是回文本身)，并找到5个候选回文。

但它可以改进得更多。以上仅在找到回文的情况下才会提高下界，但无论产品是否回文，如果该乘积比先前发现的回文小，则可以提高下界。例如：

greatest_palindrome = 0
minimum = 100

999.downto(minimum) do |a|
  a.downto(minimum) do |b|
    product = a * b

    # if it's a palindrome, store it
    if product.to_s.reverse == product.to_s
      greatest_palindrome = product
    end

    # if the product is smaller than a known palindrome, we can
    # raise the lower bound
    if product <= greatest_palindrome
      minimum = b
      break
    end
  end
end

puts greatest_palindrome

现在只剩下6166次了。