3. Кол-во 0 в конце n!

Created Friday 10 October 2014

https://www.youtube.com/watch?v=i5Y-BHFJXQg

Вход: целое число n
Выход: кол-во нулей в конце n!

f(2) = 0 — 1 * 2 = 2
f(5) = 1 — 1 * 2 * 3 * 4 * 5 = 120
f(8) = 1 — 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 40320
f(10) = 2 — 3628800

Решение 1

1 — Вычислить n!
2 — Посчитать нули

Не эффективно ни по времени, ни по памяти

Решение 2

2! = 1 * 2 = 2
3! = 1 * 2 * 3 = 6
4! = 1 * 2 * 3 * 4 = 24
5! = 1 * 2 * 3 * 5 = 120
.....
10! = ... = 3628800

Предположение: Кол-во нулей в n! = кол-ву цифр среди 1 .. n, которые деляться на 5 (25 делится на 5 2 раза!)

Для каждого х из чисел 1 .. n
t += кол-во раз, таких что х дел-ся на 5 без остатка
return t

Решение 3

Кол-во чисел 1 .. n, кот-е дел-ся на 5 без остатка = n / 5 округлённое в меньшую сторону

Пока n/5 окр. вниз > 0: t += n/5 окр. вниз, n = n/5



Backlinks: