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

Например, для исходного числа 11 = 23₄ результатом является число 2312₄= 182, а для исходного числа 12 = 30₄ это число 3030₄ = 204.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 1025.

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

Пояснение

Решение:

Пусть $r=N\bmod 4$ — последняя цифра четверичной записи $N$ . Разберём, что приписывается справа в каждом случае.

$r=0$ : приписываются две последние четверичные цифры, то есть запись удлиняется на два разряда, а приписанное значение равно $N\bmod 16$ . Значит $R=16N+(N\bmod 16)$ .
$r=1$ : $2r=2=2_4$ — один разряд, поэтому $R=4N+2$ .
$r=2$ : $2r=4=10_4$ — два разряда, поэтому $R=16N+4$ .
$r=3$ : $2r=6=12_4$ — два разряда, поэтому $R=16N+6$ .

Сверим с примерами из условия: $N=11$ , $r=3$ , $R=16\cdot 11+6=182$ ; $N=12$ , $r=0$ , $R=16\cdot 12+12=204$ . Совпадает.

Ключевое наблюдение: только при $r=1$ число увеличивается в 4 раза, во всех остальных случаях — в 16 раз.

Нужно наименьшее $N$ , при котором $R\ge 1025$ . Рассмотрим все четыре случая.

$r=1$ : $4N+2\ge 1025\Rightarrow N\ge 256$ . Наименьшее число вида $4k+1$ — это $N=257$ .
$r=2$ : $16N+4\ge 1025\Rightarrow N\ge 64$ . Наименьшее число вида $4k+2$ — это $N=66$ , $R=16\cdot 66+4=1060$ .
$r=3$ : $16N+6\ge 1025\Rightarrow N\ge 64$ . Наименьшее число вида $4k+3$ — это $N=67$ , $R=1078$ .
$r=0$ : $N=64$ даёт $R=16\cdot 64+0=1024$ — ровно на единицу меньше нужного, не подходит. Следующее кратное четырём $N=68$ даёт $R=16\cdot 68+4=1092$ .

Наименьшее из чисел 257, 66, 67, 68 — это 66.

def alg(n):
    q = ''
    m = n
    while m:
        q = str(m % 4) + q
        m //= 4
    if n % 4 == 0:
        q += q[-2:]
    else:
        t = (n % 4) * 2
        q += str(t) if t < 4 else str(t // 4) + str(t % 4)
    return int(q, 4)

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

Ответ: 66