Как определить числа в составе списка, сумма цифр которых равна N?
Дан список, состоящий из чисел от 1 до 1000. Необходимо определить все числа, цифры которых в сумме дают 13 (67, 76, 931 и т.д.). Понимаю, как это реализовать, если бы было дано одно число (1000, скажем), но в рамках списка непонятно. Пробуй следующий код, но безрезультатно:
n=[i for i in range(1001)]
res=[0 for k in range(1001)]
for i in n:
while i:
a=i%10
i=i//10
res[k]+=a
if res[k] == 13:
print(i)
Ответы (3 шт):
res
делайте просто числом, не массивом, обнуляйте на каждой итерации. На каждой итерации копируйте i
в t
, и далее работайте с t
, чтобы счётчик цикла не менять
n=[i for i in range(1001)]
# или просто for i in range(1001): ?
for i in n:
t = i
res = 0
while t:
res += t%10
t //= 10
if res == 13:
print(i)
Если диапазон будет больше, то стоит подумать об оптимизации - не проверять все числа, а просто генерировать те числа, для которых сумма цифр равна требуемой
Просто как ещё один вариант эта задача решается короче с использованием встроенных функций питона (но менее оптимально, поскольку работа со строками медленнее, чем работа с числами):
for i in range(1001):
if sum(map(int, str(i))) == 13:
print(i)
Или даже в одну строку тот же по сути код:
print(*(i for i in range(1001) if sum(map(int, str(i))) == 13), sep='\n')
Или другой однострочник:
print(*filter(lambda x: sum(map(int, str(x))) == 13, range(1001)), sep='\n')
А ведь отличная задача!
Перебор и проверка хорошо работают для небольших n, но можно заметить, что чисел с суммой цифр тринадцать немного. Если в числе ровно k разрядов, то таких чисел не более Сk+1112, что составляет лишь (бесконечно) малую долю от общего количества чисел 9·10k-1. А раз так, то их надо уметь находить без последовательного перебора всех чисел.
Конструировать числа будем последовательно увеличивая их разрядность k - генератор search(k, s, n, d1)
. Сами числа конструируются от старших разрядов к младшим. При добавлении разряда обновляется s - доступный остаток суммы цифр и n - само число.
Генератор search
бесконечный, последовательно вызывает search(k, ...)
увеличивая k. Функция main
останавливает его, когда очередное число превысило порог.
def search(ss):
def search(k, s, n, d1):
if k == 0:
yield n
min_d = max(d1, s - 9 * (k - 1))
max_d = min(9, s)
for d in range(min_d, max_d + 1):
yield from search(k - 1, s - d, 10 * n + d, 0)
k = 1
while True:
yield from search(k, ss, 0, 1)
k += 1
def main():
s, n = map(int, input().split())
for i in search(s):
if i > n:
break
print(i)
main()
$ time echo 13 1_000 | python temp.py | wc -l 75 real 0m0.030s user 0m0.028s sys 0m0.000s
Прогоны для суммы цифр - тринадцать:
n | время работы | количество чисел |
---|---|---|
103 | 0.03 с | 75 |
104 | 0.03 с | 480 |
105 | 0.04 с | 2205 |
106 | 0.05 с | 8232 |
107 | 0.1 с | 26544 |
108 | 0.3 с | 76560 |
109 | 0.6 с | 202005 |
1010 | 1.5 с | 495220 |
1011 | 3.5 с | 1140920 |
1012 | 8.0 с | 2491776 |
1013 | 17.3 с | 5194385 |
1014 | 35.7 с | 10392760 |
1015 | 71.0 с | 20048100 |
1016 | 143 с | 37429104 |
1017 | 311 с | 67847442 |
1018 | 510 с | 119739330 |