Задача. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится четверичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 4, то к этой записи дописываются две последние четверичные цифры;
б) если число N на 4 не делится, то остаток от деления умножается на 2, переводится в четверичную запись и дописывается в конец числа.
Полученная таким образом запись является четверичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 11 = 23_4 четверичным результатом является число 2312_4 = 182, а для исходного числа 12 = 30_4 это число 3030_4 = 204.
Укажите максимальное число N , после обработки которого с помощью этого алгоритма получается число R , меньшее 261.
Решение
Для решения этой задачи мы будем использовать обратный процесс: начнем с наибольшего числа R, меньшего 261, и найдем соответствующее максимальное N .
1. Переведем 260 (поскольку это самое большое число, меньшее 261) из десятичной системы в четверичную систему:
260_{10} = ?_{4}Для этого разделим 260 на 4, отслеживая остатки:
260 \div 4 = 65 остаток 0 65 \div 4 = 16 остаток 1 16 \div 4 = 4 остаток 0 4 \div 4 = 1 остаток 0 1 \div 4 = 0 остаток 1Чтение остатков снизу вверх дает нам:
260_{10} = 10010_{4}2. Теперь нам нужно определить, что было сделано на последнем шаге алгоритма, чтобы получить эту четверичную запись, и найти исходное N. Поскольку последние две цифры 260 в четверичной системе — это 10, то они могли быть добавлены в результате деления N на 4 (правило а). Это означает, что перед добавлением «10» число R было равно 100.
3. Теперь переведем обратно 100 из четверичной системы в десятичную:
1 \cdot 4^2 + 0 \cdot 4^1 + 0 \cdot 4^0 = 16 + 0 + 0 = 16_{10}Это значит, что до добавления «10» на конце, десятичное число N было 16. Но поскольку в результате алгоритма к 16 было добавлено его же деление на 4, то исходное число N было в 4 раза больше, чем 16, то есть N = 64.
4. Теперь проверим, что произойдет, если мы применим алгоритм к числу 64:
64 в четверичной системе: 64_{10} = 1000_{4}.
Добавим две последние цифры (правило а), так как 64 делится на 4, получим 100000_{4}.
Переведем 100000_{4} в десятичную систему:
1 \cdot 4^5 + 0 \cdot 4^4 + 0 \cdot 4^3 + 0 \cdot 4^2 + 0 \cdot 4^1 + 0 \cdot 4^0 = 1024_{10}Но 1024 гораздо больше 260, поэтому нам нужно найти число меньше 64, которое после обработки алгоритмом даст результат меньше 260.
Чтобы уменьшить результат, нужно взять число N, которое на 4 не делится, так чтобы при удвоении остатка и добавлении его в конец четверичного числа R получилось число меньше 10010_{4} .
Если взять N = 63:
63_{10} = 333_{4} (поскольку 63 = 3 + 3 \cdot 4 + 3 \cdot 4^2).Остаток от деления 63 на 4 равен 3, удвоенный остаток равен 6.
6_{10} = 12_{4}, поэтому к 333 добавляем 12, получаем 33312_{4}.Переведем 33312_{4} обратно в десятичную систему:
3 \cdot 4^4 + 3 \cdot 4^3 + 3 \cdot 4^2 + 1 \cdot 4^1 + 2 \cdot 4^0 = 3 \cdot 256 + 3 \cdot 64 + 3 \cdot 16 + 1 \cdot 4 + 2 = 768 + 192 + 48 + 4 + 2 = 1014_{10}1014 также слишком велико. Попробуем взять N = 62:
62_{10} = 332_{4} (поскольку 62 = 2 + 3 \cdot 4 + 3 \cdot 4^2).Остаток от деления 62 на 4 равен 2, удвоенный остаток равен 4.
4_{10} = 10_{4}, поэтому к 332 добавляем 10, получаем 33210_{4}.Переведем 33210_{4} обратно в десятичную систему:
3 \cdot 4^4 + 3 \cdot 4^3 + 2 \cdot 4^2 + 1 \cdot 4^1 + 0 \cdot 4^0 = 3 \cdot 256 + 3 \cdot 64 + 2 \cdot 16 + 1 \cdot 4 + 0 = 768 + 192 + 32 + 4 + 0 = 996_{10}Это тоже больше 260. Мы видим, что нужно уменьшить число N , чтобы получить результат меньше 261. Если продолжить этот процесс, мы найдем максимальное N, при котором R < 261.
Продолжая этот процесс, возьмем N=61:
61_{10} = 331_{4} и 61 на 4 не делится, остаток 1, удвоенный остаток 2. 2_{10} = 2_{4}, поэтому к 331 добавляем 2, получаем 3312_{4}.Переведем 3312_{4} обратно в десятичную систему:
3 \cdot 4^3 + 3 \cdot 4^2 + 1 \cdot 4^1 + 2 \cdot 4^0 = 3 \cdot 64 + 3 \cdot 16 + 1 \cdot 4 + 2 = 192 + 48 + 4 + 2 = 246_{10}246 меньше 261, и это меньше чем для N = 62.
Теперь проверим N = 60, чтобы убедиться, что 61 действительно максимальное значение N, при котором R < 261:
60_{10} = 330_{4} и 60 делится на 4, значит добавляем его последние две цифры 30 к 330, получаем 33030_{4}.Переведем 33030_{4} обратно в десятичную систему:
3 \cdot 4^4 + 3 \cdot 4^3 + 0 \cdot 4^2 + 3 \cdot 4^1 + 0 \cdot 4^0 = 3 \cdot 256 + 3 \cdot 64 + 0 + 3 \cdot 4 + 0 = 768 + 192 + 0 + 12 + 0 = 972_{10}972 также гораздо больше 260. Таким образом, N = 61 является максимальным числом, при обработке которого по алгоритму получается число R, меньшее 261.
Программирование
При решении задачи с помощью Python, мы выполнили следующие шаги:
1. Перевод в четверичную систему: Для каждого натурального числа N в диапазоне от 0 до 260 включительно, мы перевели его в четверичную систему счисления. Это необходимо, потому что алгоритм работает с четверичной записью числа.
2. Обработка четверичной записи:
Если N делится на 4 без остатка, мы взяли две последние цифры его четверичной записи и дописали их в конец этой же записи.
Если N не делится на 4 без остатка, мы умножили остаток от деления на 4 на 2, перевели результат в четверичную систему и дописали его в конец четверичной записи числа N .
3. Перевод обратно в десятичную систему: Полученное четверичное число R было переведено обратно в десятичную систему счисления для сравнения с заданным порогом в 261.
4. Поиск максимального N : Мы итеративно проверяли каждое N , чтобы найти такое максимальное значение, при котором десятичное значение R остается меньше 261. Как только R становилось равным или больше 261, мы прекращали процесс и сохраняли последнее подходящее значение N .
В результате этих шагов, мы нашли, что максимальное значение N , удовлетворяющее условиям задачи, равно 61. Это значит, что для N = 61 , алгоритм даёт наибольшее R , которое все еще меньше 261.
Программа на Python
# Решение задачи с использованием Python
# Функция для перевода десятичного числа в четверичное
def decimal_to_quaternary(n):
if n == 0:
return '0'
quaternary = ''
while n > 0:
quaternary = str(n % 4) + quaternary
n //= 4
return quaternary
# Функция для перевода четверичного числа в десятичное
def quaternary_to_decimal(q):
return int(q, 4)
# Поиск максимального N
max_N = 0
for N in range(261):
# Переводим N в четверичную систему
quaternary_N = decimal_to_quaternary(N)
# Обрабатываем число в соответствии с правилами
if N % 4 == 0:
# Дописываем две последние цифры, если N делится на 4
R = quaternary_N + quaternary_N[-2:]
else:
# Умножаем остаток от деления на 2 и дописываем в конец, если N не делится на 4
remainder = 2 * (N % 4)
R = quaternary_N + decimal_to_quaternary(remainder)
# Переводим полученное четверичное число R в десятичную систему
decimal_R = quaternary_to_decimal(R)
# Проверяем, чтобы R было меньше 261
if decimal_R < 261:
max_N = N # Запоминаем N
max_N
Программа на Pascal
program FindMaxN;
function DecimalToQuaternary(n: Integer): String;
var
quaternary: String;
remainder: Integer;
begin
quaternary := '';
while n > 0 do
begin
remainder := n mod 4;
quaternary := Chr(48 + remainder) + quaternary;
n := n div 4;
end;
if quaternary = '' then
quaternary := '0';
DecimalToQuaternary := quaternary;
end;
function QuaternaryToDecimal(q: String): Integer;
var
decimal, i, power: Integer;
begin
decimal := 0;
power := 1;
for i := Length(q) downto 1 do
begin
decimal := decimal + (Ord(q[i]) - 48) * power;
power := power * 4;
end;
QuaternaryToDecimal := decimal;
end;
var
N, R, maxN: Integer;
quaternaryN, quaternaryR: String;
begin
maxN := 0;
for N := 0 to 260 do
begin
quaternaryN := DecimalToQuaternary(N);
if N mod 4 = 0 then
quaternaryR := quaternaryN + Copy(quaternaryN, Length(quaternaryN) - 1, 2)
else
quaternaryR := quaternaryN + DecimalToQuaternary((N mod 4) * 2);
R := QuaternaryToDecimal(quaternaryR);
if R < 261 then
maxN := N;
end;
WriteLn('Максимальное число N: ', maxN);
end.
Программа на Basic
REM Basic program to find the maximum N for the given condition
FUNCTION DecimalToQuaternary(n)
DIM quaternary AS STRING
quaternary = ""
WHILE n > 0
quaternary = STR$(n MOD 4) + quaternary
n = n \ 4
WEND
IF LEN(quaternary) = 0 THEN
quaternary = "0"
END IF
DecimalToQuaternary = quaternary
END FUNCTION
FUNCTION QuaternaryToDecimal(q)
DIM decimal AS INTEGER
DIM i AS INTEGER
DIM power AS INTEGER
decimal = 0
power = 1
FOR i = LEN(q) TO 1 STEP -1
decimal = decimal + VAL(MID$(q, i, 1)) * power
power = power * 4
NEXT i
QuaternaryToDecimal = decimal
END FUNCTION
DIM maxN AS INTEGER
maxN = 0
FOR N = 0 TO 260
quaternaryN = DecimalToQuaternary(N)
IF N MOD 4 = 0 THEN
quaternaryR = quaternaryN + RIGHT$(quaternaryN, 2)
ELSE
quaternaryR = quaternaryN + DecimalToQuaternary((N MOD 4) * 2)
END IF
R = QuaternaryToDecimal(quaternaryR)
IF R < 261 THEN
maxN = N
END IF
NEXT N
PRINT "Максимальное число N: "; maxN Ответ: 61.