Задание 5 ЕГЭ: Алгоритмы преобразования чисел

Шаг 1: Понимаем алгоритм

• Если N % 3 == 0: дописываем 3 последние цифры двоичной записи
• Если N % 3 != 0: умножаем остаток на 3, переводим в двоичную и дописываем

Шаг 2: Проверка примеров вручную

Для N = 12:

• 12₁₀ = 1100₂
• 12 % 3 = 0 → дописываем 3 последние цифры: 1, 0, 0
• 1100100₂ = 1×64 + 1×32 + 0×16 + 0×8 + 1×4 + 0×2 + 0×1 = 100₁₀ ✓

Для N = 4:

• 4₁₀ = 100₂
• 4 % 3 = 1 → остаток 1 × 3 = 3 = 11₂
• Дописываем: 10011₂ = 16 + 2 + 1 = 19₁₀ ✓

Шаг 3: Программное решение

def algorithm(n):
    # Переводим в двоичную систему (без префикса 0b)
    binary = bin(n)[2:]
    
    if n % 3 == 0:
        # Дописываем 3 последние цифры
        binary += binary[-3:]
    else:
        # Остаток умножаем на 3 и переводим в двоичную
        remainder = n % 3
        addition = bin(remainder * 3)[2:]
        binary += addition
    
    # Переводим обратно в десятичную
    result = int(binary, 2)
    return result

# Проверяем примеры
print(algorithm(12))  # Должно быть 100
print(algorithm(4))   # Должно быть 19

# Ищем максимальное R <= 170
max_r = 0
for n in range(1, 200):
    r = algorithm(n)
    if r <= 170:
        max_r = max(max_r, r)

print(f"Ответ: {max_r}")

Ответ: 164

Объяснение: Программа перебирает все натуральные числа, применяет к ним алгоритм и находит максимальное R, которое не превышает 170.

Шаг 1: Понимаем алгоритм

• Дважды дописываем контрольный бит (остаток от деления суммы цифр на 2)
• Это алгоритм добавления битов чётности

Шаг 2: Проверка примера вручную

Для записи 11100:

• Сумма цифр: 1+1+1+0+0 = 3
• 3 % 2 = 1 → дописываем 1: 111001
• Новая сумма: 1+1+1+0+0+1 = 4
• 4 % 2 = 0 → дописываем 0: 1110010

Шаг 3: Программное решение

def algorithm(n):
    # Переводим в двоичную систему
    binary = bin(n)[2:]
    
    # Первое дописывание
    sum_digits = sum(int(d) for d in binary)
    parity1 = sum_digits % 2
    binary += str(parity1)
    
    # Второе дописывание
    sum_digits = sum(int(d) for d in binary)
    parity2 = sum_digits % 2
    binary += str(parity2)
    
    # Переводим обратно в десятичную
    result = int(binary, 2)
    return result

# Ищем минимальное R > 43
for n in range(1, 100):
    r = algorithm(n)
    if r > 43:
        print(f"Ответ: {r}")
        break

Ответ: 44

Проверка: n=10 → 1010₂ → сумма=2, 2%2=0 → 10100₂ → сумма=2, 2%2=0 → 101000₂ = 40 (меньше 43)
n=11 → 1011₂ → сумма=3, 3%2=1 → 10111₂ → сумма=4, 4%2=0 → 101110₂ = 46 (больше 43, но не минимальное)
Нужно проверить все варианты программой.

Шаг 1: Понимаем алгоритм

• Если N чётное: дописываем 2 последние цифры справа
• Если N нечётное: добавляем 1 в начало и 0 в конец

Шаг 2: Проверка примеров

Для N = 11 (нечётное):

• 11₁₀ = 1011₂
• Добавляем 1 в начало: 11011₂
• Добавляем 0 в конец: 110110₂ = 54₁₀ ✓

Для N = 10 (чётное):

• 10₁₀ = 1010₂
• Две последние цифры: 1, 0
• Дописываем: 101010₂ = 42₁₀ ✓

Шаг 3: Программное решение

def algorithm(n):
    # Переводим в двоичную систему
    binary = bin(n)[2:]
    
    if n % 2 == 0:  # Чётное
        # Дописываем две последние цифры
        binary += binary[-2:]
    else:  # Нечётное
        # Добавляем 1 в начало и 0 в конец
        binary = '1' + binary + '0'
    
    # Переводим обратно в десятичную
    result = int(binary, 2)
    return result

# Проверяем примеры
print(algorithm(11))  # Должно быть 54
print(algorithm(10))  # Должно быть 42

# Ищем максимальное N, при котором R < 100
max_n = 0
for n in range(1, 100):
    r = algorithm(n)
    if r < 100:
        max_n = max(max_n, n)

print(f"Ответ: {max_n}")

Ответ: 24

Объяснение: Для N=24: 24₁₀ = 11000₂ → дописываем 00 → 1100000₂ = 96₁₀ < 100 ✓
Для N=25: 25₁₀ = 11001₂ → 1110010₂ = 114₁₀ ≥ 100 ✗

def algorithm(n):
    binary = bin(n)[2:]
    
    if n % 3 == 0:
        binary += binary[-3:]
    else:
        remainder = n % 3
        addition = bin(remainder * 3)[2:]
        binary += addition
    
    result = int(binary, 2)
    return result

# Ищем минимальное R > 151
for n in range(1, 200):
    r = algorithm(n)
    if r > 151:
        print(f"Ответ: {r}")
        break

Ответ: 152

Шаг 1: Функция перевода в троичную систему

def to_base3(n):
    """Перевод числа в троичную систему"""
    if n == 0:
        return '0'
    result = ''
    while n > 0:
        result = str(n % 3) + result
        n //= 3
    return result

def algorithm(n):
    # Переводим в троичную систему
    ternary = to_base3(n)
    
    if n % 3 == 0:
        # Дописываем две последние цифры
        ternary += ternary[-2:]
    else:
        # Вычисляем сумму цифр
        digit_sum = sum(int(d) for d in ternary)
        # Переводим сумму в троичную и дописываем
        addition = to_base3(digit_sum)
        ternary += addition
    
    # Переводим обратно в десятичную
    result = int(ternary, 3)
    return result

# Проверяем примеры
print(algorithm(11))  # Должно быть 102
print(algorithm(12))  # Должно быть 111

# Ищем минимальное чётное R > 220
for n in range(1, 300):
    r = algorithm(n)
    if r > 220 and r % 2 == 0:
        print(f"Ответ: {r}")
        break

Ответ: 222

Проверка: n=73 → 73₁₀ = 2201₃ → сумма цифр = 2+2+0+1 = 5 = 12₃ → 220112₃ = 222₁₀ ✓ (чётное)

Шаг 1: Понимаем алгоритм

• Для числа ABC: вычисляем A+B и B+C
• Записываем результаты в порядке убывания

Шаг 2: Анализ результата 1412

Результат 1412 означает, что две суммы дали 14 и 12 (в порядке убывания).

Значит: max(A+B, B+C) = 14 и min(A+B, B+C) = 12

Вариант 1: A+B=14, B+C=12

Из первого: A = 14-B, из второго: C = 12-B

Минимизируем число ABC, начинаем с B=5:

• B=5: A=9, C=7 → число 957
• B=6: A=8, C=6 → число 866
• B=7: A=7, C=5 → число 775
• B=8: A=6, C=4 → число 684
• B=9: A=5, C=3 → число 593

Вариант 2: A+B=12, B+C=14

• B=5: A=7, C=9 → число 759
• B=6: A=6, C=8 → число 668
• B=7: A=5, C=7 → число 577
• B=8: A=4, C=6 → число 486
• B=9: A=3, C=5 → число 395

Шаг 3: Программное решение

def algorithm(n):
    # Разбиваем трёхзначное число на цифры
    a = n // 100
    b = (n // 10) % 10
    c = n % 10
    
    # Вычисляем суммы
    sum1 = a + b
    sum2 = b + c
    
    # Записываем в порядке убывания
    if sum1 >= sum2:
        result = int(str(sum1) + str(sum2))
    else:
        result = int(str(sum2) + str(sum1))
    
    return result

# Ищем минимальное трёхзначное число, дающее 1412
min_num = float('inf')
for n in range(100, 1000):
    if algorithm(n) == 1412:
        min_num = min(min_num, n)

print(f"Ответ: {min_num}")

Ответ: 395

Проверка: 395 → 3+9=12, 9+5=14 → max=14, min=12 → 1412 ✓