Простенькая задачка на питоне с комбинаторикой
Всем привет, подскажите пожалуйста оптимизированный алгоритм на питоне, который определяет сколько чисел в промежутке от 1 до 10**9 имеют ровно два нуля в своей двоичной записи. Простой перебор не катит :)
Ответы (1 шт):
Автор решения: Harry
→ Ссылка
Ладно, раз пошла такая пьянка и уже начали отвечать, невзирая на учебность задания...
Итак, n-значное число. Первая цифра - от 1 до 9, 9 вариантов.
В следующих n-1 знакоместах два нуля размещаются C_{n-1}^2 способами, сиречь
(n-1)!/2!/(n-3)! = (n-1)*(n-2)/2
В оставшиеся n-3 мест размещаем цифры от 1 до 9 9^(n-3) способами.
Итого - сумма
9^(n-2)*(n-1)*(n-2)/2
Для n от 3 (можно и от 1, обнулится...) до 9.
total = 0
for n in range(1,10):
total = total + 9**(n-2)*(n-1)*(n-2)/2
print(total)
Как оптимизировать эти 4 строчки? Ну разве что до
print(146039364)