Задание 6. Алгоритмы для формальных исполнителей: все задания

Ответом к заданию по информатике может быть целое число, десятичная дробь (записывайте её через запятую, вот так: 2,5), последовательность цифр или букв (пишите без пробелов: 97531).

Версия для печати

Остальные задачи

1. Задание#T785

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

Строится двоичная запись числа .
К этой записи дописываются справа ещё два разряда по следующему правилу: если чётное, в конец числа (справа) дописывается сначала ноль, а затем единица. В противном случае, если нечётное, справа дописывается сначала единица, а затем ноль.
Например, двоичная запись числа будет преобразована в , а двоичная запись числа будет преобразована в .

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

Укажите минимальное число , которое больше

и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Показать разбор и ответ

Добавление нуля в конце двоичной записи соответствует умножению исходного числа на , а добавление единицы умножению на два и прибавлению к результату единицы. Таким образом,

в случае чётного и

в случае нечётного .

Проверим число

. Оно нечётное, то есть могло быть получено лишь по формуле

. Решая уравнение, получим

, что противоречит условиям задачи.

Проверим число

. Оно чётное, то есть могло быть получено лишь по формуле

. Решая уравнение, также получим дробное значение

Проверим число

. Оно нечётное, следовательно

, откуда

.
Таким образом, найденное число

и оно могло быть получено в~результате работы автомата из числа

Ответ: 105

Это задание взято из демовариантов ФИПИ 2018-2020

Это задание решали 6 тыс. раз. С ним справились 49% пользователей.

2. Задание#T2321

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

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

Пример. Исходное число:

. Результат: .

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

Показать ответ

Это задание составил Дмитрий Богданов специально для Яндекса

Это задание решали 4 тыс. раз. С ним справились 38% пользователей.

3. Задание#T4817

Автомат обрабатывает натуральное число

по следующему алгоритму.

Строится двоичная запись числа .
Последняя цифра двоичной записи удаляется.
Если исходное число было нечётным, в конец записи (справа) дописываются цифры , если чётным – .
Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число

. Алгоритм работает следующим образом.

Двоичная запись числа : .
Удаляется последняя цифра, новая запись: .
Исходное число нечётно, дописываются цифры , новая запись: .
На экран выводится число .

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

Показать разбор и ответ

Указание:

Двоичная запись нечётных чисел заканчивается единицей, чётных – нулём; при добавлении нуля в конце двоичной записи число удваивается.

Решение:

У нечётного числа автомат удаляет последнюю единицу в двоичной записи, после чего добавляет . Фактически к записи просто добавляется , то есть число удваивается и становится чётным. Аналогично для чётных чисел к записи добавляется , то есть число удваивается и увеличивается на и становится нечётным.

Чётное число

получается удвоением нечётного числа

Ответ: 1009

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 4 тыс. раз. С ним справились 47% пользователей.

4. Задание#T4844

Автомат обрабатывает натуральное число

по следующему алгоритму.

Строится двоичная запись числа .
Последняя цифра двоичной записи удаляется.
Если исходное число было нечётным, в конец записи (справа) дописываются цифры , если четным – .
Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число

. Алгоритм работает следующим образом.

Двоичная запись числа : .
Удаляется последняя цифра, новая запись: .
Исходное число нечётно, дописываются цифры , новая запись: .
На экран выводится число .

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

Показать разбор и ответ

Указание:

Решение:

Нечётное число

получается из чётного числа

Ответ: 1008

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 3 тыс. раз. С ним справились 54% пользователей.

5. Задание#T4871

Автомат обрабатывает натуральное число

по следующему алгоритму:

Строится восьмибитная двоичная запись числа .
Все цифры двоичной записи заменяются на противоположные ( на , на ).
Полученное число переводится в десятичную запись.
Из нового числа вычитается исходное, полученная разность выводится на экран.

Пример. Дано число

. Алгоритм работает следующим образом:

Восьмибитная двоичная запись числа : .
Все цифры заменяются на противоположные, новая запись .
Десятичное значение полученного числа .
На экран выводится число .

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

Показать разбор и ответ

Указание:

Найдите сумму исходного и нового числа.

Решение:

Сумма исходного и нового числа в двоичном виде записывается восемью единицами, это соответствует десятичному числу

. Значит, новое число равно

, а итоговое число, которое выдаёт автомат, равно

Известно, что

, отсюда следует, что

Ответ: 72

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 3 тыс. раз. С ним справились 48% пользователей.

6. Задание#T4898

Автомат обрабатывает натуральное число

по следующему алгоритму:

Строится восьмибитная двоичная запись числа .
Все цифры двоичной записи заменяются на противоположные ( на , на ).
Полученное число переводится в десятичную запись.
Из нового числа вычитается исходное, полученная разность выводится на экран.

Пример. Дано число

. Алгоритм работает следующим образом:

Восьмибитная двоичная запись числа : .
Все цифры заменяются на противоположные, новая запись .
Десятичное значение полученного числа .
На экран выводится число .

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

Показать разбор и ответ

Указание:

Найдите сумму исходного и нового числа.

Решение:

. Значит, новое число равно

, а итоговое число, которое выдаёт автомат, равно

Известно, что

, отсюда следует, что

Ответ: 61

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 4 тыс. раз. С ним справились 53% пользователей.

7. Задание#T8637

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

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

Пример. Исходные числа:

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

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

Показать ответ

Это задание решали 1 тыс. раз. С ним справились 33% пользователей.

8. Задание#T9287

Автомат обрабатывает натуральное число (

) по следующему алгоритму:

Строится восьмибитная двоичная запись числа .
Все цифры двоичной записи заменяются на противоположные ( на , на ).
Полученное число переводится в десятичную запись.
Из полученного числа вычитается исходное, разность выводится на экран.

Пример. Дано число

. Алгоритм работает следующим образом:

Восьмибитная двоичная запись числа : .
Все цифры заменяются на противоположные, новая запись: .
Десятичное значение полученного числа: .
На экран выводится число: .

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

Показать разбор и ответ

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

Легко заметить, что двоичная запись суммы

состоит из единиц (так как в каждом из восьми разрядов складывается либо и , либо и ). В десятичной системе счисления эта сумма равна

Таким образом, имеется следующая система уравнений:

Вычитая из первого уравнения второе, получим

, откуда

Ответ: 51

Это задание составил Дмитрий Богданов специально для Яндекса

Это задание решали 837 раз. С ним справились 67% пользователей.

9. Задание#T9787

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

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

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