使用 Python，我正在尝试解决Project Euler问题中的问题 #4。有人可以告诉我我做错了什么吗？问题是找到由两个 3 位数字的乘积组成的最大回文数。这是我到目前为止所拥有的。
import math
def main():
for z in range(100, 1000):
for y in range(100, 1000):
for x in range(1, 1000000):
x = str(x)
if x == x[::-1] and x == z*y:
print x
if __name__ == '__main__':
main()
一些效率问题：
def is_palindrome(n): s = str(n) return s == s[::-1] def biggest(): big_x, big_y, max_seen = 0,0, 0 for x in xrange(999,99,-1): for y in xrange(x, 99,-1): # so we don't double count if x*y < max_seen: continue # since we're decreasing, # nothing else in the row can be bigger if is_palindrome(x*y): big_x, big_y, max_seen = x,y, x*y return big_x,big_y,max_seen biggest() # (993, 913, 906609)
尝试从 z 和 y 的乘积计算 x，而不是检查从 1 到 100 万之间的每个数字。想一想：如果你被要求计算 500*240，哪个更有效 - 将它们相乘，还是从 1 开始计数直到找到正确答案？
以下是一些需要牢记的一般优化。发布的代码处理所有这些，但这些是学习的一般规则，可能有助于解决未来的问题：
1) 如果您已经检查过 z = 995, y = 990，则无需检查 z = 990, y = 995。Greg Lind 正确处理此问题
2) 你计算 z*y 的乘积，然后在一个很大的范围内运行 x 并将该值与 y*z 进行比较。例如，你刚刚计算了 900*950，然后你将 x 从 1000 运行到 1M，看看 x = 900*950。你看到这个问题了吗？
3）另外，下面的代码会发生什么？（这就是为什么您的代码没有返回任何内容，但无论如何您都不应该这样做）
x = str(100)
y = 100
print x == y
4）如果你算出（3），你将在那里打印很多信息。您需要找出一种存储最大值的方法，并且只在最后返回该值。
5）这是计算欧拉问题的好方法：
if __name__ == "__main__":
import time
tStart = time.time()
print "Answer = " + main()
print "Run time = " + str(time.time() - tStart)
而不是枚举所有 3 位数字的乘积（~900^2 次迭代），枚举所有 6 位和 5 位回文串（这需要 ~1000 次迭代）；然后为每个回文决定它是否可以用两个 3 位数的乘积表示（如果不能，它应该有一个 4 位数的素数，所以这很容易测试）。
另外，你问的是问题#4，而不是#3。
将字符串与整数进行比较
x == z*y
也有逻辑错误
以相反的顺序开始range(999, 99, -1)。那会更有效率。完全删除第三个循环和第二个比较。
哇，这种方法比这个页面上的其他实现改进了很多，包括我的。
代替
我们
不难证明，在每条对角线上，x 和 y 越接近，积越高。所以我们可以从中间开始，x = y（或x = y + 1奇数对角线），仍然像以前一样做短路优化。而且因为我们可以从最高的对角线开始，也就是最短的对角线，我们很可能更快地找到最高的合格回文。
maxFactor = 999
minFactor = 100
def biggest():
big_x, big_y, max_seen, prod = 0, 0, 0, 0
for r in xrange(maxFactor, minFactor-1, -1):
if r * r < max_seen: break
# Iterate along diagonals ("ribs"):
# Do rib x + y = r + r
for i in xrange(0, maxFactor - r + 1):
prod = (r + i) * (r - i)
if prod < max_seen: break
if is_palindrome(prod):
big_x, big_y, max_seen = r+i, r-i, prod
# Do rib x + y = r + r - 1
for i in xrange(0, maxFactor - r + 1):
prod = (r + i) * (r - i - 1)
if prod < max_seen: break
if is_palindrome(prod):
big_x, big_y, max_seen = r+i,r-i-1, prod
return big_x, big_y, max_seen
# biggest()
# (993, 913, 906609)
我们现在只调用了 2228 次，而不是调用 is_palindrome() 6124 次。并且总累积时间已经从大约 23 毫秒下降到大约 9 毫秒！
我仍然想知道是否有一种完全线性（O（n））的方式来生成按降序排列的两组数字的产品列表。但我对上述算法很满意。
This adds a couple of optimizations to @GreggLind's good solution, cutting the run time in half:
def is_palindrome(n):
s = str(n)
return s == s[::-1]
def biggest():
big_x, big_y, max_seen = 0,0, 0
for x in xrange(999,99,-1):
# Optim. 1: Nothing in any row from here on can be bigger.
if x*x < max_seen: break
for y in xrange(x, 99,-1): # so we don't double count
# Optim. 2: break, not continue
if x*y < max_seen: break # since we're decreasing,
# nothing else in the row can be bigger
if is_palindrome(x*y):
big_x, big_y, max_seen = x,y, x*y
return big_x,big_y,max_seen
biggest()
# (993, 913, 906609)
The line
if x*x < max_seen: break
means that once we get to the point where x is less than sqrt of largest palindrome yet seen, not only do we not need to investigate any more factors on that row; we don't even need to investigate any more rows at all, since all remaining rows would start from a number less than the current value of x.
This doesn't reduce the number of times we call is_palindrome(), but it means many fewer iterations of the outer loop. The value of x that it breaks on is 952, so we've eliminated the checking of 853 rows (albeit the "smaller" ones, thanks to the other break).
I also noticed that
if x*y < max_seen: continue
should be
if x*y < max_seen: break
We are trying to short-circuit the whole row, not just the current iteration of the inner loop.
When I ran this script using cProfile, the cumulative time for biggest() was about 56 msec on average, before the optimizations. The optimizations shrank it to about 23 msec. Either optimization alone would deliver most of that improvement, but the first one is slightly more helpful than the second.
问题指出：
What is the largest prime factor of the number 600851475143?
我使用 C# 解决了这个问题，但算法本身与语言无关。
private static long IsPrime(long input)
{
if ((input % 2) == 0)
{
return 2;
}
else if ((input == 1))
{
return 1;
}
else
{
long threshold = (Convert.ToInt64(Math.Sqrt(input)));
long tryDivide = 3;
while (tryDivide < threshold)
{
if ((input % tryDivide) == 0)
{
Console.WriteLine("Found a factor: " + tryDivide);
return tryDivide;
}
tryDivide += 2;
}
Console.WriteLine("Found a factor: " + input);
return -1;
}
}
private static long HighestPrimeFactor(long input)
{
bool searching = true;
long highestFactor = 0;
while (searching)
{
long factor = IsPrime(input);
if (factor != -1)
{
theFactors.Add(factor);
input = input / factor;
}
if (factor == -1)
{
theFactors.Add(input);
highestFactor = theFactors.Max();
searching = false;
}
}
return highestFactor;
}
我希望这会有所帮助，而不会放弃太多。
这是您可能会考虑的解决方案。它可能会更有效率，但只需要一点时间即可运行。
largest = 0
for a in range(100, 1000):
for b in range(100, 1000):
c = a * b
if str(c) == ''.join(reversed(str(c))):
largest = max(largest, c)
print(largest)
这里的另一个建议很棒。此代码也有效。我从 999 开始，因为我们知道可能的最大组合是 999*999。不是python，而是一些快速完成的伪代码。
public static int problem4()
{
int biggestSoFar=0;
for(int i = 999; i>99;i--){
for(int j=999; j>99;j--){
if(isPaladrome(i*j))
if(i*j>biggestSoFar)
biggestSoFar=i*j;
}
}
return biggestSoFar;
}
这是一个有效的通用解决方案（比我见过的其他解决方案快约 5 倍）：
def pgen(factor):
''' Generates stream of palindromes smaller than factor**2
starting with largest possible palindrome '''
pmax = str(factor**2)
half_palindrome = int(pmax[0:len(pmax)/2]) - 1
for x in xrange(half_palindrome, 0, -1):
yield int(str(x) + str(x)[::-1])
def biggest(factor):
''' Returns largest palindrome and factors '''
for palindrome in pgen(factor):
for f1 in xrange(factor/11*11, factor/10, -11):
f2 = palindrome/f1
if f2 > factor:
break
if f2*f1 == palindrome:
return palindrome, f1, f2
>>> biggest(99)
(9009, 99, 91)
>>> biggest(999)
(906609, 993, 913)
>>> biggest(9999)
(99000099, 9999, 9901)
>>> biggest(99999)
(9966006699L, 99979, 99681L)
>>> biggest(9999999)
(99956644665999L, 9998017, 9997647L)
>>> biggest(99999999)
(9999000000009999L, 99999999, 99990001L)
>>> biggest(999999999)
(999900665566009999L, 999920317, 999980347L)
如果您的程序运行缓慢，并且您有这样的嵌套循环：
for z in range(100, 1000):
for y in range(100, 1000):
for x in range(1, 1000000):
那么你应该问自己的一个问题是：“最内层循环的主体将执行多少次？” （最内层循环的主体是以： 开头的代码x = str(x)）
在这种情况下，很容易弄清楚。外部循环将执行 900 次。 对于每次迭代，中间循环也将执行 900 次——即 900×900 或 810,000 次。然后，对于这 810,000 次迭代中的每一次，内部循环本身将执行 999,999 次。我想我需要很长时间来计算：
>>> 900*900*999999
809999190000L
换句话说，您进行了近8100 亿次回文检查。如果您想将其纳入 Project Euler 建议的每个问题 1 分钟的限制，您可能需要稍微优化一下 :-)（请参阅 David 的评论）
这就是我在 Java 中所做的：
public class Euler0004
{
//assumes positive int
static boolean palindrome(int p)
{
//if there's only one char, then it's
// automagically a palindrome
if(p < 10)
return true;
char[] c = String.valueOf(p).toCharArray();
//loop over the char array to check that
// the chars are an in a palindromic manner
for(int i = 0; i < c.length / 2; i++)
if(c[i] != c[c.length-1 - i])
return false;
return true;
}
public static void main(String args[]) throws Exception
{
int num;
int max = 0;
//testing all multiples of two 3 digit numbers.
// we want the biggest palindrome, so we
// iterate backwards
for(int i = 999; i > 99; i--)
{
// start at j == i, so that we
// don't calc 999 * 998 as well as
// 998 * 999...
for(int j = i; j > 99; j--)
{
num = i*j;
//if the number we calculate is smaller
// than the current max, then it can't
// be a solution, so we start again
if(num < max)
break;
//if the number is a palindrome, and it's
// bigger than our previous max, it
// could be the answer
if(palindrome(num) && num > max)
max = num;
}
}
//once we've gone over all of the numbers
// the number remaining is our answer
System.out.println(max);
}
}
这是我的解决方案：
polindroms = [(x, y, x * y) for x in range(100, 999) for y in range(100, 999) if str(x * y) == str(x * y)[::-1]]
print max(polindroms, key = lambda item : item[2])