Злым числом в математике называется неотрицательное целое число с чётным числом единиц в его двоичной записи (например, число 5 — злое, в его двоичной записи две единицы). Они используются в теории чисел при исследовании последовательности Морса‑Туэ и применяются в алгоритмах фрактального сжатия изображений.
Натуральное число будем называть очень злым, если само оно чётное и количество единиц в его двоичной записи также чётное. Это такие числа, как 6, 10, 12, 18, 20 и так далее.
По данному n определите количество очень злых чисел, не превосходящих n.
1 Ответ
Для решения этой задачи можно использовать следующий алгоритм:
1. Инициализируйте счетчик очень злых чисел равным 0.
2. Пройдите по всем неотрицательным целым числам от 0 до n-1.
3. Если текущее число является очень злым (то есть оно четное и количество единиц в двоичной записи четно), увеличьте счетчик очень злых чисел на 1.
4. Вернитесь к шагу 2.
Таким образом, мы пройдемся по всем очень злым числам, не превосходящим n, и посчитаем их количество.
(defun count-evil-numbers (n)
(let ((evil-count 0))
(dotimes (i n)
(let ((binary-representation (logand i 0x3fffffff)))
(if (or (zerop (remainder binary-representation 2)) (evenp (length binary-representation)))
(incf evil-count)
nil)))
evil-count))