|
Бинарные числа
(Время: 1 сек. Память: 16 Мб Сложность: 8%)
Следует заметить, что существует всего 14 бинарных чисел в указанном диапазоне: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 и 8192. Поэтому наиболее простым и понятным решением является проверка заданного числа на бинарность с использованием единственного условного оператора. Тогда решение задачи выливается в простую алгоритмическую запись:
read(n)
if(n=1 or n=2 or n=4 or n=8 or n=16 or n=32 or n=64 or n=128 or n=256 or n=512 or
n=1024 or n=2048 or n=4096 or n=8192) write('YES'); else write('NO')
Другое решение заключается в попытке деления числа на 2 до тех пор пока оно делится. В результате, если получается 1, то число бинарное, в противном случае оно таковым не является. Наиболее оптимальным решением будет реализация с использованием формулы n and (n-1), которая позволяет обнулить младший бит, равный единице; если в результате этой операции из натурального числа n получается 0, то число является степенью двойки. Здесь надо учесть, что для целых чисел 0 может получаться при n=0, для чего необходима дополнительная проверка:
read(n)
if((n>0 and (n and (n-1) = 0)) write('YES'); else write('NO')
| |
