Задание 5

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится четверичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
 а) если число N делится на 4, то к этой записи числа дописываются две последние четверичные цифры;
 б) если число N на 4 не делится, то остаток от деления умножается на 2, переводится в четверичную запись и дописывается в конец числа.
Полученная таким образом запись является четверичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 11₁₀ = 23₄ результатом является число 2312₄ = 182₁₀,
а для исходного числа 12₁₀ = 30₄ это число 3030₄ = 204₁₀.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 1088.

Теория

Данное задание предполагает знакомство с различными системами счисления и с преобразованием в этой записи числа, а также арифметическими операциями в различных системах счисления, что необходимо для профессионального ит-специалиста.
Например, если справа к n-ричной записи числа приписать 0, то оно увеличится в n раз (два 0 - в n² раз). Также полезно уметь быстро переводить числа из 2-й в 8-ю и 16-ю системы счисления (4-я аналогично) и уметь по количеству разрядов оценивать порядок числа.

С ростом популярности языков программирования и внедрения компьютеров на экзамене эту задачу быстро можно запрограммировать например на Python. К сожалению калькулятор в режиме программиста и Python содержат только функции перевода в двоичную, восьмеричную и шестнадцатеричную системы счислений - желательно знать алгоритм перевода из десятичной в любую другую систему счисления.

Решение

Аналитический способ

Число переводится в четверичную систему счисления - можно вычислять остатки от деления на 4, пока результат не станет меньше 4, а потом записать результат и остатки в обратном порядке. Проще, по аналогии с переводом из двоичной в восьмеричную с использованием триад, использовать наборы по 2 двоичных чисел справа налево (диады). Например 253₁₀ = 11111101₂ = 3331₄.

В четверичной системе счисления добавление двух разрядов справа - умножение исходного числа на 16 плюс число от 0 до 15. Если остаток от деления числа на 4 равен 2 или 3, то остаток умножается на 2 и получается 4 или 6 (в четверичной системе счисления 10 или 12 - будут приписаны два разряда и добавлены числа 4 или 6. Если остаток равен 1 то приписывается только один разряд (умножить на 4) и прибавляется 2. Разделим 1088 на 16 и получим 68. Это число первый кандидат на ответ. Проверим его. 68₁₀ = 64₁₀+4₁₀=1000100₂= 1010₄. Остаток от деления на 16 равен 4 - это две последние цифры, которые по алгоритму преобразования (1 и 2) припишутся справа. Результат - исходное число умножится на 16 и прибавится 4, результат 1092₁₀. Проверим числа 67 и 66.

67₁₀ = 64₁₀ + 3₁₀ = 1000000₂ + 11₂ = 1000011₂ = 1003₄ → 100312₄ = 1078₁₀ - меньше 1088! Число 67 умножается на 16 и к нему прибавляется остаток от деления на 4, который равен 3, умноженный на 2, т.е. 6.

66₁₀ = 1000010₂ = 1002₄ → 100210₄ = 1060₁₀ - тоже меньше. Число 66 умножается на 16 и к нему прибавляется 4 (остаток от деления на 66 на 4 = 2, умножим на 2 и получим 4 - четверичной записи числа это 10). Проверять меньшие числа - решайте сами. 

Ответ 68.

Программа

Ниже представлена программа на языке Python, в котором удобные средства преобразования типов и перевода из базовых систем счисления. Но перевода в четверичную систему счисления нет. Свою функцию напишите самостоятельно. Реализован алгоритм из аналитического способа.

Результат с тестированием и отладкой

Ответ

68 (Время не более 5 минут)