На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R меньшее 261

Задача. На вход алгоритма подаётся натуральное число 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.

Спасибо:
( 1 оценка, среднее 5 из 5 )
Справочник для школьников
Подписаться
Уведомить о
0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии