Задание 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, из-за чего число разрядов увеличивается на единицу и становится нечётным, а само число возрастает: $R\gt N$ .

Итак, в любом случае запись $R$ содержит нечётное число разрядов и $R\ge N$ .

Число $26=11010_2$ записывается пятью разрядами. Посмотрим, что даёт $N\gt 26$ :

при $27\le N\le 31$ в записи $N$ пять (нечётное число) разрядов, поэтому $R=N\gt 26$ — не подходит;
при $32\le N\le 63$ в записи $N$ шесть разрядов, значит в записи $R$ их семь и $R\ge 64$ — не подходит;
при $N\ge 64$ тем более $R\ge N\ge 64$ .

Само число $N=26=11010_2$ записывается пятью разрядами — количество нечётное, запись не изменяется, $R=26\le 26$ . Условие выполнено.

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(max(n for n in range(1, 1000) if alg(n) <= 26))

Ответ: 26