≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 6 № 17370

Автомат обрабатывает натуральное число N по следующему алгоритму:

1. Строится двоичная запись числа N.

2. Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.

3. Полученное число переводится в десятичную запись.

4. Новое число вычитается из исходного, полученная разность выводится на экран.

Пример. Дано число N = 11. Алгоритм работает следующим образом.

1. Двоичная запись числа N: 1011.

2. Удаляется первая единица и следующий за ней ноль: 11.

3. Десятичное значение полученного числа 3.

4. На экран выводится число 11 – 3 = 8.

 

Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 100 до 3000?

Пояснение.

Заметим, что при удалении первой единицы и всех стоящих сразу за ней нулей из числа вычитается 2 в степени, равной номеру старшего разряда в двоичной записи числа. Значит, нужно найти количество степеней двойки, которые находятся между 100 и 3000. Также необходимо учесть, что числа от 100 до 128 будут соответствовать предыдущей степени двойки. Значит, к количеству степеней двойки, входящих в диапазон чисел от 100 до 3000, необходимо добавить единицу. Всего в диапазоне от 100 до 3000 пять степеней двойки. Следовательно, будет показано 5 + 1 = 6 различных чисел.

 

Ответ: 6.