top of page
РЕШЕНИЕ ЗАДАЧ
ПОСИМВОЛЬНОЕ ДВОИЧНОЕ ПРЕОБРАЗОВАНИЕ

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:

    а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
    б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2

 

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

​

Решение:

Определим какими могут быть два последних разряда числа R:

  • если сумма разрядов числа нечетная (например, для 11100 сумма 3), то на первом шаге в конец записи числа будет добавлена 1 (получим 111001). Теперь сумма разрядов равна 4, значит на втором шаге в конец записи числа добавляем 0 (получим 1110010).

  • если сумма разрядов числа четная (например, для 1100 сумма 2), то на первом шаге в конец записи числа будет добавлен 0 (получим 11000). Сумма разрядов не изменилась, значит на втором шаге в конец записи числа снова добавляем 0 (получим 110000).

Таким образом,  окончанием числа может быть либо 10 (если сумма разрядов исходного числа нечетная), либо 00 (если сумма разрядов исходного числа N четная).

​

Рассмотрим числа, большие 83 в двоичной системе счисления. Найдем меньшее число, которое является результатом работы алгоритма.

84 -- 1010100, исходное число 10101, сумма разрядов нечетная, значит окончание записи должно быть 10. Вывод: 1010100 не является результатом работы алгоритма.

Аналогично:

85 = 1010101 — не является результатом работы алгоритма.

86 = 1010110 — является результатом работы алгоритма для числа 10101.

Таким образом, искомое число — 86.

Ответ: 86

ДОПОЛНИТЕЛЬНЫЕ  ЗАДАЧИ

1. Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 6 (если в числе есть цифра больше 6, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.

1) Вычисляются два шестнадцатеричных числа – сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.

2) Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходные числа: 66, 43. Поразрядные суммы: A, 9. Результат: 9A.

Определите, какое из предложенных чисел может быть результатом работы автомата.

1) 9F          2) 911          3) 42          4) 7A

​

2. Автомат получает на вход четырехзначное десятичное число. По этому числу строится новое число по следующим правилам.

1. Складываются первая и вторая, а также третья и четвёртая цифры.

2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходное число: 8754. Суммы: 8 + 7 = 15; 5 + 4 = 9. Результат: 915. Определите, какое из следующих чисел может быть результатом работы автомата.

1) 219          2) 118          3) 1411          4) 151

​

3. Автомат по­лу­ча­ет на вход пя­ти­знач­ное число. По этому числу стро­ит­ся новое число по сле­ду­ю­щим правилам.

1. Скла­ды­ва­ют­ся от­дель­но первая, тре­тья и пятая цифры, а также вто­рая и четвёртая цифры.

2. По­лу­чен­ные два числа за­пи­сы­ва­ют­ся друг за дру­гом в по­ряд­ке не­убы­ва­ния без разделителей.

Пример. Ис­ход­ное число: 63 179. Суммы: 6 + 1 + 9 = 16; 3 + 7 = 10. Результат: 1016.

Укажите наименьшее число, при обработке которого автомат выдаёт результат 621.

​

4. Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.

1. Скла­ды­ва­ют­ся от­дель­но пер­вая и вто­рая цифры, вто­рая и тре­тья цифры, а также тре­тья и четвёртая цифры.

2. Из по­лу­чен­ных трёх чисел вы­би­ра­ют­ся два наи­боль­ших и за­пи­сы­ва­ют­ся друг за дру­гом в по­ряд­ке не­убы­ва­ния без разделителей.

Пример. Исходное число: 9575. Суммы: 9+5 = 14; 5+7 = 12; 7+5=12. Наибольшие суммы: 14, 12. Результат: 1214.

Укажите наибольшее число, при  обработке которого автомат выдаёт результат 1515.

bottom of page