Вопрос:

Нужно найти эффективный способ найти Сильное число

python python-3.x list

55 просмотра

6 ответа

23 Репутация автора

Написал программу для поиска Сильного числа

Число считается сильным числом, если сумма факториала его цифр равна самому числу. 145 - Сильное число, равное 1! + 4! + 5! = 145

Нужно принять список, найти сильный номер среди списка и вернуть список

Я пробовал :

def factorial(number):
    if number == 0 or number == 1:
        return 1
    else :
        return number * factorial(number - 1)


def find_strong_numbers(num_list):
    sum = 0
    ret_list = []
    for i in num_list :
        sum = 0
        lst = list(map(int,list(str(i))))   #Converting the number into a list of numbers
        for j in lst :
            sum += factorial(j)
        if sum == i :
            ret_list.append(i)
    return ret_list

num_list=[145,375,100,2,10]
strong_num_list=find_strong_numbers(num_list)
print(strong_num_list)

В приведенном выше примере я создал список цифр числа и нашел его факториал. Но,

def factorial(number):
    if number == 0 or number == 1:
        return 1
    else :
        return number * factorial(number - 1)


def find_strong_numbers(num_list):
    sum = 0
    ret_list = []
    for i in num_list :
        sum = 0
        lst = list(str(i))   #A List of Strings of the digits
        for j in lst :
            sum += factorial(int(j))
        if sum == i :
            ret_list.append(i)
    return ret_list

num_list=[145,375,100,2,10]
strong_num_list=find_strong_numbers(num_list)
print(strong_num_list)

Я создал список строк цифр в числе. Преобразовал строку в число при вызове функции факториала. Это кажется эффективным для меня, так как мне не нужно конвертировать его в карту, а затем в int (меньше конвертации)

Правильно ли это, эффективно ли это по сравнению с предыдущим или какой-либо гораздо более оптимизированный код, чем этот, чтобы найти Strong Number?

Автор: Siva Rahul Источник Размещён: 11.08.2019 07:25

Ответы (6)


3 плюса

173631 Репутация автора

  1. Вы можете просто запомнить factorialфункцию, чтобы ускорить обработку

    from functools import lru_cache
    
    @lru_cache(maxsize=128)
    def factorial(number):
        if number <= 1:
            return 1
        else:
            return number * factorial(number - 1)
    
  2. Кроме того, вы можете использовать генератор, чтобы получить следующую цифру, как это

    def get_next_digit(num):
        while num:
            yield num % 10
            num //= 10
    
    print(sum(factorial(digit) for digit in get_next_digit(145)))
    

    Это позволяет избежать создания прерывистого списка строк.


PS: Это незначительные оптимизации, которые не могут значительно улучшить производительность программы.

Общий код

from functools import lru_cache


@lru_cache(maxsize=128)
def factorial(number):
    if number <= 1:
        return 1
    else:
        return number * factorial(number - 1)


def get_next_digit(num):
    while num:
        yield num % 10
        num //= 10


def is_strong_number(num):
    return sum(factorial(digit) for digit in get_next_digit(num)) == num


def find_strong_numbers(num_list):
    return [num for num in num_list if is_strong_number(num)]


num_list = [145, 375, 100, 2, 10]
print(find_strong_numbers(num_list))
Автор: thefourtheye Размещён: 11.08.2019 07:36

1 плюс

17927 Репутация автора

Другая версия, использующая встроенный math.factorial( doc ):

from math import factorial

def is_strong_number(num):
    return num == sum(factorial(int(c)) for c in str(num))

num_list=[145,375,100,2,10]
strong_num_list = [num for num in num_list if is_strong_number(num)]
print(strong_num_list)

Печать:

[145, 2]
Автор: Andrej Kesely Размещён: 11.08.2019 07:38

1 плюс

358 Репутация автора

Есть несколько вещей, которые вы можете сделать.

Первое, что приходит на ум, - это сделать factorialфункцию итеративной, а не рекурсивной:

def factorial(number):
    if number == 0 or number == 1:
        return 1

    result = 1

    for i in range(number + 1):
        result *= i

    return result

Вторым будет предварительное вычисление всех факториалов для каждой цифры, поскольку их количество ограничено:

def get_factorials():
    result = [1, 1]

    value = 1
    for i in range(2, 10):
        value *= i
        result.append(value)

    return result

Тогда вместо того, чтобы звонить factorialкаждый раз, вы можете просто сделать:

factorials = get_factorials()

lst = list(str(i))
for j in lst :
  sum += factorials[int(j)]

Ваша функция результата может быть такой простой:

def is_strong_number(num):
    return num == sum(map(lambda x: factorials[int(x)], str(num))

def find_strong_numbers(nums):
    factorials = get_factorials()
    return [num for num in nums if is_strong_number(num)]

Редактировать: спасибо khelwood , исправлено :)

Автор: Šimon Kocúrek Размещён: 11.08.2019 07:39

1 плюс

6156 Репутация автора

другие уже предложили улучшения в своих ответах,

просто для демонстрации более эмпирического подхода к сравнительному анализу времени выполнения:

Вы можете использовать timeitдля сравнения времени выполнения различных функций.

Я добавил обе ваши, а также версию, которая вообще не выполняет приведение строки <-> int.

import timeit


def factorial(number):
    if number == 0 or number == 1:
        return 1
    else:
        return number * factorial(number - 1)


def find_strong_numbers_with_map(num_list):
    sum = 0
    ret_list = []
    for i in num_list:
        sum = 0
        lst = list(map(int, list(str(i))))  # Converting the number into a list of numbers
        for j in lst:
            sum += factorial(j)
        if sum == i:
            ret_list.append(i)
    return ret_list


def find_strong_numbers_cast_on_call(num_list):
    sum = 0
    ret_list = []
    for i in num_list:
        sum = 0
        lst = list(str(i))  # A List of Strings of the digits
        for j in lst:
            sum += factorial(int(j))
        if sum == i:
            ret_list.append(i)
    return ret_list


def find_strong_numbers_by_div_mod(num_list):
    sum = 0
    ret_list = []
    for i in num_list:
        sum = 0
        while i > 0:
            j = i % 10  # get the value of the last digit
            sum += factorial(int(j))
            i = i // 10  # "cut" the last digit from i
        if sum == i:
            ret_list.append(i)
    return ret_list


num_list = [*range(1, 1000)]
print(timeit.timeit(lambda: find_strong_numbers_with_map(num_list), number=10 ** 3))
print(timeit.timeit(lambda: find_strong_numbers_cast_on_call(num_list), number=10 ** 3))
print(timeit.timeit(lambda: find_strong_numbers_by_div_mod(num_list), number=10 ** 3))

Результаты на моем ноутбуке:

2.4222552359969995
2.114583875001699
1.8628507399989758
Автор: Adam.Er8 Размещён: 11.08.2019 07:40

2 плюса

163061 Репутация автора

Поскольку вы используете только факториалы 0..9, вам не нужно иметь функцию для их вычисления, не говоря уже о рекурсивной. Вы можете просто жестко закодировать все 10 значений:

facts = {'0': 1, '1': 1, '2': 2, '3': 6, '4': 24, '5': 120, '6': 720, '7': 5040, '8': 40320, '9': 362880}

а затем просто используйте:

def is_strong(n):
    return sum(facts[s] for s in str(n)) == n

Вы можете выжать немного больше циклов, избегая преобразования строк:

facts2 = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

def is_strong2(n):
    s, k = 0, n
    while k:
        s += facts2[k % 10]
        k //= 10
    return s == n

... но , учитывая тот факт , что это доказано нет таких чисел ряда 1, 2, 145, 40585, целое предприятие выглядит немного бессмысленно;)

Автор: georg Размещён: 11.08.2019 07:53

0 плюса

10309 Репутация автора

Вы можете кэшировать в словаре факториал, соответствующий каждому возможному символу цифры

digits = '0123456789'
facts = [1]
for i in range(1,10): facts.append(facts[-1]*i)
d2f = dict(zip(digits, facts))

тогда вы можете легко проверить, является ли число сильным (здесь мы используем строковое представление числа)

num = '145'
str(sum(d2f[c] for c in num)) == num

Вы можете определить функцию для проверки (теперь числа являются целыми числами)

strong_p = lambda n: sum(d2f[c] for c in str(n)) == n

for i in range(1500000):
      if strong_p(n) : print(n)
# 1, 2, 145, 40585

У меня есть время для проверки первых 1500000 целых чисел:
2.37 s ± 7.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Автор: gboffi Размещён: 11.08.2019 08:17
Вопросы из категории :
32x32