Python を使用して、Project Eulerの問題の4 番目の問題を解決しようとしています。誰かが私が間違っていることを教えてもらえますか? 問題は、2 つの 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)
1から100万までのすべての数値をチェックするのではなく、zとyの積からxを計算してみてください。考えてみてください。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)
文字列と整数の比較
x == z*y
論理エラーもあります
逆の順序で開始しますrange(999, 99, -1)。それはより効率的になります。3番目のループと2番目の比較を完全に削除します。
3 桁の数のすべての積を列挙する (~900^2 回の反復) のではなく、6 桁および 5 桁の回文をすべて列挙します (これには ~1000 回の反復が必要です)。次に、回文ごとに、2 つの 3 桁の数の積で表現できるかどうかを判断します (できない場合は、4 桁の素因数を持つ必要があるため、これは簡単にテストできます)。
また、あなたは #3 ではなく、問題 #4 について質問しています。
うわー、このアプローチは、私のものを含む、このページの他の実装よりもかなり改善されています。
それ以外の
私たち
各対角線上で、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)
is_palindrome() を 6124 回呼び出す代わりに、2228 回だけ呼び出すようになりました。合計累積時間は、約 23 ミリ秒から約 9 ミリ秒に短縮されました。
降順で2セットの数値の積のリストを生成する完全に線形(O(n))の方法があるかどうか、私はまだ疑問に思っています。しかし、私は上記のアルゴリズムにかなり満足しています。
これにより、@GreggLind の優れたソリューションにいくつかの最適化が追加され、実行時間が半分に短縮されます。
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)
この線
if x*x < max_seen: break
x がこれまでに見た最大の回文の sqrt よりも小さい点に到達すると、その行の要素をそれ以上調査する必要がないだけでなく、残りのすべての行は x の現在の値よりも小さい数値から始まるため、これ以上行を調査する必要さえありません。
これは を呼び出す回数を減らすわけではありませんis_palindrome()が、外側のループの反復回数が大幅に減ることを意味します。それが壊れるの値xは 952 であるため、853 行のチェックを省略しました (他の のおかげで「小さい」行ではありますがbreak)。
ということにも気づきました
if x*y < max_seen: continue
する必要があります
if x*y < max_seen: break
内側のループの現在の反復だけでなく、行全体を短絡しようとしています。
cProfileを使用してこのスクリプトを実行したとき、最適化前の累積時間はbiggest()平均で約 56 ミリ秒でした。最適化により、約 23 ミリ秒に短縮されました。どちらの最適化だけでも改善のほとんどは実現できますが、最初の最適化は 2 番目の最適化よりもわずかに役立ちます。
これは効率的な一般的なソリューションです（私が見た他のソリューションよりも約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)
質問には次のように記載されています。
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;
}
あまりにも多くを与えることなく、これが役立つことを願っています。
ここでの他のアドバイスは素晴らしいです。このコードも機能します。可能な最大の組み合わせは 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;
}
考えられる解決策を次に示します。はるかに効率的ですが、実行にかかる時間はわずかです。
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)
プログラムの実行速度が遅く、次のようなネストされたループがある場合:
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 回実行されます。それを計算するには long が必要だと思います：
>>> 900*900*999999
809999190000L
つまり、回文チェックを約8,100 億回行っていることになります。問題ごとに 1 分の Project Euler の推奨制限にそれを入れたい場合は、少し最適化することをお勧めします :-) (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])