由两个三位数乘积构成的回文数

Question

我想找到两个三位数相乘得到的最大回文数。

我一开始把a和b都设为999，然后在每次相乘后把a和b都减小。

a = 999 #Defining Variables
b = 999

for i in range (1000): 
    c= a*b                          #multiply a to b
    if int(str(c)[::-1]) == c:
        print c
    a = a-1                         #decrement the value of a
    c=a*b                           #multiply a by the decremented a
    if int(str(c)[::-1]) == c:
        print c

    b = b-1                         #decrement b so that both a and b have been decremented

结果出现了698896、289982、94249、69696……其中698896是第一个找到的数字。目前我还在想我漏掉了什么。

Answer 1

最快的方法是从最大回文数开始往下找，最大值是999乘以999等于998001。我们可以从997799、996699开始，检查每一个数字，看它是否可以被分成两个在100到999之间的数。我的代码运行了2200次循环，而你的代码大约需要4000到8000次循环。

Sub method3a()
iterations = 0
For a = 997 To 0 Step -1
    R = a * 1000 + Val(StrReverse(a))
    b = 999      ' R=b*s
    s = Int(R / b)
    While b >= s
        iterations = iterations + 1
        If R = b * s Then
            Debug.Print "Result=" & R & " iterations=" & iterations
            Exit Sub
        End If
        b = b - 1
        s = Int(R / b)
    Wend
Next

结束子程序

Answer 2

你的算法有问题。你需要把所有的a值和所有的b值都测试一遍，这可以通过使用两个循环来解决（外层循环用a，内层循环用b）。我还建议你把a和b作为循环的索引，这样逻辑会更简单（更容易记住）。

考虑把回文检查单独放到一个函数里，这样代码会更容易理解。

---

我不是Python程序员，但这是我用PHP写的解决方案：

function palindrome($x) {
  $x = (string) $x;  //Cast $x to string
  $len = strlen($x); //Length of $x

  //Different splitting depending on even or odd length
  if($len % 2 == 0) {
    list($pre, $suf) = str_split($x, $len/2);
  }else{
    $pre = substr($x, 0, $len/2);
    $suf = substr($x, $len/2+1);
  }

  return $pre == strrev($suf);
}

$max = array(0, 0, 0);

//Loop $a from 999 to 100, inclusive.
//Do the same over $b for EVERY $a
for($a = 999; $a >= 100; $a--) {
  for($b = 999; $b >= 100; $b--) {
    $x = $a*$b;

    if(palindrome($x)) {
      echo $a, '*', $b, ' = ', $x, "\n";
      if($x > $max[2]) {
        $max = array($a, $b, $x);
      }
    }
  }
}
echo "\nLargest result: ", $max[0], '*', $max[1], ' = ', $max[2];

Answer 3

你不能交替地减少 a 和 b 的值，因为这样会漏掉一些配对的值，比如 a 是 999 而 b 是 997 的情况。

可以试试用嵌套循环的方法，从 999 开始往回数。

大概可以这样写：

def is_pal(c):
    return int(str(c)[::-1]) == c

maxpal = 0
for a in range(999, 99, -1):
    for b in range(a, 99, -1):
        prod = a * b
        if is_pal(prod) and prod > maxpal:
            maxpal = prod

print maxpal

编辑：根据保罗的评论，修改了下限。