Сложное 14

Рассмотрим ряд сложных задач типа 14 из ЕГЭ по информатике. Тип 14 это задачи на позиционные системы счисления.

Задача 1.

Дано арифметическое выражение 5xyC₁₆ + 8xx7_y. Определите, сколько различных значений может принимать выражение при всех возможных x и y.

Решение

Первым делом определяем какими могут быть x и y. В первом слагаемом x и y являются цифрами 18-тиричного числа, следовательно x  и y натуральные числа меньшие 18. Во втором слагаемом их роли различаются, x - цифра, y - основание системы счисления в которой записано это слагаемое и раз большей видимой цифрой является 8, то y>8, а x<y. Теперь, когда мы нашли область определения x и y, можно подумать и об алгоритме решения.

1. Перебор допустимых значений для  x  и y;
2. Подсчет количества различных значений выражения.

В первом случае воспользуемся двумя вложенными циклами for 

for x in range(16):

    for y in range(9,16):

Для решения второго пункта воспользуемся множеством. Прекрасным свойством множества является то, что если туда попадают одинаковые элементы - остаётся толь один. Т.о. если мы во множество будем складывать все возможные значения выражения, остануться в нем только различные.

Программа

a=set() # а - пустое множество

# перебор всевозможных x и y из их области определения

for x in range(16):

    for y in range(9,16):

        if x<y: # последнее условие

            c=5*16**3+x*16**2+y*16+12+8*y**3+x*y**2+x*y+7

            a.add(c) #добавление очередного значения выражение

print(len(a)) # вывод количества элементов множества

Ответ: 84

Задача 2

Значение выражения 39 • 15⁶⁴ + 35⁴⁵⁰ + 74 • 43¹²¹ - 450035 записали в некоторой системе счисления.

Оказалось, что количество цифр 8 в этой записи максимально.

Найдите эту систему счисления и запишите её в ответе в десятичной системе счисления. Если таких несколько, укажите ту, у которой числовое значение больше.

Решение

Идея решения достаточно проста, будем перебирать основания систем счисления, переводить значение выражения в эти системы и подсчитывать количество восьмёрок. Основание системы счисления больше 8.

 Программа

a=39*15**64+35**450+74*43**121-450035 # вычисление значения выражения

m=0 # максимальное количество цифр 8

n=0 # система счисления с максимальным количеством восьмерок

for i in range(9,100): # Перебор систем счисления

    c=a

    d=0 # количество восьмёрок

# перевод значения выражения в систему счисления i

    while c>0:

        b=c%i

        c//=i

        if b==8: # если очередная цифра равна 8, увеличиваем счетчик d

            d+=1

    if d>=m: # если в записи результата восьмерок больше чем было прежде

        n=i # запоминаем эту систему счисления и

        m=d # меняем максимальное количество цифр 8 в записи результата.

print(n) 

Ответ: 10

Задача 3

Значение выражения 53¹²³ + 65²²²² – 172¹² записали в системе счисления с основанием 7. Определите количество комбинаций цифр 6# в этой записи, где # – любая цифра от 1 до 5.

Решение

Идея решения. Вычисляем результат выражения и переводим его в систему счисления с основанием 7. Затем подсчитываем необходимые комбинации.

a=53**123+65**2222-172**12 # Pyfxtybt dshf;tybz

s='' # пустая строка для записи результата в семеричную систему счисления

while a>0: # стандартно переводим число

    s=str(a%7)+s

    a//=7

n=0 # количество комбинаций

# Подсчет количества комбинаций

for i in '12345': 

    d='6'+i # формируем очередную комбинацию

    n+=s.count(d) 

print(n)

Ответ: 478