Exam26

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

← Назад

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

В этой теме есть 2 основных вида заданий

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

Начну с подтемы попроще:

Посимвольное двоичное преобразование · решу ЕГЭ

Пример:

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

Напомню, что в питоне функция выглядит так:

def *name*(*переменные через запятую, которые будут использоваться ТОЛЬКО внутри функции*):
	*code*
	return *что данная функция возвращает*

Попробуем написать код:

  1. Строится двоичная запись числа N

    Это значит, что у нас есть переменная N типа int, которая хранит в себе десятичное число

    Далее мы делаем переменную, например binN, которой через = присваиваем двоичную запись числа N, сделать это можно с помощью команды bin(N)[2:]

    bin() - преобразование числа в строку, в двоичный вид, например, 0b1010, а [2:] - это работа со строкой, удаление первых двух символов, то есть 0b, чтобы мы получили только двоичную запись 1010

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

    binN = bin(funcN)[2:]

  2. К этой записи дописывается еще 2 разряда по след принципу:

    Складываются цифры двоичной записи, и остаток от деления на 2 дописывается справа

    Для сложения просто посчитаем количество единиц в двоичной записи через строковый метод .count() (сразу замечу, что разница функции и метода в том, что в функцию просто что то передается, и она имеет вид name(example), а вот метод привязан к типу нашей переменной, и мы не сможем вызвать у числовой или строковой переменной метод для списков)

    Поскольку метод строковый, то и значение в нем должно быть строкой, а чтобы передать туда строку, мы либо указываем её явно через функцию создания str(example), либо просто заносим в кавычки 'example'

    Тем не менее, метод .count() возвращает число, то есть объект типа int..

    Так вот, давай сразу добавим к нашему binN в конец новое число, это делается так:

    binN += str(binN.count('1') % 2)

    По сути мы только что присвоили переменной binN строку, состоящую из строки первоначальной binN, сложенной с остатком от деления на 2 (оператор mod(), он же %) количества единиц в binN

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

    (Во избежание неожиданного поведения лучше заранее указывать тип переменной через str() int() bool() float() и тд..)

    (Другая запись binN = str(binN) + str(binN.count('1') % 2), результат тот же)

    alt

    Вывод 11101 (было 1110, 3%2 это 1, дописываем в конец)

  3. И так, последнее действие, снова дописать остаток от деления на 2 суммы чисел в двоичной записи, для этого мы просто повторим предыдущую строку

    Вывод 111010 (было 11101, 4%2 это 0, в конец его)

    Вот и всё, полученная запись - двоичное представление числа R. Чтобы вернуть его обратно в десятичный вид, достаточно написать int(binN, 2)

    При помощи конструкции int(*переменная*, *число*) мы можем приводить хоть троичную хоть какую запись обратно к десятичной

    Так выглядит наша функция:

  4. Осталось только найти минимальное R, которое превышает 43, для этого сделаем цикл, в котором будем по очереди подавать в нашу функцию числа N от 1 до .. пусть до 10000, этого хватит с головой (для примера покажу на 7)

    Ну и чтобы не искать руками, добавим перед циклом переменную result, присвоим ей 1000, и, если R больше 43, будем сравнивать R с result и записывать наименьшее число в result, так мы точно не допустим ошибки в тех случаях, где R идет не в определенном порядке

    Для этого запишем до цикла result = 1000 и в цикле if R > 43: result = min(result, R), так мы будем выбирать наименьшее из двух чисел и записывать в нашу переменную

    Вот и всё, ответ 46, и код около универсальный

Вообще срезы [a:b:c] - довольно мощный инструмент, который позволяет изменять строку, как тебе угодно

Тут a - от какого индекса, b - до какого индекса, c - с каким шагом

Если написать 'abcd'[1:], то получится 'bcd'

Лучше почитай о срезах самостоятельно, попробуй потрогать их сама, на ЕГЭ это точно надо

Вот, теперь с этим знанием иди и сделай это, код мне скинешь

Ответ тут такой 1009