Задание 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 вычитается остаток от деления N на 4.
2) Строится двоичная запись полученного результата.
3) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры построенной двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия - справа дописывается остаток от деления суммы её цифр на 2.

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

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

114

Пояснение

Решение:

Обозначим $M=N-(N\bmod 4)$ — результат первого шага. Это ближайшее снизу число, кратное 4, и при переборе всех $N$ величина $M$ пробегает в точности все кратные четырём числа.

Пусть в двоичной записи $M$ ровно $k$ единиц и $p=k\bmod 2$ . На шаге 3а справа приписывается $p$ . После этого сумма цифр равна $k+p$ — она чётна при любом $k$ , поэтому на шаге 3б приписывается 0.

Итак, к записи $M$ всегда приписываются два разряда $p$ и 0, то есть $R=4M+2p$ , где $p$ — чётность количества единиц в $M$ .

Нужно наименьшее $R\gt 100$ . Так как $p\le 1$ , из $4M+2p\gt 100$ следует $4M\ge 99$ , то есть $M\ge 25$ ; а $M$ кратно 4, поэтому $M\ge 28$ . Величина $R=4M+2p$ растёт вместе с $M$ , значит достаточно взять наименьшее допустимое $M=28$ .

$M=28=11100_2$ , единиц три, $p=1$ : запись $11100$ превращается в $111001$ , затем в $1110010$ , то есть $R=1110010_2=114$ .

Для сравнения, предыдущее кратное четырём $M=24=11000_2$ даёт $p=0$ и $R=96$ — это не больше 100.

def alg(n):
    b = bin(n - n % 4)[2:]
    b += str(sum(map(int, b)) % 2)
    b += str(sum(map(int, b)) % 2)
    return int(b, 2)

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

Ответ: 114