Задание 5

Формальное исполнение простого алгоритма, записанного на естественном языке, или умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд, или умение восстанавливать исходные данные линейного алгоритма по результатам его работы · 26 заданий

Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом: 1) Строится двоичная запись числа N. 2) Далее…
Анализ алгоритмов и исполнители
Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) Далее…
Анализ алгоритмов и исполнители
Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К это…
Анализ алгоритмов и исполнители
Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом: 1) Строится двоичная запись числа N. 2) Кажды…
Анализ алгоритмов и исполнители
Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом: 1) Строится двоичная запись числа N. 2) Кажды…
Анализ алгоритмов и исполнители
Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом: 1) Из числа N вычитается остаток от деления N…
Анализ алгоритмов и исполнители
Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом: 1) Из числа N вычитается остаток от деления N…
Анализ алгоритмов и исполнители
Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом: 1) Строится двоичная запись числа N. 2) Далее…
Анализ алгоритмов и исполнители
Задание №5
№5
Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам: 1) Вычисляются суммы квадратов первой и второй,…
Анализ алгоритмов и исполнители
Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится четверичная запись числа N. 2) Да…
Анализ алгоритмов и исполнители
Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится четверичная запись числа N. 2) Да…
Анализ алгоритмов и исполнители
Задание №5
№5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится четверичная запись числа N. 2) Да…
Анализ алгоритмов и исполнители

Задание №5 — Анализ простейших алгоритмов

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

1) Строится двоичная запись числа N.
2) Каждый разряд этой записи заменяется двумя разрядами по следующему правилу: если в разряде стоит 0, то вместо него пишется 00; если в разряде стоит 1, то 1 заменяется на 11.
Например, двоичная запись 1001 числа 9 будет преобразована в 11000011.

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

Правильный ответ

192

Пояснение

Решение:

Алгоритм просто удваивает каждый разряд двоичной записи $N$ . Если запись $N$ содержит $m$ разрядов, то запись $R$ содержит ровно $2m$ разрядов, причём она составлена из пар 11 и 00.

Чем короче запись $R$ , тем меньше само число, поэтому сначала подбираем минимально возможную длину, а затем — минимальное число такой длины.

При $m=3$ (то есть $N$ от 4 до 7) запись $R$ шестиразрядная, и самое большое такое значение — $N=7\to 111111_2=63$ . Оно не больше 63, поэтому шести разрядов не хватает.

Значит, нужно $m\ge 4$ . Наименьшее восьмиразрядное $R$ получается из наименьшего четырёхразрядного $N=8=1000_2$ :

$1000_2\to 11000000_2=192$ .

def alg(n):
    return int(''.join(c * 2 for c in bin(n)[2:]), 2)

print(min(r for r in {alg(n) for n in range(1, 100)} if r > 63))

Ответ: 192