Правило: Если от двоичного числа отбросить младший разряд, то оно разделится на 2 целочисленным образом (т.е. делим на 2, если есть остаток, убираем его).
Задание 5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1001 числа 9 будет преобразована в 100111.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа – результата работы данного алгоритма.
Укажите минимальное число N, для которого результат работы алгоритма будет больше 115. В ответе это число запишите в десятичной системе счисления.
Решение.
Переведем число 11510 в двоичную систему: 11510 = 11100 112. На выходе должно быть число большее, чем 11510. Уберём из числа 11100 112 два правых разряда. Получим число 111002 = 28. Это число не подходит, поскольку, если следовать алгоритму, получится число 112 меньше 115. Возьмём число 2910 = 111012. Следуя алгоритму, проверим это число на чётность. Число 29 является нечётным, следовательно, добавим к двоичной записи числа 29 две единицы справа. Получим 11101112 = 11910.
Таким образом, минимальное число N, для которого результат работы алгоритма будет больше 115, равняется 29.
Ответ: 29.
Еще один вариант подобной задачи (более подробное решение):
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше 97. В ответе это число запишите в десятичной системе счисления.
|
|
|
Решение:
У нас на вход поступает натуральное (обычное, не дробное, положительное) число N.
Рассмотрим первое правило формирование выходного числа. На выходе получается двоичная запись числа N. Нарисуем схематично первое правило формирования выходного числа.
Рассмотрим теперь второе правило формирования числа. Сказано, что дописываются два разряда справа к тому двоичному числу, которое получили в первом пункте.
Про первый дополнительный разряд написано в пункте a второго правила: "складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001".
|
|
|
Если сказать более просто, то автомат подсчитывает количество единиц у первоначального двоичного числа N, полученного в первом пункте. Если количество чётное, то автомат в первый дополнительный разряд должен поставить 0. Если количество нечётное, то автомат в первый дополнительный разряд должен поставить 1.
Про второй дополнительный разряд сказано в пункте б второго правила. Автомат сделает тоже самое, что и в предыдущем пункте, только теперь подсчёт единиц будет происходить не только в двоичной записи числа N, но и в первом дополнительном разряде.
В вопросе просят указать входящее наименьшее число N, чтобы автомат выдал число R больше 97.
Т.к. число R должно быть больше 97, то переведём число 98 (97 + 1) в двоичный вид, чтобы можно было оценить входящее число N.
Получилось число 1100010. Будем рассматривать (начиная с 1100010) числа на выполнение правил, которые заданы для автомата. Если все правила будут выполнены, значит, мы получили то число, по которому вычислим изначальное N. Нам нужно получить именно минимальное число, поэтому мы и начали с минимального возможного претендента для числа R (98).
|
|
|
Видим, что подходит число 1100110. В части числа, которая является двоичным представлением N, количество единиц равно 3. Число 3 нечётное, значит, в первом дополнительном разряде должна стоять 1 (единица).
Проверим второй дополнительный разряд. Теперь считаем единицы не только в двоичном представлении числа N, но так же и в первом дополнительном разряде! Количество единиц равно 4. Число 4 чётное. Значит, во втором дополнительном разряде должен стоять 0 (ноль). Все правила работы автомата выполняются в числе 1100110.
Чтобы найти искомое число N, отбросим два дополнительных разряда от найденного 1100110.
Правило: Если от двоичного числа отбросить младший разряд, то оно разделится на 2 целочисленным образом (т.е. делим на 2, если есть остаток, убираем его).
Найдём полученное минимальное число R 1100110 в десятичном представлении. Число 1100010 - 98, 1100011 - 99, 1100100 - 100, 1100101 - 101, 1100110 - 102.
Уберём второй дополнительный разряд у числа 1100110, получается 102 / 2 = 51 (110011). Уберём ещё и первый дополнительный разряд , получается 51 / 2 = 25 (11001).
Значит двоичное представление искомого числа N равно 11001, а десятичное 25.
Ответ: 25.
Дата добавления: 2022-11-11; просмотров: 29; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!