Задание 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) Далее эта запись обрабатывается по следующему правилу:
а) если количество значащих цифр в двоичной записи числа чётное, то к этой записи в середину дописывается 1;
б) если количество значащих цифр в двоичной записи числа нечётное, то запись не изменяется.
Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 5₁₀ = 101₂ результатом является число 101₂ = 5₁₀, а для исходного числа 2₁₀ = 10₂ результатом является число 110₂ = 6₁₀.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее, чем 26. В ответе запишите это число в десятичной системе счисления.

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

Пояснение

Решение:

Если количество разрядов двоичной записи $N$ нечётно, запись не меняется и $R=N$ . Если чётно — в середину вставляется 1.

Ищем наименьшее $N$ , при котором $R\ge 26$ .

Числа $N\le 7$ записываются не более чем тремя разрядами, поэтому $R$ содержит не более трёх разрядов и $R\le 7$ — мало. Числа от 8 до 15 записываются четырьмя разрядами, вставка даёт пятиразрядную запись:

$N=8=1000_2\to 10100_2=20$ ;
$N=9=1001_2\to 10101_2=21$ ;
$N=10=1010_2\to 10110_2=22$ ;
$N=11=1011_2\to 10111_2=23$ ;
$N=12=1100_2\to 11100_2=28\ge 26$ — подходит.

Все меньшие числа дают $R\lt 26$ , поэтому искомое наименьшее $N$ равно 12.

def alg(n):
    b = bin(n)[2:]
    if len(b) % 2 == 0:
        b = b[:len(b) // 2] + '1' + b[len(b) // 2:]
    return int(b, 2)

print(min(n for n in range(1, 1000) if alg(n) >= 26))

Ответ: 12