Как я могу получить сумму номеров Palindromi c с указанными условиями c?

Question

Я должен написать программу, чтобы получить сумму всех чисел палиндромов c N di git, и эти числа палиндромов c не должны содержать в себе 0 и также должны быть кратны 9? У меня есть код, который я написал в python, и для небольших значений N он, кажется, работает нормально, но он не работает для больших чисел, а также требуется много времени для выполнения для больших значений N. Может ли кто-нибудь помочь найти лучшую логику c для этого, а также работает для больших значений N? Заранее спасибо

def getSum(N):
 sum=0
 first=pow(10,N-1)
 last=pow(10,N)
 for i in range(first,last):
  if(i%9==0):
   if(palindrome(i)):
    sum+=i
return sum%(pow(10,9)+7)

def palindrome(num):
 rev=0
 n=num
 while(n>0):
  rem=n%10
  if(rem==0):
   return False
  rev=(rev*10)+rem
  n=n//10

 if(num==rev):
  return True
 else:
  return False

def main():
 N=int(input("Enter the value of N "))
 result = getSum(N)
 print(result)

if __name__ == '__main__':
 main()

Answer 1

Это ни в коем случае не оптимизированное решение, и оно адаптировано из вашей идеи с несколькими исключениями. Во-первых, вместо того, чтобы рассматривать каждое число от первого до последнего, начните с первого кратного 9 и последнего кратного 9 и учитывайте только кратные девять. Это можно сделать с помощью функции диапазона range(first,last,multiple). Следующим является то, что палиндромы могут быть найдены просто путем сравнения перевернутой строки. Ваши ограничения - нет 0 и палиндромы. Так что быстро приведите тип к строке, сравните обратное и проверьте на ноль. С другой стороны, это приложение всегда будет дороже, так как число становится больше, потому что вам нужно go через список из приблизительно 10 ^ (N + 1) -10 ^ N чисел.

def palSum(N):
    multiple = 9
    #Find lower limit
    minBound = multiple*((10**(N-1))//multiple)
    minBound += multiple if len(str(minBound))< N else 0
    #Find upper limit
    maxBound = multiple*((10**(N))//multiple)
    maxBound += multiple if len(str(maxBound))<N+1 else 0
    #Get sum
    sum = 0
    for num in range(int(minBound),int(maxBound),multiple):
        nstr = str(num)
        if '0' not in nstr and nstr[::-1]==nstr:
            sum+=num
    return sum

В настоящее время я провожу быстрый эксперимент по синхронизации с N=10. Я опубликую результаты, когда они будут завершены:

if __name__ == "__main__":
    N = 10
    s1 = time.time()
    print(getSum(N)) #Original
    s2 = time.time()
    print(palSum(N)) #New
    s3 = time.time()
    print(s2-s1,s3-s2)

Результаты были:

Оригинал: 1859,58 секунды

Новое: 277,11 секунды

Если вам нужно больше производительности, вы могли бы рассмотреть подход параллельного программирования с сокращением (параллельная сумма). Надеюсь, это поможет.