6

我一直在学习 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,就像在示例中一样。

  • 有人可以告诉我哪里出错了吗?
  • 另外,有没有更好的方法来打破内部循环?

谢谢

4

13 回答 13

9

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

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

那么,我们如何找到正确的数字?

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

当您找到回文时,将两个因素相加并保存总和(同时保存两个因素)

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

于 2010-08-11T19:13:01.360 回答
5

问题是你可能会找到一个a999 和b200 的回文,但是你打破得太快了,所以你永远看不到 998*997 有一个回文(只是示例数字)。

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

于 2010-08-11T19:12:59.713 回答
3

考虑 P 的数字——假设它们是 x、y 和 z。由于回文 111111 = 143×777(两个 3 位整数的乘积),P 必须至少有 6 位长。由于 P 是回文:

P=100000x + 10000y + 1000z + 100z + 10y + x
P=100001x + 10010y + 1100z
P=11(9091x + 910y + 100z)

因为 11 是素数,所以整数 a 或 b 中至少有一个必须有 11 的因数。所以如果 a 不能被 11 整除,那么我们知道 b 一定是。使用这些信息,我们可以确定我们根据 a 检查 b 的哪些值。

于 2010-08-17T03:32:36.793 回答
3

关于第二个问题,我的建议是以功能性而非程序性的方式解决问题。因此,您可以尝试在功能上“描述”您的问题,而不是循环,让 Ruby 完成工作:

  • 从所有 3 位数字对中,
    • select只有那些乘积是回文的人,
      • 并找到具有最大产品的那个

尽管这种方法可能不会产生最有效的解决方案,但它可能会教给您几个 Ruby 习惯用法。

于 2010-08-11T19:52:56.857 回答
2

C# 实现:

using System;

namespace HighestPalindrome
{
    class Program
    {
        static void Main(string[] args)
        {
            int i, j;
            int m = 1;
            bool flag = false;

            while (true)
            {
                if (flag) j = m + 1;
                else j = m;

                for (i = m; i > 0; i--)
                {
                    Console.WriteLine("{0} * {1} = {2}", 1000 - i, 1000 - j, (1000 - i) * (1000 - j));
                    j++;

                    //--- Palindrome Check ------------------------------

                    int number, temp, remainder, sum = 0;
                    number = temp = (1000 - i) * (1000 - j);

                    while (number > 0)
                    {
                        remainder = number % 10;
                        number /= 10;
                        sum = sum * 10 + remainder;
                    }

                    if (sum == temp)
                    {
                        Console.WriteLine("Highest Palindrome Number is - {0} * {1} = {2}", 1000 - i, 1000 - j, temp);
                        Console.ReadKey();
                        return;
                    }

                    //---------------------------------------------------
                }

                if (flag)
                    m++;
                flag = !flag;
            }

        }
    }
}
于 2011-02-05T06:42:36.813 回答
1

最主要的是遍历所有可能的值。当你找到第一个答案时不要试图打破,只需从最佳答案零开始,然后尝试所有组合并保持最佳更新。其次是尽量减少“所有组合”的集合。

您可以做的一件事是将内部循环限制为小于或等于 a 的值(因为 a b == b a)。这会将较大的等式值始终放在 a 中,并大大减少了您必须测试的值的数量。

替代文字

for a in range.to_a.reverse do
    for b in (100..a).to_a.reverse do

您可以做的下一件事是在产品小于当前最佳值时打破内部循环。

c = a*b
next if c < best

接下来,如果您无论如何都要遍历它们,那么反向遍历它们没有任何好处。通过从范围的顶部开始,您需要一段时间才能找到回文数,因此需要一段时间来减少您的搜索集。如果您从底部开始,您将开始快速增加下限。

for a in range.to_a do
    for b in (100..a).to_a do

我的测试表明,无论哪种方式,您都可以尝试一些 405K 对。那么如何换一种方式来思考这个问题。两个 3 位数字的最大可能乘积是多少?999 * 999 = 998001,最小的是 100*100 = 10000。我们如何采用您打破第一个答案的想法,但将其应用于不同的范围,即 998001 到 10000(或 999*999 到 100* 100)。

for c in (10000...998001).to_a.reverse do

仅经过 202 次测试,我们就得到了一个回文……问题是它不是两个 3 位数字的乘积。所以现在我们必须检查我们找到的回文是否是 2 个 3 位数字的乘积。一旦我们在回文和两个 3 位数字的乘积范围内找到一个值,我们就完成了。我的测试表明,在少于 93K 次测试后,我们找到了满足要求的最高回文数。但是由于我们需要检查所有回文数是否是两个 3 位数字的乘积,因此它可能不会比之前的解决方案更有效。

所以让我们回到最初的改进。

for a in range.to_a.reverse do
    for b in (100..a).to_a.reverse do

我们循环行然后列,并试图通过检测我们可以转到下一行的点来提高效率,因为对当前行的任何额外尝试都不可能比我们当前最好的更好。如果我们不是沿着行向下走,而是穿过对角线怎么办?

替代文字

由于产品对角线越来越小,因此您可以在找到回文数后立即停止。这是一个非常有效的解决方案,但实现更复杂。事实证明,这种方法在 2200 多次尝试后找到了最高的回文。

于 2010-08-11T21:15:38.097 回答
1

错误是您假设如果您找到具有最大a价值的回文,它将提供最好的产品,这是不正确的。解决方案是保持max_product价值并根据您找到的解决方案对其进行更新。

于 2010-08-11T19:12:16.737 回答
1

我可以回答你的第一个问题:你需要找到最高的产品,而不是包含最高因素的产品。换句话说a * b,可能大于c * d即使c > a > b

于 2010-08-11T19:12:17.913 回答
1

你正在打破你来到的第一个回文,不一定是最大的。

假设你有 A、B、C、D、E。在测试 D * C 之前测试 E * A。

于 2010-08-11T19:14:50.927 回答
1
ar=[]
limit = 100..999
for a in limit.to_a.reverse do
  for b in (100..a).to_a.reverse do
    c=a*b
    if c.to_s == c.to_s.reverse
      palndrm=c 
      ar << palndrm
    end  
  end
end
print ar
print"\n"
puts ar.max
puts ar.min 
于 2011-06-30T10:34:42.083 回答
0

对于这个问题,当我们正在寻找最高的回文时,我假设它以 9 开​​头。因此以 9(回文)结尾。

如果你注意,要得到一个以 9 结尾的数字,你只能得到以 9 和 1、3 和 3、7 和 7 结尾的数字。

然后检查其他值是没有用的(例如 999*998,因为它不会以 9 结尾)。

从 999 和 991 开始,您可以将 10 减去 991,尝试 999 和 981 等...您对 993 和 993 执行相同操作 ... 993 * 983 与 997 * 997 相同,然后 997 * 987 等您没有需要超过 900 或 10^4 - 10^3,因为您可以确定最高值会在之前。

int PB4_firstTry(int size)
{
    int nb1 = (int)pow(10.0,size+1.0) - 1, nb2 = (int)pow(10.0,size+1.0) - 1;
    int pal91 = getFirstPalindrome(size,9,1);
    int pal33 = getFirstPalindrome(size,3,3);
    int pal77 = getFirstPalindrome(size,7,7);

    int bigger1 = (pal91 > pal33) ? pal91 : pal33;
    return (bigger1 > pal77) ? bigger1 : pal77;
}

int getFirstPalindrome(int size,int ending1,int ending2)
{
    int st1 =  (int)pow(10.0,size+1.0) - 10 + ending1;
    int comp = st1 - pow(10.0,size);
    int st2 =  (int)pow(10.0,size+1.0) - 10 + ending2;
    int answer = -1;
    while (st1 > comp)
    {
        for (int i = st2; i > comp && st1*i > answer; i-=10)
        {
            if (PB4_isPalindrome(st1*i))
                answer = st1*i;
        }
        st1 -= 10;
    }
    return answer;
}

bool PB4_isPalindrome(int number)
{
    std::string str = intToString(number);
    for (int i = 0; i < (int)(str.length() / 2); i++)
    {
        if (str[i] != str[str.length() - 1 - i])
            return false;
    }
    return true;
}

std::string intToString(int number)
{
    std::ostringstream convert;
    convert << number;
    return convert.str();
}

当然,这适用于 4 个大小的数字因子等。

于 2013-08-14T14:36:11.600 回答
0

一个实现:

max = 100.upto(999).inject([-1,0,0]) do |m, a|
  a.upto(999) do |b|
    prod = a * b
    m = [prod, a, b] if prod.to_s == prod.to_s.reverse and prod > m[0]
  end
  m
end
puts "%d = %d * %d" % max

印刷906609 = 913 * 993

于 2010-08-11T20:28:06.370 回答
0

这是我在 Ruby 中想到的:

def largest_palindrome_product(digits)
  largest, upper, lower = 0, 10**digits - 1, 10**(digits - 1)

  for i in upper.downto(lower) do
    for j in i.downto(lower) do
      product = i * j
      largest = product if product > largest && palindrome?(product)
    end
  end
  largest
end

这是检查数字是否为回文的函数:

def palindrome?(input)
  chars = input.to_s.chars
  for i in 0..(chars.size - 1) do
    return false if chars[i] != chars[chars.size - i - 1]
  end
  true
end

不过,我想那里可能有更有效的解决方案。

于 2013-05-31T03:41:15.617 回答