계산 방법 많은 수의 간격으로 palindroms?

Question

나는 큰 간격 데이터 회문 얼마나 많은 숫자 계산하려는

는 10^15

내 간단한 코드 (파이썬) 조각은 말 :

def count_palindromes(start, end): 
    count = 0 
    for i in range(start, end + 1): 
     if str(i) == str(i)[::-1]: 
      count += 1 

    return count 

start = 1000 #some initial number 
end = 10000000000000 #some other large number 

if __name__ == "__main__": 
    print count_palindromes(start, end) 

그것의 각 숫자를 하나씩 확인하는 간단한 프로그램. 그것의 시간은 다양하고 많은 컴퓨터 자원이 필요합니다.

Palindrome 수를 계산할 수있는 다른 방법/기술이 있습니까? 이것에 사용할 어떤 알고리즘?

출력을 생성하는 데 걸리는 시간을 최소화하고 싶습니다.

Answer 1

, 주어진 속성 다소 간단한 문제를 0 및 n 사이가를

얼마나 많은 숫자를 해결하기 위해 종종 유용 ?

하나의 제한을 고정하면 문제를 상당히 쉽게 해결할 수 있습니다. 간단한 문제가 해결되면, 당신은 간단한 뺄셈과 원래의 문제에 대한 해결책을 얻을 수 있습니다 : 한계 countTo에 포함되어있는 한계가 countBetween에 포함되어야한다 여부에 따라

countBetween(a,b) = countTo(b) - countTo(a) 

또는 countTo(b ± 1) - countTo(a ± 1).

제외 한계가 발생할 수있는 경우 (회문 들어, I는 추정되지 않음), countTo(n) 부정적인 n (카운트 척도에 대하여 일체로 기능 간주 할 것)에 대한 <= 0해야한다.

그래서 우리가 첫 번째 부분, 우리가 할 수 있도록 0, 회문 아닌 척하면 우리는 첫 번째 부분에 대한보다 균일 한 공식을 얻을

palindromes_below(n) = #{ k : 0 <= k < n, k is a palindrome } 

확인할 수 있습니다.

1 부 : 숫자가 d 인 회문이 몇 개 있습니까?

첫 번째 숫자는 0 일 수 없습니다. 그렇지 않으면 제한이 없으므로 9 개의 가능한 선택 사항이 있습니다 (임의의 자료에 b).

마지막 자릿수는 첫 번째 자릿수는 첫 번째 자릿수와 같습니다.

d >= 3 인 경우 두 번째 숫자는 첫 번째 숫자와 임의로 독립적으로 선택할 수 있습니다. 그것은 또한 끝에서 두 번째 숫자를 결정합니다.

d >= 5 인 경우 자유롭게 세 번째 숫자를 선택할 수도 있습니다.

순간의 생각 d = 2*k + 1 또는 d = 2*k + 2 대한 제한없이 선택 될 수 k 자리하고 비 제로로 제한 될 한 디지트 (제)가 있다는 것을 나타낸다. 그래서

9 * 10**k 

d -digit 다음 회문 (기본 b에 대한 (b-1) * b**k)이 있습니다.

멋지고 간단한 공식입니다.

• n 경우 짝수 숫자 : 것과 기하학적 합계 수식을 사용하여, 우리는 쉽게 ^N (10) (즉, 최대 n 자리이다)보다 작은 회문 수를 얻을 수있다 n 홀수

  n/2-1    n/2-1 
  2 * ∑ 9*10**k = 18 * ∑ 10**k = 18 * (10**(n/2) - 1)/(10 - 1) = 2 * (10**(n/2) - 1) 
      k=0     k=0 
  

• 경우이며, 숫자는

  2 * (10 ** ((N-1)/2) - 1) + 9 * 10 ** ((N-1)/2) = 11 * (10 ** ((n-1)/2) - 2

(일반베이스의 경우 resp. (b+1) * b**((n-1)/2) - 2). 꽤 균일로 더 이상하지만 아직 충분히 간단한

:

def palindromes_up_to_n_digits(n): 
    if n < 1: 
     return 0 
    if n % 2 == 0: 
     return 2*10**(n//2) - 2 
    else: 
     return 11*10**(n//2) - 2 

(우리가 아직 0을 계산에 포함되지 않습니다 기억).

나머지 부분은 다음과 같습니다.k 자리 n > 0을 감안하면 회문 < n 미만 k 자리 중 하나

• 회문은, 거기에 그들 중 palindromes_up_to_n_digits(k-1), 또는 n보다 작은 정확히 k 자리
• 회문.

그래서 후자를 계산합니다.

2 부 :

하자 m = (k-1)//2 및

d[1] d[2] ... d[m] d[m+1] ... d[k] 

n (전체 물건의 진수 표현은 다른 기지에 대한 동일한 원리로 작동하지만 명시 적으로 그것을 언급하지 않는다 다음)이므로

k 
n = ∑ d[j]*10**(k-j) 
    j=1 

각 1 <= c[1] < d[1]에 대해 우리는 회문

p = c[1] c[2] ... c[m+1] {c[m+1]} c[m] ... c[2] c[1] 

(심지어 k 번씩 홀수 k 대한 두번 나타나는 c[m+1] 디지트를) 얻었다 자유롭게 mc[2], ..., c[m+1] 숫자를 선택할 수있다. 이제

c[1]*(10**(k-1) + 1) <= p < (c[1] + 1)*10**(k-1) <= d[1]*10**(k-1) <= n, 

그래서 모든 (c[1]! 주어진 선택을위한)이 10**m 회문 n보다 작습니다.

따라서 첫 번째 자릿수가 n의 첫 자릿수보다 작은 - 자리 장식 문자가 있습니다.

n보다 작은 첫번째 자릿수 d[1] 인 k- 자리 장식 문자를 고려해 보겠습니다.

k == 2 인 경우 d[1] < d[2] 인 경우 1이 있고 그렇지 않은 경우는 1입니다.

이

d[1]*(10**(k-1) + 1) + c[2]*(10**(k-2) + 10) 
     <= p < d[1]*(10**(k-1) + 1) + (c[2] + 1)*(10**(k-2) + 10) 
     <= d[1]*(10**(k-1) + 1) + d[2]*(10**(k-2) + 10) <= n 

(10 10**(k-2) + 10 교체 k == 3를 들어, k > 3 가정) : k >= 3 경우 각 0 <= c[2] < d[2], 우리는 자유롭게 우리는 p < n를 참조 회문

p = d[1] c[2] c[3] ... c[m] c[m+1] {c[m+1]} c[m] ... c[3] c[2] d[1] 

을 얻기 위해 m-1 자리 c[3] ... c[m+1]를 선택할 수 있습니다.

따라서 d[2]*10**(m-1)k- 첫 번째 숫자는 d[1]이고 두 번째 숫자는 d[2]보다 작습니다.

계속는 1 <= r <= m 대해, 그 제 r 숫자이다 d[1] ... d[r] 및 그 r+1^세인트d[r+1] 자리보다 작은

d[m+1]*10**(m-r) 

k -digit 회문있다.

n의 해당 자릿수 동일

n의 해당 숫자보다 작은 제 m+1 숫자 중 하나가

(d[1]-1])*10**m + d[2]*10**(m-1) + ... + d[m]*10 + d[m+1] 

k -digit 회문 모든 선행 자리 있는데, 합산. 분명히 이들은 모두 n보다 작습니다.

그 첫번째 m+1 자리 d[1] .. d[m+1]입니다 하나 k -digit 회문 p있다, 우리는 너무 경우 p < n을 계산해야합니다.

그래서, 마무리, 지금은 너무 0을 통합, 우리가 얻을

def palindromes_below(n): 
    if n < 1: 
     return 0 
    if n < 10: 
     return n # 0, 1, ..., n-1 

    # General case 
    dec = str(n) 
    digits = len(dec) 
    count = palindromes_up_to_n_digits(digits-1) + 1 # + 1 for 0 
    half_length = (digits-1) // 2 
    front_part = dec[0:half_length + 1] 
    count += int(front_part) - 10**half_length 
    i, j = half_length, half_length+1 
    if digits % 2 == 1: 
     i -= 1 
    while i >= 0 and dec[i] == dec[j]: 
     i -= 1 
     j += 1 
    if i >= 0 and dec[i] < dec[j]: 
     count += 1 
    return count 

(영업 오해하지 않는 한), 우리는 다음

이 한계는 모두 주어진 문제에 대한 계산에 포함 할되기 때문에 빠른 솔루션

def count_palindromes(start, end): 
    return palindromes_below(end+1) - palindromes_below(start) 

는 :

>>> bench(10**100,10**101-1) 
900000000000000000000000000000000000000000000000000 palindromes between 
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 
and 
99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 
in 0.000186920166016 seconds 

Answer 2

이것은 Project Euler와 같은 것으로 가정합니다 ... 나의 대략적인 아이디어는 최대 한도의 절반까지 모든 숫자를 생성하는 것입니다 (예 : 99999로가는 경우 99까지). 그런 다음이를 뒤집어서 되돌릴 수없는 항목에 추가하고 중간에 숫자를 추가하십시오 (홀수 인 경우). 중복 또는 이상한 필터링 (숫자 또는 sommat의 시작 부분에 0이있는 경우처럼)을 필터링해야 할 수도 있지만 그렇게하는 것이 훨씬 빠르게 수행해야합니다.

Answer 3

실제로 Google Codejam (외부 도움을 받기로되어 있지 않다는 것을 확신합니다)에 문제가 있습니다. 아아, 2 센트를 버리 겠습니다.

큰 문제에 대해 생각해 낸 아이디어는 런타임에 생성되어 소스로 하드 코드되지 않고 프리드 립트 (palhandromic numbers)의 목록이 10^15 (매우 많지는 않습니다. ~ 60 초 정도 걸립니다.) 그런 다음 얼마나 많은 숫자가 각 입력 범위 사이에 있는지 알아보십시오.

편집 : 당신이 말했듯이 이것은 10^100 문제에서 작동하지 않습니다. 수학적 해결책이 될 것입니다. (보니 패턴이 있지만, 모든 숫자를 생성하는 알고리즘이 필요합니다. 패턴) 두 한계 사이에 주어진 특성을 갖는 숫자를 카운트 할