2

範囲があるとしましょう: 1 ≤ X≤ 120

これは私が試したことです：

>>> def isPalindrome(s):
    ''' check if a number is a Palindrome '''
    s = str(s)
    return s == s[::-1]

>>> def generate_palindrome(minx,maxx):
    ''' return a list of Palindrome number in a given range '''
    tmpList = []
    for i in range(minx,maxx+1):
        if isPalindrome(i):
            tmpList.append(i)

    return tmpList

>>> generate_palindrome(1,120)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111]

しかし、これはO(n).

このアルゴリズムを改善して高速化するにはどうすればよいですか?

PS。これは Python 2.7 です

4

6 に答える 6

7

あなたの方法は次のとおりです。

palindromes = [x for x in xrange(min, max) if isPalindrome(x)]

これを行うことができ、非線形アルゴリズムを使用できる唯一の方法は、テストではなく、回文を自分で生成することです。

回文は、前の回文に同じ数を左辺と右辺に足すことで生成できるので、そこが出発点です。

から始めるとしましょう1:

可能性のある回文は、1:9 の各数字を左右に追加することによって得られます。

111
212
313
...

また、範囲内のすべての桁が等しいいくつかのエントリを生成する必要があります...

于 2013-05-02T17:43:53.327 に答える
4

これは楽しい作業だと思うので、さびついた Python のスキルを練習しました。

def generate_palindromes_with_length(l):
''' generate a list of palindrome numbers with len(str(palindrome)) == l '''
    if l < 1:
        return []
    if l == 1:
        return [x for x in range(10)]
    p = []
    if (l % 2):
        half_length = (l - 1) / 2
        for x in xrange(0, 10):
            for y in xrange(10 ** (half_length - 1), 10 ** half_length):
                p.append(int(str(y) + str(x) + str(y)[::-1]))
    else:
        half_length = l / 2
        for x in xrange(10 ** (half_length - 1), 10 ** half_length):
            p.append(int(str(x) + str(x)[::-1]))
    p.sort()
    return p


def generate_palindrome(minx, maxx):
''' return a list of palindrome numbers in a given range '''
    min_len = len(str(minx))
    max_len = len(str(maxx))
    p = []
    for l in xrange(min_len, max_len + 1):
        for x in generate_palindromes_with_length(l):
            if x <= maxx and x >= minx:
                p.append(x)
    p.sort
    return p

generate_palindromes_with_lengthここで重要な部分です。この関数は、指定された小数点以下の桁数で回文を生成します。小数点以下の奇数と偶数に異なる戦略を使用します。例: 長さ 5 が要求された場合、パターン の回文が生成されますabxba。ここでa、 、b、およびxは 1 から 9 までの任意の数です (さらにx0 の場合もあります)。要求された長さが 4 の場合、パターンはabbaです。

generate_palindrome必要なすべての長さの回文を収集するだけで済み、境界を処理する必要があります。

アルゴリズムは O(2*p) で、p は回文数です。

アルゴリズムは機能します。ただし、私の python スキルはさびているため、より洗練されたソリューションのアドバイスをいただければ幸いです。

于 2013-05-02T18:54:37.307 に答える
1

これは、すぐにリストを表示したい場合に機能します。

def palindrome_range(start,stop,step=1):
    ret=[x for x in xrange(start,step,stop) if str(x)==str(x)[::-1]]
    return ret

ただし、ジェネレーターが必要な場合は、次を使用できます。

def palindrome_range(start,stop,step=1):
    for x in xrange(start,stop,step):
        if str(x)==str(x)[::-1]:
            yield x

これらは、使用している内容に応じて、物事をかなり高速化するのに役立ちます。たとえば、回文を反復処理したい場合は、ジェネレーターが役立ちます。ただし、リスト全体が必要な場合は、返される通常のリストの方が適しています。xrangeただし、ここに記載されているように、大きなリストをより適切に処理するため、この場合は範囲​​よりもはるかに優れていることも注目に値します。

于 2013-05-02T19:24:50.907 に答える