Exam26

Project maintained by K3rnys Hosted on GitHub Pages — Theme by mattgraham

← Назад

5. Анализ и построение алгоритмов для исполнителей, часть 2

Посимвольное преобразование в n-ричной системе счисления · решу ЕГЭ

Если в первой подтеме все задачи +- однотипные, то в этой я насчитал как минимум 3 разных их вида, начнем с первого:

Похоже на предыдущее, но проблема в том, что теперь мы используем троичную систему счисления, а питон из коробки может переводить числа только в:

Поэтому первым делом предлагаю написать функцию для перевода числа в его троичное представление, делать мы это будем посредством простенького алгоритма:

Звучит просто, да?

  1. 11/3 -> 3 наше число, 2 остаётся
  2. 3/3 -> 1 наше число, 0 остаётся, получается 02
  3. 1/3 -> 0 наше число, 1 остаётся, получается 102
  4. мы дошли до 0, алгоритм кончается

Теперь переведем это в код:

Замечу, что ternaryN - это строковый тип, и возвращаем из функции мы именно что строку

Вывод:

Как мы видим, работает ровно как, мы и ожидаем от программы

А самое прекрасное, что подобным образом мы можем переводить числа в любую систему, от двоичной до десятичной

Двоичная:

девятеричная:

В будущих заданиях от нас потребуется уметь переводить и в систему более высокого разряда, например, 37, но об этом потом

А пока, предлагаю вместо цикла использовать рекурсию, так мы сильно сократим количество кода, которое потребуется писать

И вывод получаем тот же самый, 102

Пока ты не запуталась окончательно, объясню логику, она особо не отличается от предыдущего кода

  1. Мы вызываем функцию
  2. Функция возвращает вызов своей функции с первоначальным числом, деленным без остатка на 3, и добавляет в конец остаток от деления нашего числа на 3, и это всё при условии, что число больше 0, иначе возвращает пустую строку
  3. Получается такая картина:
    • render(decN) даёт decN // 3 и decN % 3 -> render(decN//3) + decN % 3
    • render(11) даёт 11 // 3 = 3 и 11 % 3 = 2 -> render(3) + 2 -> '' + 1 + 0 + 2
    • render(3) даёт 3 // 3 = 1 и 3 % 3 = 0 -> render(1) + 0 -> '' + 1 + 0
    • render(1) даёт 1 // 3 = 0 и 1 % 3 = 1 -> render(0) + 1 -> '' + 1
    • render(0) даёт '' -> ''

Надеюсь логика понятна, как мы спускаемся вверх, а затем поднимаемся вверх.

Более того, в любой из этих функций мы можем очень просто указать систему, в которую нам нужно перевести десятичное число, просто заменив степень на какую нибудь переменную, например, pivot

Её мы будем передавать в функцию вместе с числом:

684

Ну и вызов, для примера, render(11, 3) - получим '102'

Вауля, теперь у нас собственная функция для перевода числа из одной системы счисления в другую, ничем не хуже той же bin()

Вернёмся к заданию и сделаем функцию с алгоритмом:

Вывод соответствует, 11 в троичной действительно 102, остаток от деления 11 на 3 это 2, 2 на 5 это 10, а 10 в троичной это 101 при сложении получается 102101, осталось только вернусь к десятичному виду, но это не сложно

Также проверим на числе, которое делится на 3, например, на 15

Выглядит достойно, осталось только в цикле перебрать N и R:

И так мы получаем ответ 162

А вообще советую добавлять проверки на небольших отрезках для N:

Ответ как раз получается при N равном 18, теперь это прекрасно видно

Так же хочу привести в пример решение из ответов решу ЕГЭ. Оно особо не отличается от моего, но я очень хочу, чтобы ты объяснила мне построчно, c комментариями, как он работает

def f(n):
    s=''
    while n > 0:
        s = str(n%3)+s
        n //= 3
    return s
 
c = set()
for n in range(1,100):
    s = f(n)
    if n%3 == 0:
        s = s + s[-2:]
    else:
        s = s + f((n%3)*5)
    r = int(s,3)
    if r <= 173:
        c.add(r)
print(max(c))

Для примера, попробуй решить это, можешь использовать функцию oct(), решение скинешь мне

Ну и конечно, ответ 57

Так, рассмотрим еще одну интересную задачу

Она похожа на то, что будет в задачах дальше, поэтому уделю ей немного внимания

Вся проблема в первом пункте, как нам вообще перебрать все трёхзначные числа в числе?

В этом нам поможет такой замечательный тип данных, как массив

Считай, что это просто хранилище, мы можем положить в 1ую ячейку одно, во 2ую другое, потом достать что то, удалить, и самая прелесть в том, что все ячейки проиндексированы, т.е. если нам нужно достать что то из 3ьей ячейки, мы возьмем её с помощью второго индекса (ну да, они начинаются с 0, а не с 1, небольшой подвох)

Создать массив можно либо с помощью функции list(), либо с помощью указания для переменной этого самого массива X = []

Хочу заметить, что создать его можно уже с чем нибудь внутри, но это уж потом

Так выглядит наш код для этого задания

Из неизвестного тебе тут есть полезная функция для строки, массивов, кортежей и всего, что можно измерить - len(n), которая возвращает количество букв в строке n / элементов в нашем списке n

А еще тут есть метод для списков - .append(n), который добавляет в конец списка элемент n

Функции max() и min() так же работают для для списков, собственно, в них мы всегда и передавали несколько элементов

И break, оператор, который позволяет незамедлительно завершить цикл (вместе с ним есть оператор continue, который позволяет пропустить текущий этап в цикле) (оператор / выражение / инструкция, ну или просто statements)

Обращаю особое внимание на 7 и 8 строку, мы брали первые 3 элемента из строки, записывали их, а затем удаляли первый элемент строки, и это всё до тех пор, пока строка не становилась меньше 3 символов

Мы могли спокойно поменять эти строки на такое

И тогда мы бы вносили последние 3 элемента, а потом удаляли бы последний, но разницы по сути никакой

И так, ответ, 1572, потому что 572 - 157 действительно 415

Вот похожая задачка тебе на подумать, решение скинешь мне

Ответ 72

Третий тип отличается от первого только добавлением пары новых условий, я не буду приводить пример решения, просто укажу, что нужно использовать, а дальше давай сама)

Теперь попробуй решить это, тут нет массивов, зато есть парочка других интересных мест, в этом тебе помогут:

  1. Метод для строки .replace('a', 'b', n), который заменяет в строке все подстроки 'a' на подстроки 'b' n раз, но не изменяет изначальную строку, только для присваивания.

    Если не указывать n, то заменяет все подстроки

    s = 'banana' -> print(s.replace('a', 'o'), s) -> 'bonono', 'banana'

  2. Методы для строки .strip('n'), .lstrip('n'), .rstrip('n')

    Помогают удалить из строки все ведущие пробелы или нули по умолчанию (или что нибудь еще, если это точно указать в скобках)

    Как и с .replace() не изменяют строку, только для присваивания

    P.S. А вообще функция int('a', n) и так по умолчанию не учитывает ведущие нули, но это так, мем на подумать))

  3. Ну и функция для взятия модуля от числа - abs(n), тут и сказать нечего, вместо n как бы и выражения могут быть, 35-45, например, даст 10

Решение так же закинешь мне

Ответ впечатляет 3323607