Задание 6. Алгоритмы для формальных исполнителей: все задания
Ответом к заданию по информатике может быть целое число, десятичная дробь (записывайте её через запятую, вот так: 2,5), последовательность цифр или букв (пишите без пробелов: 97531).
Автомат обрабатывает натуральное число () по следующему алгоритму:
Строится восьмибитная двоичная запись числа
Все цифры двоичной записи заменяются на противоположные ( на на ).
Полученное число переводится в десятичную запись.
Из исходного числа вычитается полученное, разность выводится на экран.
Пример. Дано число Алгоритм работает следующим образом:
Восьмибитная двоичная запись числа :
Все цифры заменяются на противоположные, новая запись:
Десятичное значение полученного числа:
На экран выводится число:
Какое число нужно ввести в автомат, чтобы в результате получилось
Показать разбор и ответ
Сумма исходного и нового числа в двоичном виде записывается восемью единицами, это соответствует десятичному числу Значит, новое число равно а итоговое число, которое выдаёт автомат, равно
Известно, что отсюда следует, что
Ответ: 220
Это задание составили эксперты «СтатГрада» для Яндекса
Это задание решали 9 тыс. раз. С ним справились 71% пользователей.
Автомат обрабатывает натуральное число () по следующему алгоритму:
Строится восьмибитная двоичная запись числа
Все цифры двоичной записи заменяются на противоположные ( на на ).
Полученное число переводится в десятичную запись.
Из исходного числа вычитается полученное, разность выводится на экран.
Пример. Дано число Алгоритм работает следующим образом:
Восьмибитная двоичная запись числа :
Все цифры заменяются на противоположные, новая запись:
Десятичное значение полученного числа:
На экран выводится число:
Какое число нужно ввести в автомат, чтобы в результате получилось
Показать разбор и ответ
Сумма исходного и нового числа в двоичном виде записывается восемью единицами, это соответствует десятичному числу Значит, новое число равно а итоговое число, которое выдаёт автомат, равно
Известно, что отсюда следует, что
Ответ: 180
Это задание составили эксперты «СтатГрада» для Яндекса
Это задание решали 6 тыс. раз. С ним справились 77% пользователей.
Автомат обрабатывает натуральное число по следующему алгоритму:
Строится двоичная запись числа без ведущих нулей.
Если в полученной записи единиц больше, чем нулей, то справа приписывается единица. Если нулей больше или нулей и единиц поровну, справа приписывается ноль.
Полученное число переводится в десятичную запись и выводится на экран.
Пример. Дано число Алгоритм работает следующим образом:
Двоичная запись числа :
В записи больше единиц, справа приписывается единица:
На экран выводится десятичное значение полученного числа
Какое наименьшее число, превышающее может получиться в результате
работы автомата?
Показать разбор и ответ
Автомат приписывает к любому числу одну двоичную цифру. Значит, для любого числа, которое может получиться в результате работы автомата, можно узнать исходное число: для этого нужно перевести результат в двоичную систему и отбросить последнюю цифру.
Наименьшее число, большее равно
это число может получиться только из
Но в двоичной записи этого числа нулей больше, чем единиц, значит, по
правилам работы автомата приписывается ноль и преобразуется в Тогда результат больше получится при обработке следующего числа: преобразуется в
Ответ: 82
Это задание составили эксперты «СтатГрада» для Яндекса
Это задание решали 5 тыс. раз. С ним справились 69% пользователей.
Автомат обрабатывает натуральное число по следующему алгоритму:
Строится двоичная запись числа без ведущих нулей.
Если в полученной записи единиц больше, чем нулей, то справа приписывается единица. Если нулей больше или нулей и единиц поровну, справа приписывается ноль.
Полученное число переводится в десятичную запись и выводится на экран.
Пример. Дано число Алгоритм работает следующим образом:
Двоичная запись числа :
В записи больше единиц, справа приписывается единица:
На экран выводится десятичное значение полученного числа
Какое наименьшее число, превышающее может получиться в результате работы автомата?
Показать разбор и ответ
Автомат приписывает к любому числу одну двоичную цифру. Значит, для любого числа, которое может получиться в результате работы автомата, можно узнать исходное число: для этого нужно перевести результат в двоичную систему и отбросить последнюю цифру.
Наименьшее число, большее равно
это число может получиться только из
Но в двоичной записи этого числа нулей и единиц поровну, значит, по правилам работы автомата приписывается ноль и преобразуется в Тогда результат больше получится при обработке следующего числа: преобразуется в
Ответ: 103
Это задание составили эксперты «СтатГрада» для Яндекса
Это задание решали 5 тыс. раз. С ним справились 73% пользователей.
Автомат обрабатывает натуральное число () по следующему алгоритму:
Строится восьмибитная двоичная запись числа .
Все цифры двоичной записи заменяются на противоположные ( на , на ).
Полученное число переводится в десятичную запись.
Из исходного числа вычитается полученное, разность выводится на экран.
Пример. Дано число . Алгоритм работает следующим образом:
Восьмибитная двоичная запись числа : .
Все цифры заменяются на противоположные, новая запись: .
Десятичное значение полученного числа: .
На экран выводится число: .
Какое число нужно ввести в автомат, чтобы в результате получилось ?
Показать разбор и ответ
Обозначим через число, получаемое после третьего шага указанного в задании алгоритма из исходного числа .
Легко заметить, что двоичная запись суммы состоит из единиц (так как в каждом из восьми разрядов складывается либо и , либо и ). В десятичной системе счисления эта сумма равна .
Таким образом, имеется следующая система уравнений:
Складывая первое уравнение со вторым, получим , откуда .
Ответ: 215
Это задание решали 3 тыс. раз. С ним справились 58% пользователей.
На вход алгоритма подаётся натуральное число Алгоритм строит по нему новое число следующим образом.
Строится двоичная запись числа
К этой записи дописываются справа ещё два разряда по следующему правилу:
складываются все цифры двоичной записи числа и остаток от деления суммы на дописывается в конец числа (справа). Например, запись преобразуется в запись ;
над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа ) является двоичной записью искомого числа
Укажите минимальное число которое превышает число и может являться результатом работы данного алгоритма.
В ответе это число запишите в десятичной системе счисления.
Автомат обрабатывает натуральное число () по следующему алгоритму:
Строится восьмибитная двоичная запись числа .
Все цифры двоичной записи заменяются на противоположные ( на , на ).
Полученное число переводится в десятичную запись.
Из полученного числа вычитается исходное, разность выводится на экран.
Пример. Дано число . Алгоритм работает следующим образом:
Восьмибитная двоичная запись числа : .
Все цифры заменяются на противоположные, новая запись: .
Десятичное значение полученного числа: .
На экран выводится число: .
Какое число нужно ввести в автомат, чтобы в результате получилось ?
Показать разбор и ответ
Обозначим через число, получаемое после третьего шага указанного в задании алгоритма из исходного числа .
Легко заметить, что двоичная запись суммы состоит из единиц (так как в каждом из восьми разрядов складывается либо и , либо и ). В десятичной системе счисления эта сумма равна .
Таким образом, имеется следующая система уравнений:
Вычитая из первого уравнения второе, получим , откуда .
Автомат получает на вход два двузначных шестнадцатеричных числа. По этим числам строится новое шестнадцатеричное число по следующим правилам.
Вычисляются два шестнадцатеричных числа – сумма старших разрядов исходных чисел и сумма младших разрядов.
Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходные числа: . Поразрядные суммы: , . Результат: .
Определите, какое количество чисел из списка ниже может быть результатом работы автомата.
Определите, какое количество чисел из списка ниже может быть результатом работы автомата.
Показать ответ
5
Это задание решали 4 тыс. раз. С ним справились 35% пользователей.
Автомат обрабатывает натуральное число по следующему алгоритму:
Строится восьмибитная двоичная запись числа .
Все цифры двоичной записи заменяются на противоположные ( на , на ).
Полученное число переводится в десятичную запись.
Из нового числа вычитается исходное, полученная разность выводится на экран.
Пример. Дано число . Алгоритм работает следующим образом:
Восьмибитная двоичная запись числа : .
Все цифры заменяются на противоположные, новая запись .
Десятичное значение полученного числа .
На экран выводится число .
Какое число нужно ввести в автомат, чтобы в результате получилось ?
Показать разбор и ответ
Указание:
Найдите сумму исходного и нового числа.
Решение:
Сумма исходного и нового числа в двоичном виде записывается восемью единицами, это соответствует десятичному числу . Значит, новое число равно , а итоговое число, которое выдаёт автомат, равно .
Известно, что , отсюда следует, что .
Ответ: 61
Это задание составили эксперты «СтатГрада» для Яндекса
Это задание решали 8 тыс. раз. С ним справились 58% пользователей.
Автомат обрабатывает натуральное число по следующему алгоритму:
Строится восьмибитная двоичная запись числа .
Все цифры двоичной записи заменяются на противоположные ( на , на ).
Полученное число переводится в десятичную запись.
Из нового числа вычитается исходное, полученная разность выводится на экран.
Пример. Дано число . Алгоритм работает следующим образом:
Восьмибитная двоичная запись числа : .
Все цифры заменяются на противоположные, новая запись .
Десятичное значение полученного числа .
На экран выводится число .
Какое число нужно ввести в автомат, чтобы в результате получилось ?
Показать разбор и ответ
Указание:
Найдите сумму исходного и нового числа.
Решение:
Сумма исходного и нового числа в двоичном виде записывается восемью единицами, это соответствует десятичному числу . Значит, новое число равно , а итоговое число, которое выдаёт автомат, равно .
Известно, что , отсюда следует, что .
Ответ: 72
Это задание составили эксперты «СтатГрада» для Яндекса
Это задание решали 6 тыс. раз. С ним справились 61% пользователей.
Автомат обрабатывает натуральное число по следующему алгоритму.
Строится двоичная запись числа .
Последняя цифра двоичной записи удаляется.
Если исходное число было нечётным, в конец записи (справа) дописываются цифры , если четным – .
Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число . Алгоритм работает следующим образом.
Двоичная запись числа : .
Удаляется последняя цифра, новая запись: .
Исходное число нечётно, дописываются цифры , новая запись: .
На экран выводится число .
Какое число нужно ввести в автомат, чтобы в результате получилось ?
Показать разбор и ответ
Указание:
Двоичная запись нечётных чисел заканчивается единицей, чётных – нулём; при добавлении нуля в конце двоичной записи число удваивается.
Решение:
У нечётного числа автомат удаляет последнюю единицу в двоичной записи, после чего добавляет . Фактически к записи просто добавляется , то есть число удваивается и становится чётным. Аналогично для чётных чисел к записи добавляется , то есть число удваивается и увеличивается на и становится нечётным.
Нечётное число получается из чётного числа .
Ответ: 1008
Это задание составили эксперты «СтатГрада» для Яндекса
Это задание решали 7 тыс. раз. С ним справились 61% пользователей.
Автомат обрабатывает натуральное число по следующему алгоритму.
Строится двоичная запись числа .
Последняя цифра двоичной записи удаляется.
Если исходное число было нечётным, в конец записи (справа) дописываются цифры , если чётным – .
Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число . Алгоритм работает следующим образом.
Двоичная запись числа : .
Удаляется последняя цифра, новая запись: .
Исходное число нечётно, дописываются цифры , новая запись: .
На экран выводится число .
Какое число нужно ввести в автомат, чтобы в результате получилось ?
Показать разбор и ответ
Указание:
Двоичная запись нечётных чисел заканчивается единицей, чётных – нулём; при добавлении нуля в конце двоичной записи число удваивается.
Решение:
У нечётного числа автомат удаляет последнюю единицу в двоичной записи, после чего добавляет . Фактически к записи просто добавляется , то есть число удваивается и становится чётным. Аналогично для чётных чисел к записи добавляется , то есть число удваивается и увеличивается на и становится нечётным.
Чётное число получается удвоением нечётного числа .
Ответ: 1009
Это задание составили эксперты «СтатГрада» для Яндекса
Это задание решали 8 тыс. раз. С ним справились 57% пользователей.
На вход алгоритма подаётся натуральное число . Алгоритм строит по нему новое число следующим образом.
Строится двоичная запись числа .
К этой записи дописываются справа ещё два разряда по следующему правилу: если чётное, в конец числа (справа) дописывается сначала ноль, а затем единица. В противном случае, если нечётное, справа дописывается сначала единица, а затем ноль. Например, двоичная запись числа будет преобразована в , а двоичная запись числа будет преобразована в .
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа ) является двоичной записью числа – результата работы данного алгоритма.
Укажите минимальное число , которое больше и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Показать разбор и ответ
Добавление нуля в конце двоичной записи соответствует умножению исходного
числа на , а добавление единицы умножению на два
и прибавлению к результату единицы. Таким образом,
в случае чётного и в случае
нечётного .
Проверим число . Оно нечётное, то есть могло быть получено
лишь по формуле . Решая уравнение,
получим , что противоречит условиям задачи.
Проверим число . Оно чётное, то есть могло быть получено лишь
по формуле . Решая уравнение, также
получим дробное значение .
Проверим число . Оно нечётное, следовательно ,
откуда . Таким образом, найденное число и оно
могло быть получено в~результате работы автомата из числа .