Алгоритмы, которые меняют запись числа
В задании 5 алгоритм строит двоичную или другую запись числа N, дописывает, заменяет или удваивает её цифры и получает число R. Программа повторяет алгоритм в функции над строкой и перебирает N, а вопрос решает условие в цикле: наименьшее N, наибольшее N или наименьший возможный результат R. Короткие правила, например дописывание битов чётности, решаются и вручную: дописать цифру справа значит умножить число на основание и прибавить цифру.
Как решать задание 5
Алгоритм превращает число в число через запись в системе счисления. — число из вопроса задачи.
- Функция
R(n): записьs = bin(n)[2:], действия над строкойs, результатint(s, 2). - Наименьшее , при котором больше : цикл по вверх, первое подходящее — ответ.
- Наибольшее , при котором меньше : перебор всех до , запоминается последнее подходящее.
- Наименьшее возможное , большее : соберите все результаты и возьмите наименьший из подходящих.
- Вручную: дописать цифру справа к P-ичной записи — получить .
Запись числа как строка
Алгоритм задания 5 меняет запись числа, поэтому в программе запись хранят строкой. bin(n)[2:] — двоичная запись без приставки 0b. Над строкой работают срезы и методы: s + '01' дописывает цифры справа, '1' + s — слева, s[2:] отрезает два левых разряда, s[-2:] — две последние цифры, s.count('1') — число единиц, то есть сумма цифр двоичной записи. Середина строки длины — позиция L // 2: s[:L // 2] + '1' + s[L // 2:] вставляет 1 в середину.
Готовую строку переводят в число функцией int(s, 2). Перевод и приставки bin — в теме позиционные системы счисления.
Пример
К двоичной записи числа справа дописывают остаток от деления суммы её цифр на 2. Затем то же делают с новой записью. Найдите результат .
- 1., единиц три, остаток 1: запись .
- 2.В новой записи единиц четыре, остаток 0: запись .
- 3.. Программа печатает 110110 54.
Ответ:
Дописывание разрядов вручную
Дописать к P-ичной записи числа цифру справа — значит получить : все цифры сдвигаются на разряд влево. Дописать справа две двоичные цифры — получить плюс значение этих цифр. Дописать цифры слева к числу из цифр — прибавить их значение, умноженное на . Эти правила разобраны в теме позиционные системы счисления.
Частый алгоритм — два бита чётности: дважды дописывают остаток от деления суммы цифр на 2. Если в записи единиц чётное число, дописываются 0 и 0, и . Если нечётное, дописываются 1 и 0, и . Значит, всегда чётно и в его записи всегда чётное число единиц.
Пример задания
Открытый банк ФИПИ
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1210 = 11002 результатом является число 1100002 = 4810, а для исходного числа 710 = 1112 это число 111102 = 3010.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше числа 253.
В ответе запишите это число в десятичной системе счисления.
Программа: наименьшее N
Функция R(n) повторяет алгоритм шаг за шагом: строит запись, проверяет условие правила через if и меняет строку. Цикл for n in range(1, 1000) перебирает по возрастанию. Первое , при котором условие на верно, — наименьшее, и цикл останавливает break.
Сначала проверьте функцию на примерах из условия: она должна давать те же . Читайте вопрос точно: «больше» — знак >, «не меньше» — знак >=.
Пример
Строится двоичная запись числа . Если чётное, к записи справа дописывают 01. Если нечётное, слева дописывают 11. Получается двоичная запись числа . Найдите наименьшее , при котором больше 100.
- 1.Проверка функции: , .
- 2.Цикл идёт по от 1. Все до не больше 100: .
- 3. нечётное: , это больше 100. Программа печатает 17.
Ответ:
Наименьший результат R, больший K
Вопрос «укажите наименьшее число , большее , которое может получиться» спрашивает о результате, а не об . Перебирайте , считайте и оставьте только те , которые больше . Ответ — наименьшее из них: min(R(n) for n in range(1, 1000) if R(n) > K). Результат растёт не всегда вместе с , поэтому первое найденное не обязательно наименьшее.
Вручную помогает длина записи. Если алгоритм удлиняет запись на известное число цифр, найдите, сколько цифр должно быть у , и подберите наименьшую запись такой длины, которую алгоритм может дать.
Пример задания
Открытый банк ФИПИ
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) Каждый разряд этой записи заменяется двумя разрядами по следующему правилу: если в разряде стоит 0, то вместо него пишется 00; если в разряде стоит 1, то 1 заменяется на 11.
Например, двоичная запись 1001 числа 9 будет преобразована в 11000011.
Полученная таким образом запись (в ней в два раза больше разрядов, чем в записи исходного числа N) является двоичной записью числа R — результата работы данного алгоритма.
Укажите минимальное число R, большее 63, которое может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Запись в четверичной и другой системе
Если алгоритм строит запись в системе с основанием , функции bin нет. Запись строит цикл деления на из темы позиционные системы счисления, его оформляют отдельной функцией. Результат переводят обратно через int(s, p). Сумма цифр P-ичной записи — sum(int(c) for c in s).
Число, которое дописывают в конец, тоже сначала переводят в систему . Если оно не меньше , его запись займёт две цифры: в четверичной системе , а удвоенный остаток .
Пример
Строится четверичная запись числа . Справа к ней дописывают остаток от деления суммы её цифр на 4. Получается четверичная запись числа . Найдите наименьшее , при котором больше 200.
- 1.Дописывание одной цифры даёт , где от 0 до 3. больше 200 не раньше .
- 2., сумма цифр 5, остаток 1: .
- 3.Программа перебирает с функцией
to4и печатает 50.
Ответ:
Программа: наибольшее N
Если нужно наибольшее , при котором меньше , цикл не останавливают на первом подходящем числе. Он проходит весь диапазон, а переменная best запоминает каждое подходящее . После цикла в ней последнее, то есть наибольшее. Алгоритм только дописывает цифры, поэтому больше , и перебор до ничего не пропускает.
Пример задания
Открытый банк ФИПИ
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится четверичная запись числа N.
2) Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 4, то к этой записи дописываются две последние четверичные цифры;
б) если число N на 4 не делится, то остаток от деления умножается на 2, переводится в четверичную запись и дописывается в конец числа.
Полученная таким образом запись является четверичной записью искомого числа R.
Например, для исходного числа 11 = 234 результатом является число 23124 = 182, а для исходного числа 12 = 304 это число 30304 = 204.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 261.
Автомат над десятичными цифрами
Другой вид задания 5: автомат берёт цифры трёхзначного числа, считает из них два числа (суммы квадратов, произведение, сумму) и записывает их подряд в порядке невозрастания. Цифры числа дают n // 100, n // 10 % 10 и n % 10: цифры числа.
Вручную результат разрезают на два числа: левое не меньше правого, и оба не больше наибольшего возможного значения (сумма квадратов двух цифр не больше ). Затем подбирают цифры. Для наибольшего исходного числа ставят большую цифру в старший разряд. Программа перебирает все числа от 100 до 999 и запоминает последнее, которое даёт нужный результат.
Пример задания
Открытый банк ФИПИ
Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам:
1) Вычисляются суммы квадратов первой и второй, а также второй и третьей цифр исходного числа.
2) Полученные два числа записываются друг за другом в порядке невозрастания (без разделителей).
Пример. Исходное число: 621. Суммы квадратов цифр: Результат: 405.
Укажите наибольшее число, при обработке которого автомат выдаст число 9752.